3. 红-黑树的操作
红-黑树的基本操作是添加、删除和旋转。对红-黑树进行添加或删除后，可能会破坏其平衡性，会用到哪种旋转方式去修正呢？我们首先对红-黑树的节点做一介绍，然后分别对左旋和右旋的具体实现做一分析，最后我们探讨下红-黑树的具体操作。
3.1 红-黑树的节点
红-黑树是对二叉搜索树的改进，所以其节点与二叉搜索树是差不多的，只不过在它基础上增加了一个boolean型变量来表示节点的颜色，具体看RBNode类：
public class RBNode<T extends Comparable<T>>{ boolean color; //颜色 T key; //关键字(键值) RBNode<T> left; //左子节点 RBNode<T> right; //右子节点 RBNode<T> parent; //父节点 public RBNode(T key, boolean color, RBNode<T> parent, RBNode<T> left, RBNode<T> right) { this.key = key; this.color = color; this.parent = parent; this.left = left; this.right = right; } public T getKey() { return key; } public String toString() { return "" + key + (this.color == RED? "R" : "B"); } }
3.2 左旋的具体实现
上面对左旋的概念已经有了感性的认识了，这里就不再赘述了，我们从下面的代码中结合上面的示意图，探讨一下左旋的具体实现：
/*************对红黑树节点x进行左旋操作 ******************/ /* * 左旋示意图：对节点x进行左旋 * p p * / / * x y * / \ / \ * lx y -----> x ry * / \ / \ * ly ry lx ly * 左旋做了三件事： * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时) * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) * 3. 将y的左子节点设为x，将x的父节点设为y */ private void leftRotate(RBNode<T> x) { //1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时) RBNode<T> y = x.right; x.right = y.left; if(y.left != null) y.left.parent = x; //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) y.parent = x.parent; if(x.parent == null) { this.root = y; //如果x的父节点为空，则将y设为父节点 } else { if(x == x.parent.left) //如果x是左子节点 x.parent.left = y; //则也将y设为左子节点 else x.parent.right = y;//否则将y设为右子节点 } //3. 将y的左子节点设为x，将x的父节点设为y y.left = x; x.parent = y; }
3.3 右旋具体实现
上面对右旋的概念已经有了感性的认识了，这里也不再赘述了，我们从下面的代码中结合上面的示意图，探讨一下右旋的具体实现：
/*************对红黑树节点y进行右旋操作 ******************/ /* * 左旋示意图：对节点y进行右旋 * p p * / / * y x * / \ / \ * x ry -----> lx y * / \ / \ * lx rx rx ry * 右旋做了三件事： * 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时) * 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右) * 3. 将x的右子节点设为y，将y的父节点设为x */ private void rightRotate(RBNode<T> y) { //1. 将y的左子节点赋给x的右子节点，并将x赋给y左子节点的父节点(y左子节点非空时) RBNode<T> x = y.left; y.left = x.right; if(x.right != null) x.right.parent = y; //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右) x.parent = y.parent; if(y.parent == null) { this.root = x; //如果x的父节点为空，则将y设为父节点 } else { if(y == y.parent.right) //如果x是左子节点 y.parent.right = x; //则也将y设为左子节点 else y.parent.left = x;//否则将y设为右子节点 } //3. 将y的左子节点设为x，将x的父节点设为y x.right = y; y.parent = x; }
3.4 插入操作
分析完了红-黑树中主要的旋转操作，接下来我们开始分析常见的插入、删除等操作了。这里先分析插入操作。 由于红-黑树是二叉搜索树的改进，所以插入操作的前半工作时相同的，即先找到待插入的位置，再将节点插入，先来看看插入的前半段代码：
/*********************** 向红黑树中插入节点 **********************/ public void insert(T key) { RBNode<T> node = new RBNode<T>(key, RED, null, null, null); if(node != null) insert(node); } //将节点插入到红黑树中，这个过程与二叉搜索树是一样的 private void insert(RBNode<T> node) { RBNode<T> current = null; //表示最后node的父节点 RBNode<T> x = this.root; //用来向下搜索用的 //1. 找到插入的位置 while(x != null) { current = x; int cmp = node.key.compareTo(x.key); if(cmp < 0) x = x.left; else x = x.right; } node.parent = current; //找到了位置，将当前current作为node的父节点 //2. 接下来判断node是插在左子节点还是右子节点 if(current != null) { int cmp = node.key.compareTo(current.key); if(cmp < 0) current.left = node; else current.right = node; } else { this.root = node; } //3. 将它重新修整为一颗红黑树 insertFixUp(node); }
这与二叉搜索树中实现的思路一模一样，这里不再赘述，主要看看方法里面最后一步insertFixUp操作。因为插入后可能会导致树的不平衡，insertFixUp方法里主要是分情况讨论，分析何时变色，何时左旋，何时右旋。我们先从理论上分析具体的情况，然后再看insertFixUp方法的具体实现。
如果是第一次插入，由于原树为空，所以只会违反红-黑树的规则2，所以只要把根节点涂黑即可；如果插入节点的父节点是黑色的，那不会违背红-黑树的规则，什么也不需要做；但是遇到如下三种情况时，我们就要开始变色和旋转了：
- 1.插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的；
- 2.插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点；
- 3.插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。
下面我们先挨个分析这三种情况都需要如何操作，然后再给出实现代码。
对于情况1：插入节点的父节点和其叔叔节点（祖父节点的另一个子节点）均为红色的。此时，肯定存在祖父节点，但是不知道父节点是其左子节点还是右子节点，但是由于对称性，我们只要讨论出一边的情况，另一种情况自然也与之对应。这里考虑父节点是祖父节点的左子节点的情况，如下左图所示：
于这种情况，我们要做的操作有：将当前节点(4)的父节点(5)和叔叔节点(8)涂黑，将祖父节点(7)涂红，变成上右图所示的情况。再将当前节点指向其祖父节点，再次从新的当前节点开始算法（具体等下看下面的程序）。这样上右图就变成了情况2了。
对于情况2：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的右子节点。我们要做的操作有：将当前节点(7)的父节点(2)作为新的节点，以新的当前节点为支点做左旋操作。完成后如左下图所示，这样左下图就变成情况3了。
于情况3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是其父节点的左子节点。我们要做的操作有：将当前节点的父节点(7)涂黑，将祖父节点(11)涂红，在祖父节点为支点做右旋操作。最后把根节点涂黑，整个红-黑树重新恢复了平衡，如右上图所示。至此，插入操作完成！
我们可以看出，如果是从情况1开始发生的，必然会走完情况2和3，也就是说这是一整个流程，当然咯，实际中可能不一定会从情况1发生，如果从情况2开始发生，那再走个情况3即可完成调整，如果直接只要调整情况3，那么前两种情况均不需要调整了。故变色和旋转之间的先后关系可以表示为：变色->左旋->右旋。
至此，我们完成了全部的插入操作。下面我们看看insertFixUp方法中的具体实现（可以结合上面的分析图，更加利与理解）：
private void insertFixUp(RBNode<T> node) { RBNode<T> parent, gparent; //定义父节点和祖父节点 //需要修整的条件：父节点存在，且父节点的颜色是红色 while(((parent = parentOf(node)) != null) && isRed(parent)) { gparent = parentOf(parent);//获得祖父节点 //若父节点是祖父节点的左子节点，下面else与其相反 if(parent == gparent.left) { RBNode<T> uncle = gparent.right; //获得叔叔节点 //case1: 叔叔节点也是红色 if(uncle != null && isRed(uncle)) { setBlack(parent); //把父节点和叔叔节点涂黑 setBlack(uncle); setRed(gparent); //把祖父节点涂红 node = gparent; //将位置放到祖父节点处 continue; //继续while，重新判断 } //case2: 叔叔节点是黑色，且当前节点是右子节点 if(node == parent.right) { leftRotate(parent); //从父节点处左旋 RBNode<T> tmp = parent; //然后将父节点和自己调换一下，为下面右旋做准备 parent = node; node = tmp; } //case3: 叔叔节点是黑色，且当前节点是左子节点 setBlack(parent); setRed(gparent); rightRotate(gparent); } else { //若父节点是祖父节点的右子节点,与上面的完全相反，本质一样的 RBNode<T> uncle = gparent.left; //case1: 叔叔节点也是红色 if(uncle != null & isRed(uncle)) { setBlack(parent); setBlack(uncle); setRed(gparent); node = gparent; continue; } //case2: 叔叔节点是黑色的，且当前节点是左子节点 if(node == parent.left) { rightRotate(parent); RBNode<T> tmp = parent; parent = node; node = tmp; } //case3: 叔叔节点是黑色的，且当前节点是右子节点 setBlack(parent); setRed(gparent); leftRotate(gparent); } } //将根节点设置为黑色 setBlack(this.root); }
