红黑树(RBTree)原理及实现
红黑树(RBTree)原理
红黑树(RBTree)
当平衡二叉树(AVL树)中插入或删除节点后,使得高度之差大于1。为了让它重新维持在一个平衡状态,就需要对其进行旋转处理。为了降低旋转成本,提出了红黑树的数据结构。
红黑树是一种自平衡二叉查找树,它在每个节点增加了一个存储位记录节点的颜色,可以是RED,也可以是BLACK;通过任意一条从根到叶子简单路径上颜色的约束,红黑树保证最长路径不超过最短路径的二倍,因而近似平衡。
红黑树的特性:
- 每个节点颜色不是黑色,就是红色
- 根节点是黑色的
- 如果一个节点是红色,那么它的两个子节点就是黑色的(没有连续的红节点)
- 对于每个节点,从该节点到其后代叶节点的简单路径上,均包含相同数目的黑色节点
红黑树基本操作
红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后,都会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的结点之后,红黑树的结构就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转和变色,可以使这颗树重新成为红黑树。简单点说,旋转和变色的目的是让树保持红黑树的特性:自平衡二叉树。
旋转包括两种:左旋 和 右旋。下面分别对它们进行介绍:
左旋:以某个结点作为支点(旋转结点),其右子结点变为旋转结点的父结点,右子结点的左子结点变为旋转结点的右子结点,其左子结点保持不变。如图2。
右旋:以某个结点作为支点(旋转结点),其左子结点变为旋转结点的父结点,左子结点的右子结点变为旋转结点的左子结点,其右子结点保持不变。如图3。
变色:结点的颜色由红变黑或由黑变红。
图2(左旋图)
图3(右旋图)