红黑二叉树定义:满足一下性质的二叉树
- 根结点是黑色
- 父子节点不能同时为红节点
- 从x节点到叶子的任意路径黑节点数相同
- 所有叶子节点都是黑色
证明:由性质2 树高h<2bh ,
由性质3当来看当全部节点都是黑色时bh最大,又全部节点为n的完全二叉树高度为log(n+1),所以bh<log(n+1)
所以h<2log(n+1)