algorithm - 将Red-Black树更改为AVL树算法

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
我需要写一个接收红黑树并将其转换为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 - 将Red-Black树更改为AVL树算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28793497/