数据结构基础13———非线性数据结构之自平衡二叉查找树之红黑树

红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能,但是与AVL不同的是红黑树不是完全平衡的二叉树只是近似平衡。
它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

顾名思义,红黑树中的节点,一类被标记为黑色,一类被标记为红色。除此之外,一棵红黑树还需要满足这样几个要求:

根节点是黑色的;

每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;

任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;

每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

事实上,说道平衡二叉树大部分人第一反应就是红黑树(虽然它并不完全平衡),这也是目前业界使用最广泛的自平衡二叉树,相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。

场景:
前面我们为了处理二叉查找树的单边退化问题,引入了平衡二叉树AVL树,但是AVL树严格要求高度差不能大于1,所以导致在插入删除过程中需要进行大量的旋转平衡操作反而影响了插入删除的性能。所以我们引入了2-3树,但是2-3树并不是二叉树,且2节点和3节点的组合方式有点显得有点不伦不类(至少对强迫症患者来说)。那么有没有一种二叉树的平衡2-3树实现呢?
为了解决这个问题,在这一章中答案就是红黑树了,只不过要加上左倾二字(事实上我一直喜欢将红黑树看做时2-3树的二叉树版实现,数学上称他们为同构)

在2-3树中,最让强迫症犯难的就是3节点。如果没有3节点那么整棵2-3树看上去就是一棵满二叉树。所以讲2-3树用二叉树形式实现的首要目标就是干掉3节点。

替换3-节点

红黑树背后的基本思想是用标准的二叉查找树(完全由2节点组成)和一些额外信息(替换3节点)来表示2-3树。我们将树中的链接分为两种类型:

红色链接将两个2节点连接起来构成一个3节点
黑色链接则是2-3树中的普通连接。

确切的说我们将3节点表示为由一条左斜的红色连接(两个2节点其中之一是另一个左子节点)相连的2个2节点。这样我们不用做任何修改就可以直接使用二叉树的get()方法。对于任意2-3树只要对节点进行转换,我们都可以派生出一棵对应的二叉查找树。用这种方法表示的2-3树就被称为红黑树。
(这就是《算法》中对红黑树实现的标准阐述,对双黑、caseN 法死记硬背感觉痛苦的童鞋不妨换一个思考方式来理解)自己推导更容易理解和实现
image.png

这样转换出的红黑树除了满足标准的红黑树定义外,因为我们是将3节点表示为由一条【左斜的红色连接】所以又称左倾红黑树,除标准的红黑树特性外还多一个红连接在左边。

如果我们将一颗红黑树中的红链接画平,那么所有的空链接到根结点的距离都将是相同的。如果我们将由红链接相连的结点合并,得到的就是一颗2-3树。

相反,如果将一颗2-3树中的3-结点画作由红色左链接相连的两个2-结点,那么不会存在能够和两条红链接相连的结点,且树必然是完美平衡的。
image.png

每个节点都有一条由父节点指向自己的链接,用bool变量来表示链接的颜色,约定空链接的颜色是黑色。

image.png

旋转

在我们实现的某些操作中可能会出现红色右链接或者两条连续的红链接,但在操作完成前这些情况都会被小心地旋转并修复。

(我们在这里不讨论旋转的几种情况,把红黑树看做2-3树,自然可以得到正确的旋转后结果)

image.png

插入

在插入时我们可以使用旋转操作帮助我们保证2-3树和红黑树之间的一一对应关系,因为旋转操作可以保持红黑树的两个重要性质:有序性和完美平衡性。

插入也很简单:有空则插,没空硬插,再分裂。

这样,我们就不用记那么复杂且让人头疼的红黑树插入旋转的各种情况了。只要清楚2-3树的插入方式即可。

向单个2-节点插入新键:
image.png

向树底部的2-节点插入新键:
image.png

向一颗仅有一个红链接相连的两个节点的树种插入新键:
image.png

flipColor
这项操作的重要性质在于它是局部变换,不会影响黑链的平衡性
image.png

根节点永远是黑色的
每次插入都会将根节点设置成黑色,每当根节点由红变黑的时候,黑链接高度就会加1

向树底部的3-节点中插入新键
image.png

红链接向上传递
image.png

红黑树的构造轨迹
image.png

传统红黑树与2-3-4树对应。
虽然看上去复杂,但是如果理解2-3树,那么相应的就可以推导出红黑树的操作步骤。所以并不建议死记硬背(关键是背着也晕啊!😵)

Java中TreeMap就是用红黑树实现的,另外在讲散列表时也提到在HashMap链表法实现时长度大于8也会自动转换为红黑树。感兴趣的可自行查看相应源码


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);
   }
 }

更新时间:2020-02-13 15:36:18

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构13非线性数据结构之平衡二叉查找树之红黑树
最后更新:2020-02-13 15:36:18

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×