本文主要是介绍红黑树高度上限2log2(N+1)简洁证明【通俗易懂且正确！】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
首先阅读这篇文章 https://fanlv.fun/2018/08/12/binary-tree/
明白什么是满二叉树？什么是2-3树，红黑树如何转换成2-3树。
-
我们可以得知满二叉树节点n和高度h的关系。
n = 2 h − 1 n = 2^h-1 n=2h−1 -
根据2-3树的构造规则，可知2-3树是一个满树，若全为2-的节点，即为满二叉树
所以2-3树节点n和高度H的关系
1 2 ( 3 H − 1 ) ⩾ n ⩾ 2 H − 1 ⇒ H ⩽ log 2 ( n + 1 ) \frac{1}{2}(3^{H}-1 ) \geqslant n \geqslant 2^H-1\\ \Rightarrow H \leqslant \log_2 (n+1) 21(3H−1)⩾n⩾2H−1⇒H⩽log2(n+1) -
由红黑树转化为2-3树可知，2-3树的高度H==红黑树的高度hb
为什么？转化过程中，红连接展平，黑链接不动。始终不变的是黑连接，
红黑树的高度 h b ⩾ h 2 hb \geqslant \frac{h}{2} hb⩾2h
n ⩾ 2 H − 1 n ⩾ 2 h b − 1 ⩾ 2 h 2 − 1 h ⩽ 2 log 2 ( n + 1 ) n \geqslant 2^{H}-1\\ n \geqslant 2^{hb}-1 \geqslant 2^{\frac{h}{2}} -1\\ h \leqslant 2\log_2 ( n+1) n⩾2H−1n⩾2hb−1⩾22h−1h⩽2log2(n+1)
这篇关于红黑树高度上限2log2(N+1)简洁证明【通俗易懂且正确！】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
