后面阅读源码会涉及到红黑树,查阅资料发现本文不错
红黑树是特殊的二叉查找树,又名R-B树(RED-BLACK-TREE),由于红黑树是特殊的二叉查找树,即红黑树具有了二叉查找树的特性,而且红黑树还具有以下特性:
有几点需要注意的是:
首先红黑树在插入节点的时,我们设定插入节点的颜色为红色,如果插入的是黑色节点,必然会违背特性5,即改变了红黑树的黑高度,如下插入红色结点又存在着几种情况:
如图所示,这种情况不会破坏红黑树的特性,即不需要任何处理
当其父亲为红色时又会存在以下的情况
红叔的情况,其实相对来说比较简单的,如下图所示,只需要通过修改父、叔的颜色为黑色,祖的颜色为红色,而且回去递归的检查祖节点即可
黑叔 黑叔的情况有如下几种,这几种情况下是不能够通过修改颜色达到平衡的效果,因此会通过旋转的操作,红黑树种有两种旋转操作,左旋和右旋(现在存在的疑问,什么时候使用到左旋,什么时候使用到右旋)
Case 1:[先右旋,在改变颜色(根节点必须为黑色,其两个子节点为红色,叔节点不用改变)],如下图所示,注意省略黑哨兵节点
Case 2:[先左旋变成Case1中的情况,再右旋,最后改变颜色(根节点必须为黑色,其两个子节点为红色,叔节点不用改变)],如下图所示,注意省略黑哨兵节点
Case 3:[先左旋,最后改变颜色(根节点必须为黑色,其两个子节点为红色,叔节点不用改变)],如下图所示,注意省略黑哨兵节点
Case 4:[先右旋变成Case 3的情况,再左旋,最后改变颜色(根节点必须为黑色,其两个子节点为红色,叔节点不用改变)],如下图所示,注意省略黑哨兵节点
以上就是红黑树新增节点所有可能的操作,下面会介绍红黑树中的删除操作
2.1.2 删除操作 删除操作相比于插入操作情况更加复杂,删除一个节点可以大致分为三种情况:
1.删除的节点没有孩子节点,即当前节点为叶子节点,这种可以直接删除
2.删除的节点有一个孩子节点,这种需要删除当前节点,并使用其孩子节点顶替上来
3.删除的节点有两个孩子节点,这种需要先找到其后继节点(树中大于节点的最小的元素);然后将其后继节点的内容复制到该节点上,其后继节点就相当于该节点的替身, 需要注意的是其后继节点一定不会有两个孩子节点(这点应该很好理解,如果后继节点有左孩子节点,那么当前的后继节点肯定不是最小的,说明后继节点只能存在没有孩子节点或者只有一个右孩子节点),即这样就将问题转换成为1,2中的方式。
在讲述修复操作之前,首先需要明白几点,
1.对于红黑树而言,单支节点的情况只有如下图所示的一种情况,即为当前节点为黑色,其孩子节点为红色,(1.假设当前节点为红色,其两个孩子节点必须为黑色,2.若有孙子节点,则必为黑色,导致黑子数量不等,而红黑树不平衡)
2.由于红黑树是特殊的二叉查找树,它的删除和二叉查找树类型,真正的删除点即为删除点A的中序遍历的后继(前继也可以),通过红黑树的特性可知这个后继必然最多只能有一个孩子,其这个孩子节点必然是右孩子节点,从而为单支情况(即这个后继节点只能有一个红色孩子或没有孩子)
下面将详细介绍,在执行删除节点操作之后,将通过修复操作使得红黑树达到平衡的情况。
Case 1:被删除的节点为红色,则这节点必定为叶子节点(首先这里的被删除的节点指的是真正删除的节点,通过上文得知的真正删除的节点要么是节点本身,要么是其后继节点,若是节点本身则必须为叶子节点,不为叶子节点的话其会有左右孩子,则真正删除的是其右孩子树上的最小值,若是后继节点,也必须为叶子节点,若不是则其也会有左右孩子,从而和2中相违背),这种情况下删除红色叶节点就可以了,不用进行其他的操作了。
Case 2:被删除的节点是黑色,其子节点是红色,将其子节点顶替上来并改变其颜色为黑色,如下图所示
Case 3:被删除的节点是黑色,其子节点也是黑色,将其子节点顶替上来,变成了双黑的问题,此时有以下情况
从图中可以看出,操作之后红黑树并未达到平衡状态,而是变成的黑兄的情况
Case 2:新节点的兄弟节点为黑色,此时可能有如下情况
红父二黑侄:将父节点变成黑色,兄弟节点变成红色,新节点变成黑色即可,如下图所示
黑父二黑侄:将父节点变成新节点的颜色,新节点变成黑色,兄弟节点染成红色,还需要继续以父节点为判定点继续判断,如下图所示
红侄:情况一:新节点在右子树,红侄在兄弟节点左子树,此时的操作为右旋,并将兄弟节点变为父亲的颜色,父亲节点变为黑色,侄节点变为黑色,如下图所示
情况二:新节点在右子树,红侄在兄弟节点右子树,此时的操作为先左旋,后右旋并将侄节点变为父亲的颜色,父节点变为黑色,如下图所示
情况三:新节点在左子树,红侄在兄弟节点左子树,此时的操作为先右旋在左旋并将侄节点变为父亲的颜色,父亲节点变为黑色,如下图所示
情况四:新节点在右子树,红侄在兄弟节点右子树,此时的操作为左旋,并将兄弟节点变为父节点的颜色,父亲节点变为黑色,侄节点变为黑色,如下图所示
如下是使用JAVA代码实现红黑树的过程,主要包括了插入、删除、左旋、右旋、遍历等操作
private void insert(RBTreeNode<T> node){ int cmp; RBTreeNode<T> root = this.rootNode; RBTreeNode<T> parent = null;
while(null != root){ parent = root; cmp = node.key.compareTo(root.key); if (cmp < 0){ root = root.left; } else { root = root.right; } }
node.parent = parent;
if (null == parent){ this.rootNode = node; } else {
cmp = node.key.compareTo(parent.key); if (cmp < 0){ parent.left = node; } else { parent.right = node; } }
node.color = COLOR_RED;
insertFixUp(node);}
private void insertFixUp(RBTreeNode<T> node){ RBTreeNode<T> parent,gparent;
while( ((parent = getParent(node)) != null) && isRed(parent)){ gparent = getParent(parent);
if(parent == gparent.left){ RBTreeNode<T> uncle = gparent.right; if ((null != uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node = gparent; continue; }
if (parent.right == node){ RBTreeNode<T> tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; }
setColorBlack(parent); setColorRed(gparent); rightRotate(gparent); } else { RBTreeNode<T> uncle = gparent.left; if ((null != uncle) && isRed(uncle)){ setColorBlack(uncle); setColorBlack(parent); setColorRed(gparent); node = gparent; continue; }
if (parent.left == node){ RBTreeNode<T> tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; }
setColorBlack(parent); setColorRed(gparent); leftRotate(gparent); } } setColorBlack(this.rootNode);}
插入节点的操作主要分为以下几步:
如下为删除节点的代码
private void remove(RBTreeNode<T> node){ RBTreeNode<T> child,parent; boolean color;
if ((null != node.left) && (null != node.right)){
RBTreeNode<T> replace = node;
replace = replace.right; while(null != replace.left){ replace = replace.left; }
if (null != getParent(node)){
if (getParent(node).left == node){ getParent(node).left = replace; } else { getParent(node).right = replace; } } else { this.rootNode = replace; }
child = replace.right; parent = getParent(replace); color = getColor(replace);
if (parent == node){ parent = replace; } else { if (null != child){ setParent(child,parent); } parent.left = child;
replace.right = node.right; setParent(node.right, replace); }
replace.parent = node.parent; replace.color = node.color; replace.left = node.left; node.left.parent = replace; if (color == COLOR_BLACK){ removeFixUp(child,parent); }
node = null; return; }
if (null != node.left){ child = node.left; } else { child = node.right; }
parent = node.parent; color = node.color; if (null != child){ child.parent = parent; }
if (null != parent){ if (parent.left == node){ parent.left = child; } else { parent.right = child; } } else { this.rootNode = child; }
if (color == COLOR_BLACK){ removeFixUp(child, parent); } node = null;}
private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent){ RBTreeNode<T> other;
while ((null == node || isBlack(node)) && (node != this.rootNode) ){
if (node == parent.left){
other = parent.right;
if (isRed(other)){ setColorBlack(other); setColorRed(parent); leftRotate(parent); other = parent.right; }
if ((other.left == null || isBlack(other.left)) && (other.right == null || isBlack(other.right))){ setColorRed(other); node = parent; parent = getParent(node); } else {
if (null == other.right || isBlack(other.right)){ setColorBlack(other.left); setColorRed(other); rightRotate(other); other = parent.right; }
setColor(other, getColor(parent)); setColorBlack(parent); setColorBlack(other.right); leftRotate(parent); node = this.rootNode; break; } } else { other = parent.left; if (isRed(other)){ setColorBlack(other); setColorRed(parent); rightRotate(parent); other = parent.left; }
if ((null == other.left || isBlack(other.left)) && (null == other.right || isBlack(other.right))){ setColorRed(other); node = parent; parent = getParent(node); } else { if (null == other.left || isBlack(other.left)){ setColorBlack(other.right); setColorRed(other); leftRotate(other); other = parent.left; }
setColor(other,getColor(parent)); setColorBlack(parent); setColorBlack(other.left); rightRotate(parent); node = this.rootNode; break; } } } if (node!=null) setColorBlack(node);}
删除节点主要分为几种情况去做对应的处理:
以上主要介绍了红黑树的一些特性,包括一些操作详细的解析了里面的过程,写的时间比较长,感觉确实比较难理清楚。后面会持续的理解更深入,若有存在问题的地方,请指正,另红黑树实现代码
原文:遇见技术 https://www.jianshu.com/p/4cd37000f4e3