我正在寻找所有AVL树都可以像红黑树一样着色的证据吗？
谁能提供证明？
最佳答案
根据定义，R / B树的平衡可能比AVL-s稍差，如| maxPath-minPath |。对于AVL，必须为
4
/ \
3 6
/\ /\
1 E 5 8
是完全合法的AVL，并且不是R / B，因为R / B不能包含叶子，并且必须以空树结尾，空树的颜色始终为黑色-因此您无法为上面的树着色。
为了使其成为R / B，您可以将每个叶子x转换为节点E x E
然后遵循以下规则：
R / B树：
必须是BST
必须仅包含黑色或红色的节点和空树
每个红色节点都有黑色子节点
所有空树都是黑色的
给定一个节点，所有指向“空树”的路径必须具有相同数量的“黑色节点”
可以用左右子树为空的Node替换任何Leaf
最大路径T≤2 *最小路径T
顺便说一句，Btw刚刚意识到它使我的节点着色并留下红色-这不是故意的。
卡罗尔
关于data-structures - AVL树是否总是红黑树的子集？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/431714/