Java红黑树代码实现

Java红黑树是一种自平衡二叉搜索树，它是在二叉查找树的基础上添加了一些限制，以保证树的平衡。红黑树的着色性质，即每个节点要么是红色的，要么是黑色的，并且有以下几条性质：

1. 每个节点要么是红色的，要么是黑色的。
2. 根节点是黑色的。
3. 每个叶子节点都是黑色的。
4. 如果一个节点是红色的，那么它的子节点一定是黑色的。
5. 对于任意一个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点。

下面是一个Java红黑树的代码实现：

public class RedBlackTree {
  private static final boolean RED = true;
  private static final boolean BLACK = false;

  private class Node {
    int key;
    Node left;
    Node right;
    boolean color;

    public Node(int key, boolean color) {
      this.key = key;
      this.color = color;
    }
  }

  private Node root;

  public void put(int key) {
    root = put(root, key);
    root.color = BLACK;
  }

  private Node put(Node h, int key) {
    if (h == null) {
      return new Node(key, RED);
    }

    if (key < h.key) {
      h.left = put(h.left, key);
    } else if (key > h.key) {
      h.right = put(h.right, key);
    } else {
      h.key = key;
    }

    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)) {
      flipCol