java算法实现红黑树完整代码示例

import java.util.nosuchelementexception;
import java.util.scanner;
public class redblackbst<key extends="" key="">, value> {
  private static final boolean red = true;
  private static final boolean black = false;
  private node root; //root of the bst
  private class node {
    private key key;      //key
    private value val;     //associated data
    private node left, right;  //links to left and right subtrees
    private boolean color;   //color of parent link
    private int size;      //subtree count
    public node(key key, value val, boolean color, int size) {
      this.key = key;
      this.val = val;
      this.color = color;
      this.size = size;
    }
  }
  //is node x red?
  private boolean isred(node x) {
    if(x == null) {
      return false;
    }
    return x.color == red;
  }
  //number of node in subtree rooted at x; 0 if x is null
  private int size(node x) {
    if(x == null) {
      return 0;
    }
    return x.size;
  }  
  /**
   * return the number of key-value pairs in this symbol table
   * @return the number of key-value pairs in this symbol table
   */
  public int size() {
    return size(root);
  }
  /**
   * is this symbol table empty?
   * @return true if this symbol table is empty and false otherwise
   */
  public boolean isempty() {
    return root == null;
  }
  /**
   * return the value associated with the given key
   * @param key the key
   * @return the value associated with the given key if the key is in the symbol table, and null if it is not.
   */
  public value get(key key) {
    if(key == null) {
      throw new nullpointerexception("argument to get() is null");
    }
    return get(root, key);
  }
  //value associated with the given key in subtree rooted at x; null if no such key
  private value get(node x, 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.val;
      }        
    }
    return null;
  }
  /**
   * does this symbol table contain the given key?
   * @param key the key
   * @return true if this symbol table contains key and false otherwise
   */
  public boolean contains(key key) {
    return get(key) != null;
  }
  /***************************************************************************
  * red-black tree insertion.
  ***************************************************************************/
  /**
   * inserts the specified key-value pair into the symbol table, overwriting the old 
   * value with the new value if the symbol table already contains the specified key.
   * deletes the specified key (and its associated value) from this symbol table
   * if the specified value is null.
   *
   * @param key the key
   * @param val the value
   * @throws nullpointerexception if key is null
   */
  public void put(key key, value val) {
    if (key == null) {
      throw new nullpointerexception("first argument to put() is null");
    }
    if (val == null) {
      delete(key);
      return;
    }
    root = put(root, key, val);
    root.color = black;    
  }
  // insert the key-value pair in the subtree rooted at h
  private node put(node h, key key, value val) {
    if(h == null) {
      return new node(key, val, red, 1);
    }
    int cmp = key.compareto(h.key);
    if(cmp < 0) {
      h.left = put(h.left, key, val);
    }
    else if(cmp > 0) {
      h.right = put(h.right, key, val);
    }
    else {
      h.val = val;
    }
    if(isred(h.right) && !isred(h.left)) {
      h = rotateleft(h);
    }
    if(isred(h.left) && isred(h.left.left)) {
      h = rotateright(h);
    }
    if(isred(h.left) && isred(h.right)) {
      flipcolors(h);
    }
    h.size = size(h.left) + size(h.right) + 1;
    return h;
  }
  /***************************************************************************
  * red-black tree deletion.
  ***************************************************************************/
 
  /**
   * removes the smallest key and associated value from the symbol table.
   * @throws nosuchelementexception if the symbol table is empty
   */
  public void deletemin() {
    if (isempty()) {
      throw new nosuchelementexception("bst underflow");
    }
    // if both children of root are black, set root to red
    if (!isred(root.left) && !isred(root.right))
      root.color = red;
    root = deletemin(root);
    if (!isempty()) root.color = black;
    // assert check();
  }
  // delete the key-value pair with the minimum key rooted at h
  // delete the key-value pair with the minimum key rooted at h
  private node deletemin(node h) { 
    if (h.left == null){
      return null;
    }
    if (!isred(h.left) && !isred(h.left.left)) {
      h = moveredleft(h);
    }
    h.left = deletemin(h.left);
    return balance(h);
  }
  /**
   * removes the largest key and associated value from the symbol table.
   * @throws nosuchelementexception if the symbol table is empty
   */
  public void deletemax() {
    if (isempty()) {
      throw new nosuchelementexception("bst underflow");
    }
    // if both children of root are black, set root to red
    if (!isred(root.left) && !isred(root.right))
      root.color = red;
    root = deletemax(root);
    if (!isempty()) root.color = black;
    // assert check();
  }
  // delete the key-value pair with the maximum key rooted at h
  // delete the key-value pair with the maximum key rooted at h
  private node deletemax(node h) { 
      if (isred(h.left))
        h = rotateright(h);
      if (h.right == null)
        return null;
      if (!isred(h.right) && !isred(h.right.left))
        h = moveredright(h);
      h.right = deletemax(h.right);
      return balance(h);
    }
  /**
   * remove the specified key and its associated value from this symbol table   
   * (if the key is in this symbol table).  
   *
   * @param key the key
   * @throws nullpointerexception if key is null
   */
  public void delete(key key) {
    if (key == null) {
      throw new nullpointerexception("argument to delete() is null");
    }
    if (!contains(key)) {
      return;
    }
    //if both children of root are black, set root to red
    if(!isred(root.left) && !isred(root.right)) {
      root.color = red;
    }
    root = delete(root, key);
    if(!isempty()) {
      root.color = black;
    }
  }
  // delete the key-value pair with the given key rooted at h
  // delete the key-value pair with the given key rooted at h
  private node delete(node h, key key) {
    if(key.compareto(h.key) < 0) {
      if(!isred(h.left) && !isred(h.left.left)) {
        h = moveredleft(h);
      }
      h.left = delete(h.left, key);
    }
    else {
      if(isred(h.left)) {
        h = rotateright(h);
      }
      if (key.compareto(h.key) == 0 && (h.right == null)) {
        return null;
      }
      if (!isred(h.right) && !isred(h.right.left)) {
        h = moveredright(h);
      }
      if (key.compareto(h.key) == 0) {
        node x = min(h.right);
        h.key = x.key;
        h.val = x.val;
        h.right = deletemin(h.right);
      }
      else {
        h.right = delete(h.right, key);
      }
    }
    return balance(h);
  }
  /***************************************************************************
  * red-black tree helper functions.
  ***************************************************************************/
  // make a left-leaning link lean to the right
  // make a left-leaning link lean to the right
  private node rotateright(node h) {
    // assert (h != null) && isred(h.left);
    node x = h.left;
    h.left = x.right;
    x.right = h;
    x.color = x.right.color;
    x.right.color = red;
    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
  }
  // make a right-leaning link lean to the left
  // make a right-leaning link lean to the left
  private node rotateleft(node h) {
    // assert (h != null) && isred(h.right);
    node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = x.left.color;
    x.left.color = red;
    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
  }
  // flip the colors of a node and its two children
  // flip the colors of a node and its two children
  private void flipcolors(node h) {
    // h must have opposite color of its two children
    // assert (h != null) && (h.left != null) && (h.right != null);
    // assert (!isred(h) && isred(h.left) && isred(h.right))
    //  || (isred(h) && !isred(h.left) && !isred(h.right));
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
  }
  // assuming that h is red and both h.left and h.left.left
  // are black, make h.left or one of its children red.
  // assuming that h is red and both h.left and h.left.left
  // are black, make h.left or one of its children red.
  private node moveredleft(node h) {
    // assert (h != null);
    // assert isred(h) && !isred(h.left) && !isred(h.left.left);
    flipcolors(h);
    if (isred(h.right.left)) { 
      h.right = rotateright(h.right);
      h = rotateleft(h);
      flipcolors(h);
    }
    return h;
  }
  // assuming that h is red and both h.right and h.right.left
  // are black, make h.right or one of its children red.
  // assuming that h is red and both h.right and h.right.left
  // are black, make h.right or one of its children red.
  private node moveredright(node h) {
    // assert (h != null);
    // assert isred(h) && !isred(h.right) && !isred(h.right.left);
    flipcolors(h);
    if (isred(h.left.left)) { 
      h = rotateright(h);
      flipcolors(h);
    }
    return h;
  }
  // restore red-black tree invariant
  // restore red-black tree invariant
  private node balance(node h) {
    // assert (h != null);
    if (isred(h.right)) {
      h = rotateleft(h);
    }
    if (isred(h.left) && isred(h.left.left)) {
      h = rotateright(h);
    }
    if (isred(h.left) && isred(h.right)) {
      flipcolors(h);
    }
    h.size = size(h.left) + size(h.right) + 1;
    return h;
  }
  /***************************************************************************
   * utility functions.
   ***************************************************************************/
   /**
   * returns the height of the bst (for debugging).
   * @return the height of the bst (a 1-node tree has height 0)
   */
   public int height() {
     return height(root);
   }
   private int height(node x) {
     if (x == null) {
       return -1;
     }
     return 1 + math.max(height(x.left), height(x.right));
   }
  /***************************************************************************
   * ordered symbol table methods.
   ***************************************************************************/
   /**
   * returns the smallest key in the symbol table.
   * @return the smallest key in the symbol table
   * @throws nosuchelementexception if the symbol table is empty
   */
   public key min() {
     if (isempty()) {
       throw new nosuchelementexception("called min() with empty symbol table");
     }
     return min(root).key;
   } 
   // the smallest key in subtree rooted at x; null if no such key
   private node min(node x) { 
     // assert x != null;
     if (x.left == null) {
       return x; 
     }
     else {
       return min(x.left); 
     }
   } 
   /**
   * returns the largest key in the symbol table.
   * @return the largest key in the symbol table
   * @throws nosuchelementexception if the symbol table is empty
   */
   public key max() {
     if (isempty()) {
       throw new nosuchelementexception("called max() with empty symbol table");
     }
     return max(root).key;
   } 
   // the largest key in the subtree rooted at x; null if no such key
   private node max(node x) { 
     // assert x != null;
     if (x.right == null) {
       return x; 
     }
     else {
       return max(x.right);     
     }
   } 
   /**
   * returns the largest key in the symbol table less than or equal to key.
   * @param key the key
   * @return the largest key in the symbol table less than or equal to key
   * @throws nosuchelementexception if there is no such key
   * @throws nullpointerexception if key is null
   */
   public key floor(key key) {
     if (key == null) {
       throw new nullpointerexception("argument to floor() is null");
     }
     if (isempty()) {
       throw new nosuchelementexception("called floor() with empty symbol table");
     }
     node x = floor(root, key);
     if (x == null) {
       return null;     
     }
     else {
       return x.key;
     }
   }  
   // the largest key in the subtree rooted at x less than or equal to the given key
   private node floor(node x, key key) {
     if (x == null) {
       return null;
     }
     int cmp = key.compareto(x.key);
     if (cmp == 0) {
       return x;
     }
     if (cmp < 0) {
       return floor(x.left, key);     
     }
     node t = floor(x.right, key);
     if (t != null) {
       return t;     
     }
     else {
       return x;
     }
   }
   /**
   * returns the smallest key in the symbol table greater than or equal to key.
   * @param key the key
   * @return the smallest key in the symbol table greater than or equal to key
   * @throws nosuchelementexception if there is no such key
   * @throws nullpointerexception if key is null
   */
   public key ceiling(key key) {
     if (key == null) {
       throw new nullpointerexception("argument to ceiling() is null");
     }
     if (isempty()) {
       throw new nosuchelementexception("called ceiling() with empty symbol table");
     }
     node x = ceiling(root, key);
     if (x == null) {
       return null;
     }
     else {
       return x.key; 
     }
   }
   // the smallest key in the subtree rooted at x greater than or equal to the given key
   private node ceiling(node x, key key) { 
     if (x == null) {
       return null;
     }     
     int cmp = key.compareto(x.key);
     if (cmp == 0) {
       return x;
     }
     if (cmp > 0) {
       return ceiling(x.right, key);
     }
     node t = ceiling(x.left, key);
     if (t != null) {
       return t; 
     }
     else {
       return x;
     }
   }
   /**
   * return the kth smallest key in the symbol table.
   * @param k the order statistic
   * @return the kth smallest key in the symbol table
   * @throws illegalargumentexception unless k is between 0 and
   *   <em>n</em> − 1
   */
   public key select(int k) {
     if (k < 0 || k >= size()) {
       throw new illegalargumentexception();
     }
     node x = select(root, k);
     return x.key;
   }
   // the key of rank k in the subtree rooted at x
   private node select(node x, int k) {
     // assert x != null;
     // assert k >= 0 && k < size(x);
     int t = size(x.left); 
     if   (t > k) {
       return select(x.left, k); 
     }
     else if (t < k) {
       return select(x.right, k-t-1); 
     }
     else {
       return x; 
     }
   } 
   /**
   * return the number of keys in the symbol table strictly less than key.
   * @param key the key
   * @return the number of keys in the symbol table strictly less than key
   * @throws nullpointerexception if key is null
   */
   public int rank(key key) {
     if (key == null) {
       throw new nullpointerexception("argument to rank() is null");
     }
     return rank(key, root);
   } 
   // number of keys less than key in the subtree rooted at x
   private int rank(key key, node x) {
     if (x == null) {
       return 0; 
     }
     int cmp = key.compareto(x.key); 
     if   (cmp < 0) {
       return rank(key, x.left); 
     }
     else if (cmp > 0) {
       return 1 + size(x.left) + rank(key, x.right); 
     }
     else {
       return size(x.left); 
     }
   } 
  /***************************************************************************
   * range count and range search.
   ***************************************************************************/
   /**
   * returns all keys in the symbol table as an iterable.
   * to iterate over all of the keys in the symbol table named st,
   * use the foreach notation: for (key key : st.keys()).
   * @return all keys in the symbol table as an iterable
   */
   public iterable<key> keys() {
     if (isempty()) {
       return new queue<key>();
     }
     return keys(min(), max());
   }
   /**
   * returns all keys in the symbol table in the given range,
   * as an iterable.
   * @return all keys in the symbol table between lo 
   *  (inclusive) and hi (exclusive) as an iterable
   * @throws nullpointerexception if either lo or hi
   *  is null
   */
   public iterable<key> keys(key lo, key hi) {
     if (lo == null) {
       throw new nullpointerexception("first argument to keys() is null");
     }
     if (hi == null) {
       throw new nullpointerexception("second argument to keys() is null");
     }
     queue<key> queue = new queue<key>();
     // if (isempty() || lo.compareto(hi) > 0) return queue;
     keys(root, queue, lo, hi);
     return queue;
   } 
   // add the keys between lo and hi in the subtree rooted at x
   // to the queue
   private void keys(node x, queue<key> queue, key lo, key hi) { 
     if (x == null) {
       return; 
     }
     int cmplo = lo.compareto(x.key); 
     int cmphi = hi.compareto(x.key); 
     if (cmplo < 0) {
       keys(x.left, queue, lo, hi); 
     }
     if (cmplo <= 0 && cmphi >= 0) {
       queue.enqueue(x.key); 
     }
     if (cmphi > 0) {
       keys(x.right, queue, lo, hi); 
     }
   } 
   /**
   * returns the number of keys in the symbol table in the given range.
   * @return the number of keys in the symbol table between lo 
   *  (inclusive) and hi (exclusive)
   * @throws nullpointerexception if either lo or hi
   *  is null
   */
   public int size(key lo, key hi) {
     if (lo == null) {
       throw new nullpointerexception("first argument to size() is null");
     }
     if (hi == null) {
       throw new nullpointerexception("second argument to size() is null");
     }
     if (lo.compareto(hi) > 0) {
       return 0;
     }
     if (contains(hi)) {
       return rank(hi) - rank(lo) + 1;
     }
     else {
       return rank(hi) - rank(lo);     
     }
   }
  /***************************************************************************
   * check integrity of red-black tree data structure.
   ***************************************************************************/
   private boolean check() {
     if (!isbst())      system.out.println("not in symmetric order");
     if (!issizeconsistent()) system.out.println("subtree counts not consistent");
     if (!isrankconsistent()) system.out.println("ranks not consistent");
     if (!is23())       system.out.println("not a 2-3 tree");
     if (!isbalanced())    system.out.println("not balanced");
     return isbst() && issizeconsistent() && isrankconsistent() && is23() && isbalanced();
   }
   // does this binary tree satisfy symmetric order?
   // note: this test also ensures that data structure is a binary tree since order is strict
   private boolean isbst() {
     return isbst(root, null, null);
   }
   // is the tree rooted at x a bst with all keys strictly between min and max
   // (if min or max is null, treat as empty constraint)
   // credit: bob dondero's elegant solution
   private boolean isbst(node x, key min, key max) {
     if (x == null) {
       return true;
     }
     if (min != null && x.key.compareto(min) <= 0) {
       return false;     
     }
     if (max != null && x.key.compareto(max) >= 0) {
       return false;
     }
     return isbst(x.left, min, x.key) && isbst(x.right, x.key, max);
   } 
   // are the size fields correct?
   private boolean issizeconsistent() { 
     return issizeconsistent(root); 
   }
   private boolean issizeconsistent(node x) {
     if (x == null) {
       return true;
     }
     if (x.size != size(x.left) + size(x.right) + 1) {
       return false;
     }
     return issizeconsistent(x.left) && issizeconsistent(x.right);
   } 
   // check that ranks are consistent
   private boolean isrankconsistent() {
     for (int i = 0; i < size(); i++) {
       if (i != rank(select(i))) {
         return false;
       }
     }
     for (key key : keys()) {
       if (key.compareto(select(rank(key))) != 0) {
         return false;
       }
     }
     return true;
   }
   // does the tree have no red right links, and at most one (left)
   // red links in a row on any path?
   private boolean is23() { 
     return is23(root); 
   }
   private boolean is23(node x) {
     if (x == null) {
       return true;
     }
     if (isred(x.right)) {
       return false;
     }
     if (x != root && isred(x) && isred(x.left)){
       return false;
     }
     return is23(x.left) && is23(x.right);
   } 
   // do all paths from root to leaf have same number of black edges?
   private boolean isbalanced() { 
     int black = 0;   // number of black links on path from root to min
     node x = root;
     while (x != null) {
       if (!isred(x)) black++;
       x = x.left;
     }
     return isbalanced(root, black);
   }
   // does every path from the root to a leaf have the given number of black links?
   private boolean isbalanced(node x, int black) {
     if (x == null) {
       return black == 0;     
     }
     if (!isred(x)) {
       black--;
     }
     return isbalanced(x.left, black) && isbalanced(x.right, black);
   } 
   /**
   * unit tests the redblackbst data type.
   */
   public static void main(string[] args) { 
     redblackbst<string, integer=""> st = new redblackbst<string, integer="">();
     string data = "a b c d e f g h m n o p";
     scanner sc = new scanner(data);
     int i = 0;
     while (sc.hasnext()) {     
      string key = sc.next();
      st.put(key, i);
      i++;
     }
     sc.close();   
     for (string s : st.keys())
       system.out.println(s + " " + st.get(s));
     system.out.println();
     boolean result = st.check();
     system.out.println("check: " + result);
   }
 }

<code>a 0
b 1
c 2
d 3
e 4
f 5
g 6
h 7
m 8
n 9
o 10
p 11
 
check: true</code>