红黑树
本文共 24861 字，大约阅读时间需要 82 分钟。
红黑树原理
红黑树（Red-Black Tree，简称R-B Tree），它是一种特殊的二叉查找树。首先它满足二叉查找树的特征：任意结点结点包含的键值，大于左孩子的键值，小于右孩子的键值。
除此之外，红黑树的每个结点都有存储位来表示结点的颜色，不是红（Red）就是 黑（Black）。 红黑树的特性：
- 1.每个结点或是红色的，或是黑色的。
- 2.根结点是黑色的。
- 3.每个叶结点（NIL）是黑色的。（最后的叶结点就是空的，或者用一个哨兵替换掉所有的空结点）
- 4.如果一个结点是红色的，那么它的两个子结点都是黑色的。
- 5.对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
关于它的特性，需要注意：
第一，特性 3 中的叶子结点，是为空（NIL或null）的结点 第二，特性 5 ，确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。红黑树的图如下（直接借用算法导论中的图，其中浅色的为红色，深色的为黑色）：
红黑树的java代码实现
红黑树的基本操作是查找，选择，添加，删除。查找就省略了，和二叉树的查找区别不大。在添加和删除后，都会用到红黑树的旋转。因为修改红黑树之后，会破坏红黑树的性质，所以需要旋转满足这几条性质。
旋转包括两种：左旋和右旋1.基本定义
public class RBTree>{ private RBTNode mRoot; //根结点 private static final boolean RED = false; private static final boolean BLACK = true; public class RBTNode >{ boolean color; //颜色 T key; //关键字（键值） RBTNode left; //左孩子 RBTNode right; //右孩子 RBTNode parent; //父节点 public RBTNode(T key, boolean color, RBTNode parent, RBTNode left, RBTNode right) { this.key = key; this.color = color; this.parent = parent; this.left = left; this.right = right; } } ...}
说明：RBTree是红黑树对应的类，RBTNode是红黑树的结点类。在RBTree中包含了根节点mRoot和红黑树的相关API。
2.左旋
对x进行左旋，意味着将x变成一个左结点。
左旋代码
/* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)-. / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ private void leftRotate(RBTNodex){ //设置x的右孩子为y RBTNode y = x.right; //将 "y的左孩子" 设为 "x的右孩子" //如果y的左孩子非空，将 "x" 设为 "y的左孩子的父亲" x.right = y.left; if(y.left != null){ y.left.parent = x; } //将 "x的父亲" 设为 "y的父亲" y.parent = x.parent; if(x.parent == null){ this.mRoot = y; //如果 "x的父亲" 是空结点，则将y设为根结点 }else{ if(x.parent.left == x){ x.parent.left = y; //如果 x是它父节点的左孩子，则将y设置为 "x的父节点的左孩子" }else{ x.parent.right = y; //如果 x是它父节点的右孩子，则将y设置为 "x的父节点的右孩子" } } // 将 “x” 设为 “y的左孩子” y.left = x; // 将 “x的父节点” 设为 “y” x.parent = y; }
3.右旋
对y进行左旋，意味着"将y变成一个右节点"。
右旋代码：
/* * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： * py py * / / * y x * / \ --(右旋)-. / \ # * x ry lx y * / \ / \ # * lx rx rx ry * */private void rightRotate(RBTNodey) { // 设置x是当前节点的左孩子。 RBTNode x = y.left; // 将 “x的右孩子” 设为 “y的左孩子”； // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲” y.left = x.right; if (x.right != null) x.right.parent = y; // 将 “y的父亲” 设为 “x的父亲” x.parent = y.parent; if (y.parent == null) { this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点 } else { if (y == y.parent.right) y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子” else y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x.right = y; // 将 “y的父节点” 设为 “x” y.parent = x;}
4.添加
将结点插入红黑树时，首先将红黑树当作一棵二叉查找树，然后将结点插入；然后将结点着色为红色，再通过“旋转和重新着色”等操作修正该树，使其成为一棵红黑树。详细步骤如下：
第一步：将红黑树当作一棵二叉查找树，将结点插入（这个简单，不展开）。第二步：将插入的结点着色为“红色”
为什么着色为红色，而不是黑色？可以观测红黑树的5个特性，发现不会违背“特性（5）”，当然有可能违背其他特性，但只是可能，不一定会，所以遵循着违背的越少越好的原则，将插入的结点着色为红色。第三步：通过一系列的选择或者着色等操作，使其重新成为红黑树
第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？ 对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。 对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。 对于"特性(4)"，是有可能违背的！ 那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。添加操作的实现代码
/* * 将结点插入到红黑树中 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的node */private void insert(RBTNodenode) { int cmp; RBTNode y = null; RBTNode x = this.mRoot; // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。 while (x != null) { y = x; cmp = node.key.compareTo(x.key); if (cmp < 0) x = x.left; else x = x.right; } node.parent = y; if (y!=null) { cmp = node.key.compareTo(y.key); if (cmp < 0) y.left = node; else y.right = node; } else { this.mRoot = node; } // 2. 设置节点的颜色为红色 node.color = RED; // 3. 将它重新修正为一颗二叉查找树 insertFixUp(node);}/* * 新建结点(key)，并将其插入到红黑树中 * * 参数说明： * key 插入结点的键值 */public void insert(T key) { RBTNode node=new RBTNode (key,BLACK,null,null,null); // 如果新建结点失败，则返回。 if (node != null) insert(node);}
内部接口 -- insert(node)的作用是将"node"节点插入到红黑树中。
外部接口 -- insert(key)的作用是将"key"添加到红黑树中。添加修正操作的实现代码
/* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的z */private void insertFixUp(RBTNodenode) { RBTNode parent, gparent; // 若“父节点存在，并且父节点的颜色是红色” while (((parent = parentOf(node))!=null) && isRed(parent)) { gparent = parentOf(parent); //若“父节点”是“祖父节点的左孩子” if (parent == gparent.left) { // Case 1条件：叔叔节点是红色 RBTNode uncle = gparent.right; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是右孩子 if (parent.right == node) { RBTNode tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是左孩子。 setBlack(parent); setRed(gparent); rightRotate(gparent); } else { //若“z的父节点”是“z的祖父节点的右孩子” // Case 1条件：叔叔节点是红色 RBTNode uncle = gparent.left; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是左孩子 if (parent.left == node) { RBTNode tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是右孩子。 setBlack(parent); setRed(gparent); leftRotate(gparent); } } // 将根节点设为黑色 setBlack(this.mRoot);}
insertFixUp(node)的作用是对应"上面所讲的第三步"。它是一个内部接口。
5.删除操作
将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：
第一步：将红黑树当作一棵二叉查找树，将结点删除 这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况： ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。 ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。 ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。第二步：通过“旋转和重新着色”等一系列操作修正该树，使其重新成为一棵红黑树。
因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。/* * 删除结点(node)，并返回被删除的结点 * * 参数说明： * node 删除的结点 */private void remove(RBTNodenode) { RBTNode child, parent; boolean color; // 被删除节点的"左右孩子都不为空"的情况。 if ( (node.left!=null) && (node.right!=null) ) { // 被删节点的后继节点。(称为"取代节点") // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。 RBTNode replace = node; // 获取后继节点 replace = replace.right; while (replace.left != null) replace = replace.left; // "node节点"不是根节点(只有根节点不存在父节点) if (parentOf(node)!=null) { if (parentOf(node).left == node) parentOf(node).left = replace; else parentOf(node).right = replace; } else { // "node节点"是根节点，更新根节点。 this.mRoot = replace; } // child是"取代节点"的右孩子，也是需要"调整的节点"。 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。 child = replace.right; parent = parentOf(replace); // 保存"取代节点"的颜色 color = colorOf(replace); // "被删除节点"是"它的后继节点的父节点" if (parent == node) { parent = replace; } else { // child不为空 if (child!=null) 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 == BLACK) removeFixUp(child, parent); node = null; return ; } if (node.left !=null) { child = node.left; } else { child = node.right; } parent = node.parent; // 保存"取代节点"的颜色 color = node.color; if (child!=null) child.parent = parent; // "node节点"不是根节点 if (parent!=null) { if (parent.left == node) parent.left = child; else parent.right = child; } else { this.mRoot = child; } if (color == BLACK) removeFixUp(child, parent); node = null;}/* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * tree 红黑树的根结点 * z 删除的结点 */public void remove(T key) { RBTNode node; if ((node = search(mRoot, key)) != null) remove(node);}
内部接口 -- remove(node)的作用是将"node"节点插入到红黑树中。
外部接口 -- remove(key)删除红黑树中键值为key的节点。删除修正操作的实现代码
/* * 红黑树删除修正函数 * * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 待修正的节点 */private void removeFixUp(RBTNodenode, RBTNode parent) { RBTNode other; while ((node==null || isBlack(node)) && (node != this.mRoot)) { if (parent.left == node) { other = parent.right; if (isRed(other)) { // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); leftRotate(parent); other = parent.right; } if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))) { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else { if (other.right==null || isBlack(other.right)) { // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.left); setRed(other); rightRotate(other); other = parent.right; } // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.right); leftRotate(parent); node = this.mRoot; break; } } else { other = parent.left; if (isRed(other)) { // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); rightRotate(parent); other = parent.left; } if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))) { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else { if (other.left==null || isBlack(other.left)) { // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.right); setRed(other); leftRotate(other); other = parent.left; } // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.left); rightRotate(parent); node = this.mRoot; break; } } } if (node!=null) setBlack(node);}
removeFixup(node, parent)是对应"上面所讲的第三步"。它是一个内部接口。
红黑树的完整源码
下面是红黑树实现的完整代码和相应的测试程序。
(1) 除了上面所说的"左旋"、"右旋"、"添加"、"删除"等基本操作之后，还实现了"遍历"、"查找"、"打印"、"最小值"、"最大值"、"创建"、"销毁"等接口。 (2) 函数接口大多分为内部接口和外部接口。内部接口是private函数，外部接口则是public函数。 (3) 测试代码中提供了"插入"和"删除"动作的检测开关。默认是关闭的，打开方法可以参考"代码中的说明"。建议在打开开关后，在草稿上自己动手绘制一下红黑树。红黑树的实现文件(RBTree.java)
/** * Java 语言: 红黑树 * * @author skywang * @date 2013/11/07 */public class RBTree> { private RBTNode mRoot; // 根结点 private static final boolean RED = false; private static final boolean BLACK = true; public class RBTNode > { boolean color; // 颜色 T key; // 关键字(键值) RBTNode left; // 左孩子 RBTNode right; // 右孩子 RBTNode parent; // 父结点 public RBTNode(T key, boolean color, RBTNode parent, RBTNode left, RBTNode 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"); } } public RBTree() { mRoot=null; } private RBTNode parentOf(RBTNode node) { return node!=null ? node.parent : null; } private boolean colorOf(RBTNode node) { return node!=null ? node.color : BLACK; } private boolean isRed(RBTNode node) { return ((node!=null)&&(node.color==RED)) ? true : false; } private boolean isBlack(RBTNode node) { return !isRed(node); } private void setBlack(RBTNode node) { if (node!=null) node.color = BLACK; } private void setRed(RBTNode node) { if (node!=null) node.color = RED; } private void setParent(RBTNode node, RBTNode parent) { if (node!=null) node.parent = parent; } private void setColor(RBTNode node, boolean color) { if (node!=null) node.color = color; } /* * 前序遍历"红黑树" */ private void preOrder(RBTNode tree) { if(tree != null) { System.out.print(tree.key+" "); preOrder(tree.left); preOrder(tree.right); } } public void preOrder() { preOrder(mRoot); } /* * 中序遍历"红黑树" */ private void inOrder(RBTNode tree) { if(tree != null) { inOrder(tree.left); System.out.print(tree.key+" "); inOrder(tree.right); } } public void inOrder() { inOrder(mRoot); } /* * 后序遍历"红黑树" */ private void postOrder(RBTNode tree) { if(tree != null) { postOrder(tree.left); postOrder(tree.right); System.out.print(tree.key+" "); } } public void postOrder() { postOrder(mRoot); } /* * (递归实现)查找"红黑树x"中键值为key的节点 */ private RBTNode search(RBTNode x, T key) { if (x==null) return x; int cmp = key.compareTo(x.key); if (cmp < 0) return search(x.left, key); else if (cmp > 0) return search(x.right, key); else return x; } public RBTNode search(T key) { return search(mRoot, key); } /* * (非递归实现)查找"红黑树x"中键值为key的节点 */ private RBTNode iterativeSearch(RBTNode x, T key) { while (x!=null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else return x; } return x; } public RBTNode iterativeSearch(T key) { return iterativeSearch(mRoot, key); } /* * 查找最小结点：返回tree为根结点的红黑树的最小结点。 */ private RBTNode minimum(RBTNode tree) { if (tree == null) return null; while(tree.left != null) tree = tree.left; return tree; } public T minimum() { RBTNode p = minimum(mRoot); if (p != null) return p.key; return null; } /* * 查找最大结点：返回tree为根结点的红黑树的最大结点。 */ private RBTNode maximum(RBTNode tree) { if (tree == null) return null; while(tree.right != null) tree = tree.right; return tree; } public T maximum() { RBTNode p = maximum(mRoot); if (p != null) return p.key; return null; } /* * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。 */ public RBTNode successor(RBTNode x) { // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。 if (x.right != null) return minimum(x.right); // 如果x没有右孩子。则x有以下两种可能： // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 RBTNode y = x.parent; while ((y!=null) && (x==y.right)) { x = y; y = y.parent; } return y; } /* * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。 */ public RBTNode predecessor(RBTNode x) { // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。 if (x.left != null) return maximum(x.left); // 如果x没有左孩子。则x有以下两种可能： // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 RBTNode y = x.parent; while ((y!=null) && (x==y.left)) { x = y; y = y.parent; } return y; } /* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)-. / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ private void leftRotate(RBTNode x) { // 设置x的右孩子为y RBTNode y = x.right; // 将 “y的左孩子” 设为 “x的右孩子”； // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲” x.right = y.left; if (y.left != null) y.left.parent = x; // 将 “x的父亲” 设为 “y的父亲” y.parent = x.parent; if (x.parent == null) { this.mRoot = y; // 如果 “x的父亲” 是空节点，则将y设为根节点 } else { if (x.parent.left == x) x.parent.left = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” else x.parent.right = y; // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子” } // 将 “x” 设为 “y的左孩子” y.left = x; // 将 “x的父节点” 设为 “y” x.parent = y; } /* * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： * py py * / / * y x * / \ --(右旋)-. / \ # * x ry lx y * / \ / \ # * lx rx rx ry * */ private void rightRotate(RBTNode y) { // 设置x是当前节点的左孩子。 RBTNode x = y.left; // 将 “x的右孩子” 设为 “y的左孩子”； // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲” y.left = x.right; if (x.right != null) x.right.parent = y; // 将 “y的父亲” 设为 “x的父亲” x.parent = y.parent; if (y.parent == null) { this.mRoot = x; // 如果 “y的父亲” 是空节点，则将x设为根节点 } else { if (y == y.parent.right) y.parent.right = x; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子” else y.parent.left = x; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子” } // 将 “y” 设为 “x的右孩子” x.right = y; // 将 “y的父节点” 设为 “x” y.parent = x; } /* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的z */ private void insertFixUp(RBTNode node) { RBTNode parent, gparent; // 若“父节点存在，并且父节点的颜色是红色” while (((parent = parentOf(node))!=null) && isRed(parent)) { gparent = parentOf(parent); //若“父节点”是“祖父节点的左孩子” if (parent == gparent.left) { // Case 1条件：叔叔节点是红色 RBTNode uncle = gparent.right; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是右孩子 if (parent.right == node) { RBTNode tmp; leftRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是左孩子。 setBlack(parent); setRed(gparent); rightRotate(gparent); } else { //若“z的父节点”是“z的祖父节点的右孩子” // Case 1条件：叔叔节点是红色 RBTNode uncle = gparent.left; if ((uncle!=null) && isRed(uncle)) { setBlack(uncle); setBlack(parent); setRed(gparent); node = gparent; continue; } // Case 2条件：叔叔是黑色，且当前节点是左孩子 if (parent.left == node) { RBTNode tmp; rightRotate(parent); tmp = parent; parent = node; node = tmp; } // Case 3条件：叔叔是黑色，且当前节点是右孩子。 setBlack(parent); setRed(gparent); leftRotate(gparent); } } // 将根节点设为黑色 setBlack(this.mRoot); } /* * 将结点插入到红黑树中 * * 参数说明： * node 插入的结点 // 对应《算法导论》中的node */ private void insert(RBTNode node) { int cmp; RBTNode y = null; RBTNode x = this.mRoot; // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。 while (x != null) { y = x; cmp = node.key.compareTo(x.key); if (cmp < 0) x = x.left; else x = x.right; } node.parent = y; if (y!=null) { cmp = node.key.compareTo(y.key); if (cmp < 0) y.left = node; else y.right = node; } else { this.mRoot = node; } // 2. 设置节点的颜色为红色 node.color = RED; // 3. 将它重新修正为一颗二叉查找树 insertFixUp(node); } /* * 新建结点(key)，并将其插入到红黑树中 * * 参数说明： * key 插入结点的键值 */ public void insert(T key) { RBTNode node=new RBTNode (key,BLACK,null,null,null); // 如果新建结点失败，则返回。 if (node != null) insert(node); } /* * 红黑树删除修正函数 * * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： * node 待修正的节点 */ private void removeFixUp(RBTNode node, RBTNode parent) { RBTNode other; while ((node==null || isBlack(node)) && (node != this.mRoot)) { if (parent.left == node) { other = parent.right; if (isRed(other)) { // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); leftRotate(parent); other = parent.right; } if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))) { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else { if (other.right==null || isBlack(other.right)) { // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.left); setRed(other); rightRotate(other); other = parent.right; } // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.right); leftRotate(parent); node = this.mRoot; break; } } else { other = parent.left; if (isRed(other)) { // Case 1: x的兄弟w是红色的 setBlack(other); setRed(parent); rightRotate(parent); other = parent.left; } if ((other.left==null || isBlack(other.left)) && (other.right==null || isBlack(other.right))) { // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的 setRed(other); node = parent; parent = parentOf(node); } else { if (other.left==null || isBlack(other.left)) { // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。 setBlack(other.right); setRed(other); leftRotate(other); other = parent.left; } // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。 setColor(other, colorOf(parent)); setBlack(parent); setBlack(other.left); rightRotate(parent); node = this.mRoot; break; } } } if (node!=null) setBlack(node); } /* * 删除结点(node)，并返回被删除的结点 * * 参数说明： * node 删除的结点 */ private void remove(RBTNode node) { RBTNode child, parent; boolean color; // 被删除节点的"左右孩子都不为空"的情况。 if ( (node.left!=null) && (node.right!=null) ) { // 被删节点的后继节点。(称为"取代节点") // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。 RBTNode replace = node; // 获取后继节点 replace = replace.right; while (replace.left != null) replace = replace.left; // "node节点"不是根节点(只有根节点不存在父节点) if (parentOf(node)!=null) { if (parentOf(node).left == node) parentOf(node).left = replace; else parentOf(node).right = replace; } else { // "node节点"是根节点，更新根节点。 this.mRoot = replace; } // child是"取代节点"的右孩子，也是需要"调整的节点"。 // "取代节点"肯定不存在左孩子！因为它是一个后继节点。 child = replace.right; parent = parentOf(replace); // 保存"取代节点"的颜色 color = colorOf(replace); // "被删除节点"是"它的后继节点的父节点" if (parent == node) { parent = replace; } else { // child不为空 if (child!=null) 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 == BLACK) removeFixUp(child, parent); node = null; return ; } if (node.left !=null) { child = node.left; } else { child = node.right; } parent = node.parent; // 保存"取代节点"的颜色 color = node.color; if (child!=null) child.parent = parent; // "node节点"不是根节点 if (parent!=null) { if (parent.left == node) parent.left = child; else parent.right = child; } else { this.mRoot = child; } if (color == BLACK) removeFixUp(child, parent); node = null; } /* * 删除结点(z)，并返回被删除的结点 * * 参数说明： * tree 红黑树的根结点 * z 删除的结点 */ public void remove(T key) { RBTNode node; if ((node = search(mRoot, key)) != null) remove(node); } /* * 销毁红黑树 */ private void destroy(RBTNode tree) { if (tree==null) return ; if (tree.left != null) destroy(tree.left); if (tree.right != null) destroy(tree.right); tree=null; } public void clear() { destroy(mRoot); mRoot = null; } /* * 打印"红黑树" * * key -- 节点的键值 * direction -- 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */ private void print(RBTNode tree, T key, int direction) { if(tree != null) { if(direction==0) // tree是根节点 System.out.printf("%2d(B) is root\n", tree.key); else // tree是分支节点 System.out.printf("%2d(%s) is %2d's %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left"); print(tree.left, tree.key, -1); print(tree.right,tree.key, 1); } } public void print() { if (mRoot != null) print(mRoot, mRoot.key, 0); }}
红黑树的测试文件(RBTreeTest.java)
/** * Java 语言: 二叉查找树 * * @author skywang * @date 2013/11/07 */public class RBTreeTest { private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80}; private static final boolean mDebugInsert = false; // "插入"动作的检测开关(false，关闭；true，打开) private static final boolean mDebugDelete = false; // "删除"动作的检测开关(false，关闭；true，打开) public static void main(String[] args) { int i, ilen = a.length; RBTree tree=new RBTree (); System.out.printf("== 原始数据: "); for(i=0; i 参考资料
真的很感谢这位博主的解析，让我等也能窥探红黑树的代码魅力。
1.转载地址：http://pnezo.baihongyu.com/
你可能感兴趣的文章
AKM项目轶事之GBS同事转入GDC
查看>>
MySQL日期 专题
查看>>
C#中禁止程序多开
查看>>
分布式缓存Redis使用以及原理
查看>>
[LeetCode] Number of 1 Bits 位操作
查看>>
数据结构与算法JavaScript描述——队列
查看>>
练习二：结对练习
查看>>
JSON中JObject和JArray,JValue序列化(Linq)
查看>>
onclick与addEventListener的区别
查看>>
杂七杂八
查看>>
samba、nginx服务
查看>>
Activity竟然有两个onCreate方法，可别用错了
查看>>
Linux经常使用命令(十六) - whereis
查看>>
Tomcat
查看>>
插件编译 版本问题
查看>>
android中TextView的阴影设置
查看>>
core dump相关
查看>>
MySQL如何导出带日期格式的文件
查看>>
Linux五种IO模型
查看>>
Bootstrap技术: 模式对话框的使用
查看>>