文章目录
- 关于黑高的结论
- 红黑树的插入
平衡二叉树 AVL:插入/删除 很容易破坏“平衡”特性，需要频繁调整树的形态。如:插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树(时间开销大)，再进行 LL/RR/LR/RL 调整
红黑树 RBT:插入/刚除 很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成
平衡二叉树:适用于以查为主、很少插入/删除的场景
红黑树:适用于频繁插入、删除的场景，实用性更强
左根右，根叶黑
不红红，黑路同
性质1证明:任何一条查找失败路径上黑结点数量都相同，而路径上不能连续出现两个红结点，即红结点只能穿插在各个黑结点中间
性质2证明:若红黑树总高度=h，则根节点黑高>h/2，因此内部结点数 n ≥ 2 h / 2 − 1 n≥2^{h/2}-1 n≥2h/2−1，由此推出h≤ 2 l o g 2 ( n + 1 ) 2log_2(n+1) 2log2(n+1)
关于黑高的结论
最少的情况
结点的黑高bh–从某结点出发(不含该结点)到达任一叶结点的路径上黑结点总数
**思考:**根节点黑高为h的红黑树，内部结点数(关键字)至少有多少个?
**回答:**内部结点数最少的情况–总共h层黑结点的满树形态
**结论:**若根节点黑高为h，内部结点数(关键字)最少有 2 h − 1 2^h-1 2h−1个
最多的情况
结点的黑高bh–从某结点出发(不含该结点)到达任一叶结点的路径上黑结点总数
**思考:**根节点黑高为h的红黑树，内部结点数(关键字)至多有多少个?
**回答:**内部结点数最多的情况–h层黑结点，每一层黑结点下面都铺满一层红结点。共2h层的满树形态
**结论:**若根节点黑高为h，内部结点数(关键字)最多有 2 2 h − 1 2^{2h}-1 22h−1个
红黑树的插入
