<分区>
我需要编写一个算法来接收红黑树并将其转换为 AVL 树。 不必是完美的代码，伪代码也可以。甚至帮助我入门的主要想法。 不知道如何开始，请帮助。 谢谢!
<分区>
我需要编写一个算法来接收红黑树并将其转换为 AVL 树。 不必是完美的代码，伪代码也可以。甚至帮助我入门的主要想法。 不知道如何开始，请帮助。 谢谢!
最佳答案
你有一棵红黑树:
data Color = Black | Red
data RB a = NodeRB !Color (RB a) a (RB a) | TipRB
instance Foldable RB where
foldMap _ TipRB = mempty
foldMap f (NodeRB _ l v r) =
foldMap f l <> f v <> foldMap f r
这给了我们 length 和 toList
你想要一棵 AVL 树:
data AVL a = NodeAVL Int (AVL a) a (AVL a) | TipAVL
fromListAVL :: Int -> Int -> [a] -> (AVL a, [a])
fromListAVL _ 0 xs = (TipAVL, xs)
fromListAVL _ _ [] = (TipAVL, [])
fromListAVL _ 1 (x:_) = NodeAVL 1 TipAVL x TipAVL
fromListAVL d xs = case fromListAVL (d-1) (n `quot` 2) xs of
(NodeAVL _ l v r,[]) -> NodeAVL d l v r
(t,(x:xs)) = NodeAVL d n t x $
fst (fromListAVL (d-1) (n-n `quot` 2-1)) xs
rbToAVL :: RB a -> AVL a
rbToAVL rb = fromListAVL depth lrb (toList rb)
where lrb = length rb
depth = calculateDepth lrb -- write this!
关于algorithm - 将红黑树改成AVL树算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28793497/