特征
红黑树有以下特征:
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- null结点默认是黑色, 因此每个叶子节点（指空(nil或null)的叶子节点！）是黑色。 : 个人理解,根据这个特征,插入节点时,每个结点都能找到叔叔结点
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
另外红黑树可以理解为是一个四阶的B树
还可以反推出一些特征
- 红色结点要么有两个黑色的nil结点,要么有两个黑色非空子结点. 要不然就违背了第五个特征
插入
插入的结点默认是红色的,这样的话,插入结束后,只有可能违背第四个原则,之后只要通过一些办法修正就可以了
- 按照二叉搜索树的插入方法进行插入
- 若插入的是根结点,插入结点变成黑色,插入结束
- 若插入后父结点是黑色的,没有违背红黑树的特征,插入结束
- 若插入后父结点是红色的, 此时祖父结点肯定是黑色的, 叔叔结点可能是黑色可能是红色
- 若叔叔结点是红色的
- 父结点和叔叔结点都变成黑色,祖父结点变成红色,
- 祖父结点的子结点们,都满足了红黑树的特征,以祖父结点作为插入结点,重新走插入结束的判断
- 若叔叔结点是黑色的,且当前结点是父结点的右结点
- 把父结点作为当前结点,之后左旋.
- 重新走插入结束的判断
- 这一步的目的是把当前结点变成父结点的左结点
- 若叔叔结点是红色的
- 若叔叔结点是黑色的,且当前结点是父结点的左结点
- 把父结点变成黑色,祖父结点变成红色
- 以祖父结点作为当前结点,然后右旋,
- 到这一步,就修复了违背红黑树第四个特征的问题,插入结束
删除
首先按照二叉搜索树的删除方法进行删除
删除的结点,要么是黑色结点,要么是有两个黑色的nil结点的红色结点.
- 如果删除的红色结点,并不会违背什么原则,直接结束
- 如果要删除的是黑色结点
- 要删除的结点是两个黑色的nil结点
1.兄弟结点是红色且删除的结点是左结点 (父结点是黑色)- 兄弟结点变成黑色,父结点变成红色,然后父结点左旋,
-
这样做的目的是,兄弟结点变成了黑色,
要删除D结点
要删除D结点
- 兄弟结点是红色且删除的结点是右结点(父结点是黑色)
- 兄弟结点变成黑色,父结点变成红色,然后父结点右旋,
- 这样做的目的是,兄弟结点变成了黑色,
- 节点是左结点,兄弟结点是黑色,且兄弟结点的右节点是红色结点(要么是红色结点,要么是黑色的nil结点,要不然在删除之前就不平衡了)
- 此时要删除结点若删除,则经过子节点（nil节点）的路径的黑色节点个数就会减1，
-
将兄弟结点的右结点变成黑色,父结点和兄弟结点换颜色,然后父结点左旋,
要删除D结点
要删除D结点
- 节点是右节点,兄弟节点是黑色,且兄弟结点的左结点是红色结点
- 将兄弟结点和左结点变成黑色,父结点和兄弟结点换颜色,父结点右旋
- 结点是左结点,兄弟结点是黑色,兄弟结点的左结点是红色
- 兄弟结点变成红色,兄弟结点的左结点变成黑色, 兄弟结点右旋
-
此时变成了第3种情况
要删除D结点
要删除D结点
- 节点是右节点,兄弟结点是黑色,兄弟结点的右节点是红色
- 兄弟结点变成红色,兄弟结点的右节点变成黑色,兄弟结点左旋
- 此时变成了第四种情况
- 不符合上述情况时,兄弟结点是黑色,兄弟结点的孩子,都是黑色的nil结点,父结点是红色,
-
将父亲节点改成黑色，将兄弟节点改成红色，
要删除D结点
-
- 父结点是黑色,兄弟结点是黑色,兄弟结点的孩子都是黑色的nil结点,父结点是黑色
- 兄弟结点变成红色,再以父结点作为删除结点,进行平衡操作
-
删除黑色的非叶节点
这种情况下,删除的黑色节点仅有左子树或者仅有右子树。且另一个结点肯定是有两个黑色的nil子结点的红色结点
直接让另一个子结点变为黑色,然后替换要删除的结点就行
删除D结点
删除D结点
- 要删除的结点是两个黑色的nil结点
