红黑树的平衡操作是通过旋转操作来实现的,分为左旋和右旋:
Y为根结点,A为Y的右孩子,以Y-A为轴进行左旋,A为新的根结点,Y为A的左孩子,A原左孩子B为旋转后Y的右子,Y的左子和A的右子不变。
代码实现
Y为根结点,X为Y的左孩子,以Y-X为轴进行右旋,X为新的根结点,Y为X的右孩子,X原右孩子R为旋转后Y的左子,Y的右子和X的左子不变。
代码实现
红黑树的插入操作包括二叉搜索树的插入操作(左小右大)和红黑树平衡插入操作,平衡操作主要是为了让红黑树重新满足红黑树属性。而平衡插入操作是在固定几种情况的步骤下完成,所以,红黑树插入的时间复杂度仍为O(logn)。
插入操作
1、类似于二叉搜索树,按照左小右大原则,插入新元素
2、将新元素着成红色(根据红黑树的性质,着成红色,破坏的性质较少,可以更快调整平衡)
插入平衡操作
3、平衡新树
新树可能不满足红黑树的性质,需要进行插入平衡操作。那平衡操作面对的场景包括哪些呢,下面先分析一下:
3.1、插入结点为根
根据性质2,直接变为黑色;
3.2、插入结点的父结点为黑色
发现没有违反红黑树的性质,仍然是一颗红黑树;
3.3、插入结点的父结点为红色,父结点为祖父结点的左孩子
3.3.1、祖父结点的另一个子结点(右子)为红色
新结点是其父结点的左子或者右子,此时破坏了性质4,将父结点、叔结点的颜色着为黑色、祖父结点着为红色,就能使其祖父之下的子树满足红黑树,将其祖父结点作为新结点,继续判断祖父以上的红黑树是否满足红黑树;
3.3.2、祖父结点的另一个子结点(右子)为黑色,当前结点为是其父结点的左子结点
以祖父结点和父结点为轴,进行右旋转,然后将原父结点(旋转后仍然为父结点)着为黑色,原祖父结点(旋转后为父结点的右子)着为红色,如下图:
3.3.3、祖父结点的另一个子结点(右子)为黑色,当前结点为是其父结点的右子结点
以父结点与当前结点为轴,进行左旋转,发现变成3.3.2的情况。
3.4、插入结点的父结点为红色,父结点为祖父结点的右孩子(与3.3互为对称操作)
略
HashMap的红黑树插入平衡算法
删除
红黑树的删除操作同样需要两个步骤:二叉树的删除操作和删除平衡操作。
下面先分析一下二叉树删除结点的场景(理解继承结点的概念):
1.1、删除结点无子结点
1.2、删除结点只有一个子结点
1.3、删除结点存在两个子结点,在左子树或者右子树中找到继承结点
继承结点其实就是替换删除结点的位置,也就是比删除结点的左子树中的结点大,比删除结点的右子树中的结点小,所以在左子树中找最大值,或者在右子树中找最小值。(注:无论找哪个子树都可以满足情况,本文参考《算法导论-第三版》,所以也找左子树中的最大值)
如果在左子树中找的话,一定是找其左子的右子,直到找不到右子,这个值为左子树中最大值;如果在右子树中找的话,一定是找其右子的左子,直到找不到左子,这个值为右子树中的最小值。
继承结点移动到删除结点位置,继承结点的子(一定只有一个子)为继承结点父结点的子。
《算法导论-第三版》找继承结点的代码实现
寻找左子树中的继承结点:
寻找右子树中的继承结点:
下面分析一下红黑树删除结点的场景(相比于二叉树,增加红黑树的属性,需要考虑颜色的平衡性):
2.1、删除结点无子结点(只有叶结点-Nil结点)
如果结点是红色,直接删除即可,将删除结点的一个叶结点(Nil结点)继承删除结点,此叶结点实际颜色应为黑-红色(红色继承自删除结点),此时直接去掉红色,仍然满足红黑树;
如果结点是黑色,将删除结点的一个叶结点(Nil结点)继承删除结点,此叶结点实际颜色应为黑-黑色,需要进行平衡操作;
2.2、删除结点有一个子结点
此时删除结点只能是黑色,并且删除结点的子结点(唯一继承结点)只能是红色,此时继承结点为红-黑色,需进行平衡操作;
2.3、删除结点有两个子结点
2.3.1、先找到继承结点;
2.3.2、继承结点继承删除结点;
2.3.3、类似于删除继承结点操作,即找继承结点的继承结点(注:此操作只会进行一层,因为继承结点只能包含一个子或者两个叶子,所以2.3退化成2.1、2.2的情况)
《算法导论-第三版》删除结点的代码实现
继承操作
下面分析一下平衡删除的场景:
3.1、平衡结点是树的根结点
根据性质2,直接着为黑色,满足红黑树性质;
3.2、平衡结点是红色(红-黑),2.2情况之后
直接将其着为黑色,满足红黑树性质;
3.3、平衡结点为黑色(黑-黑的叶节点-Nil结点),平衡结点为其父结点的左子,2.1情况之后
3.3.1、平衡结点为黑-黑,兄弟结点为红色
3.3.2、平衡结点为黑-黑,兄弟结点为黑色,包含两个叶结点
3.3.3、平衡结点为黑-黑,兄弟结点为黑色,包含一个左子为红色,右子为叶结点
3.3.4、平衡结点为黑-黑,兄弟结点为黑色,包含一个右子为红色,左子为叶结点或为叶结点
3.4、平衡结点为黑色(黑-黑的叶节点-Nil结点),平衡结点为其父结点的右子,2.1情况之后(与3.3互为对称的操作)
略
情况3.3.1 和 3.3.4
情况3.3.2和3.3.3
《算法导论-第三版》找删除平衡的代码实现
HashMap的红黑树删除平衡算法