红黑树的高度问题

Question

老师， 视频里面说红黑树的最大高度是2logn n是红黑树的结点数， 我咋感觉n应该是2-3树的结点数， 或者说是红黑树黑结点的数目呢

Answer 1

liuyubobobo 2019-09-14 05:18:51

如果 n 是 黑节点数，那么红黑树高度肯定超不过 2logn，没有问题。

但如果 n 是红黑树节点总数的话，红黑树的高度存在一个上界，这个上界严格来说，是2log2(n + 1)。

具体证明可以参考这里：https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/

继续加油！：）

• 提问者 IT_god #1

  非常感谢！

• BYMS #2

  老师您好，请问为什么BST的高度是logn，而红黑树的高度是2logn？

• liuyubobobo 回复 BYMS #3

  首先；BST 的高度不是 logn 的，BST 的高度可能退化为 n，所以才有平衡二叉树的概念。一个绝对平衡的二叉树，高度是 logn 级别的。这一点我在讲堆的时候应该推导过。高度为 1 的树最多有 1 个节点 = 2^1 - 1；高度为 2 的树最多有 3 个节点 = 2^2 - 1；高度为 3 的树最多有 7 个节点 = 2^3 - 1；以此类推。高度和节点数量之间是 log 的关系。红黑树的黑节点满足平衡，所以黑节点的高度是 logn 级别的。每个黑节点下面可以再有一个红节点，所以整体式 2logn 的。当然，从复杂度的角度，O(2logn) 就是 O(logn)。继续加油：）

点开查看后面1条评论