红黑树 研究

数据结构

定义

也是一种平衡树，经常用来代替AVL树。红黑树的时间代价同样是$O(log(n))$

是一种比AVL树平衡性还要差的树

特点（性质）

1、每个结点被染成红色或黑色
2、根节点是黑色的
3、如果一个节点的颜色是红色的，那么他的子节点一定是黑色的
4、从任何一个节点出发到空节点的路径上的黑结点的个数是相同的。

一些结论

1、根据性质四，红黑树对于黑结点而言是完全平衡的

2、根据性质三，每条路径上是不可能存在连续两个红色结点的，所以各条到空节点（叶子结点）的路径的最长路径是最短路径的1.5倍

3、如果一条到空节点的路上有H个黑结点，那么整棵树至少有$2^H - 1$个黑结点，之多有$2^{2H}-1$个节点

4、如果红黑树中有N个黑结点，那么红黑树的高至多为$2log(N+1)$

基本操作分析

插入操作

情况一：父节点的兄弟结点是黑色的

情况二：父节点的兄弟是红色的

删除操作

情况一：删除的结点是红色的

情况二：删除的结点只有一个儿子

情况三：删除一个黑色的叶子结点

代码实现

参考链接

https://www.cnblogs.com/skywang12345/p/3624177.html