本文共 10717 字，大约阅读时间需要 35 分钟。

红黑二叉查找树构造与操作

（黄毅然的半月更！）

以下为定义节点类以及各个操作的算法

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;//构造节点结构类型为RBTNode 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 RBTNode
                       
                         iterativeSearch(RBTNode
                        
                          x, T key) { //非递归实现查找"红黑树"中键值为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); } private RBTNode
                          
                            minimum(RBTNode
                           
                             tree) { if (tree == null) return null; while(tree.left != null)//查找最小结点：返回tree为根结点的红黑树的最小结点。 tree = tree.left; return tree; } public T minimum() { RBTNode
                            
                              p = minimum(mRoot); if (p != null) return p.key; return null; } private RBTNode
                             
                               maximum(RBTNode
                              
                                tree) { //查找最大结点：返回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; } public RBTNode
                                
                                  successor(RBTNode
                                 
                                   x) { //找结点(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; } public RBTNode
                                   
                                     predecessor(RBTNode
                                    
                                      x) { //找结点(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)进行左旋转 // 设置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; } 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);// 将根节点设为黑色 } 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); } public void insert(T key) { //新建结点(key)，并将其插入到红黑树中 RBTNode
                                                   
                                                     node=new RBTNode
                                                    
                                                     (key,BLACK,null,null,null); // 如果新建结点失败，则返回。 if (node != null) insert(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); } private void remove(RBTNode
                                                        
                                                          node) { //删除结点(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; } public void remove(T key) { //删除结点(z)，并返回被删除的结点 RBTNode
                                                           
                                                             node; if ((node = iterativeSearch(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); }
                                                             
                                                            
                                                           
                                                          
                                                         
                                                        
                                                       
                                                      
                                                     
                                                    
                                                   
                                                  
                                                 
                                                
                                               
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

以下为主函数：

import java.util.Scanner;public class RBTreeTest {       private static final int a[] = {   10, 20, 30, 40, 50, 60, 70, 80, 90};    public static void main(String[] args) {           int i, ilen = a.length;        RBTree
   
     tree=new RBTree
    
     ();                System.out.printf("== 原始数据: ");        for(i=0; i
    
   

本次代码参考了《算法导论》，仅供个人以及火汁们学习