将红黑树转换为AVL树

Question

我试图将红黑树转换为AVL树但我无法做到这一点。请提供伪算法或某种语言的实现

Answer 1

好吧，你不能直接，因为一些RB树不是有效的AVL树（因为它们太不平衡）。当然，您可以简单地创建一个新的AVL树并将RB树中的所有项目插入其中。或者，您必须剥离颜色并执行重新平衡操作以使所有叶子的深度足够接近。