将红黑树转换为AVL树算法

Question

我需要写一个接收红黑树并将其转换为AVL树的算法。不一定要是完美的代码，伪代码也可以。甚至是帮助我入门的主要想法。不知道怎么开始，请帮帮忙。谢谢！

Answer 1

你有一棵红黑相间的树：

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!