红黑树的高度问题
来源：13-4 红黑树的基本性质和复杂度分析
IT_god
2019-09-13
老师， 视频里面说红黑树的最大高度是2logn n是红黑树的结点数， 我咋感觉n应该是2-3树的结点数， 或者说是红黑树黑结点的数目呢
写回答
1回答
-
如果 n 是 黑节点数，那么红黑树高度肯定超不过 2logn，没有问题。
但如果 n 是红黑树节点总数的话，红黑树的高度存在一个上界，这个上界严格来说，是2log2(n + 1)。
具体证明可以参考这里：https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/
继续加油！：）
042021-01-26
相似问题