红黑树

2-3树

2-3树的节点它可以有一个元素，也可以有两个元素，它也满足二分搜索树的性质
红黑树 - 图1
我们把含有两个孩子的节点称为2节点，含有3个孩子的节点称为3节点
红黑树 - 图2
2-3树是一种绝对平衡的树，所谓绝对平衡的树指的是从根节点到任意一个叶子节点，所经过的节点是都是相同的。那么2-3树是怎么做到的呢?
红黑树 - 图3

红黑树与2-3树的等价性

由于我们一般每个节点都是表示一个数据的，2-3树有点难以实现，所以有人发明一种树叫做红黑树，它可以说是2-3树的等价，那么它树如何等价的呢?
红黑树 - 图4
上图想必很清楚的描述了等价的过程
红黑树 - 图5
现在我们来实现一下上面描述的红黑树，大部分的代码都是和二分搜索树是重合的，只是在添加时有调整，另外这里我们不牵涉到从红黑树中删除元素，因为太复杂了(其实是我不会)

  1. public class RedBlackTree<E extends Comparable<E>> {
  2.     //规定红色为true 黑色为false
  3.     private static final boolean RED = true;
  4.     private static final boolean BLACK = false;
  6.     private class Node {
  7.         public E e;
  8.         public Node left;
  9.         public Node right;
  10.         public boolean color;
  12.         public Node(E e) {
  13.             this.e = e;
  14.             left = null;
  15.             right = null;
  16.             //我们在2-3树中添加节点时 永远是和别的节点融合 所以默认为红色
  17.             color = RED;
  18.         }
  20.         @Override
  21.         public String toString() {
  22.             return e.toString();
  23.         }
  24.     }
  26.     private Node root;
  27.     private int size;
  29.     public RedBlackTree() {
  30.         root = null;
  31.         size = 0;
  32.     }
  34.     public int size() {
  35.         return size;
  36.     }
  37.     public boolean isEmpty() {
  38.         return size == 0;
  39.     }
  41.     public void add(E e) {
  42.         root = add(root, e);
  43.     }
  45.     // 判断节点node的颜色
  46.     private boolean isRed(Node node){
  47.         if(node == null)
  48.             return BLACK;
  49.         return node.color;
  50.     }
  52.     private Node add(Node node, E e) {
  53.         if (node == null) {
  54.             size++;
  55.             return new Node(e);
  56.         }
  58.         if (e.compareTo(node.e) < 0) {
  59.             node.left = add(node.left, e);
  60.         } else if (e.compareTo(node.e) > 0) {
  61.             node.right = add(node.right,e);
  62.         }
  64.         return node;
  65.     }
  67.     public boolean contains(E e) {
  68.         return contains(root, e);
  69.     }
  71.     private boolean contains(Node node, E e) {
  72.         if (node == null) {
  73.             return false;
  74.         }
  76.         if (e.equals(node.e)) {
  77.             return true;
  78.         } else if (e.compareTo(node.e) < 0) {
  79.             return contains(node.left, e);
  80.         } else {
  81.             return contains(node.right,e);
  82.         }
  83.     }
  84. }

红黑树的性质

在了解了红黑树与2-3等价以后，我们来看红黑树满足哪些性质

  • 每个节点或者是红色的，或者的是黑色的
  • 根节点是黑色的

红黑树 - 图6

  • 每一个叶子节点(最后的空节点是黑色的)
    • 因为红色节点只存在于3节点中，而所有的叶子节点都是2节点
  • 如果一个节点是红色的，那么它的所有孩子节点都是黑色的

红黑树 - 图7

  • 从任意一个节点到黑色节点，经过的黑色节点是一样的
    • 因为2-3树到所有叶子节点的距离都是一样的，而经过的节点，不管是2节点还是3节点，都包括一个黑色节点，所以经过的黑色节点是一样的

向红黑树中添加元素

因为根节点是黑色的，所以我们在添加完元素后需要将根节点变为黑色

  1. public void add(E e) {
  2.     root = add(root, e);
  4.     root.color = BLACK;
  5. }

在添加元素到红黑树中时，可能会破坏红黑树的规则，这时就需要红黑树进行自我调整，我们就来看一下添加过程会碰到的所有情形，以及处理方法
红黑树 - 图8

  1. //   node                     x
  2. //  /   \     左旋转         /  \
  3. // T1   x   --------->   node   T3
  4. //     / \              /   \
  5. //    T2 T3            T1   T2
  6. private Node leftRotate(Node node){
  7.     Node x = node.right;
  8.     // 左旋转
  9.     node.right = x.left;
  10.     x.left = node;
  11.     x.color = node.color;
  12.     node.color = RED;
  13.     return x;
  14. }

红黑树 - 图9

  1. // 颜色翻转
  2. private void flipColors(Node node){
  3.     node.color = RED;
  4.     node.left.color = BLACK;
  5.     node.right.color = BLACK;
  6. }

红黑树 - 图10

  1. //     node                   x
  2. //    /   \     右旋转       /  \
  3. //   x    T2   ------->   y   node
  4. //  / \                       /  \
  5. // y  T1                     T1  T2
  6. private Node rightRotate(Node node){
  7.     Node x = node.left;
  8.     // 右旋转
  9.     node.left = x.right;
  10.     x.right = node;
  11.     x.color = node.color;
  12.     node.color = RED;
  13.     return x;
  14. }

红黑树 - 图11
对上面的情况进行总结
红黑树 - 图12

  1. private Node add(Node node, E e) {
  3.     if (node == null) {
  4.         size++;
  5.         return new Node(e);
  6.     }
  8.     if (e.compareTo(node.e) < 0) {
  9.         node.left = add(node.left, e);
  10.     } else if (e.compareTo(node.e) > 0) {
  11.         node.right = add(node.right,e);
  12.     }
  14.     if (isRed(node.right) && !isRed(node.left))
  15.         node = leftRotate(node);
  16.     if (isRed(node.left) && isRed(node.left.left))
  17.         node = rightRotate(node);
  18.     if (isRed(node.left) && isRed(node.right))
  19.         flipColors(node);
  21.     return node;
  22. }

完整代码

  1. public class RedBlackTree<E extends Comparable<E>> {
  2.     //规定红色为true 黑色为false
  3.     private static final boolean RED = true;
  4.     private static final boolean BLACK = false;
  6.     private class Node {
  7.         public E e;
  8.         public Node left;
  9.         public Node right;
  10.         public boolean color;
  12.         public Node(E e) {
  13.             this.e = e;
  14.             left = null;
  15.             right = null;
  16.             //我们在2-3树中添加节点时 永远是和别的节点融合 所以默认为红色
  17.             color = RED;
  18.         }
  20.         @Override
  21.         public String toString() {
  22.             return e.toString();
  23.         }
  24.     }
  26.     private Node root;
  27.     private int size;
  29.     public RedBlackTree() {
  30.         root = null;
  31.         size = 0;
  32.     }
  34.     public int size() {
  35.         return size;
  36.     }
  37.     public boolean isEmpty() {
  38.         return size == 0;
  39.     }
  41.     private boolean isRed(Node node) {
  42.         if (node == null) {
  43.             return BLACK;
  44.         }
  45.         return node.color;
  46.     }
  48.     //   node                     x
  49.     //  /   \     左旋转         /  \
  50.     // T1   x   --------->   node   T3
  51.     //     / \              /   \
  52.     //    T2 T3            T1   T2
  53.     private Node leftRotate(Node node) {
  54.         Node x = node.right;
  55.         node.right = x.left;
  56.         x.left = node;
  58.         x.color = node.color;
  59.         node.color = RED;
  61.         return x;
  62.     }
  64.     //     node                   x
  65.     //    /   \     右旋转       /  \
  66.     //   x    T2   ------->   y   node
  67.     //  / \                       /  \
  68.     // y  T1                     T1  T2
  69.     private Node rightRotate(Node node) {
  70.         Node x = node.left;
  71.         node.left = x.right;
  72.         x.right = node;
  74.         x.color = node.color;
  75.         node.color = RED;
  77.         return x;
  78.     }
  80.     private void flipColors(Node node) {
  81.         node.color = RED;
  82.         node.left.color = BLACK;
  83.         node.right.color = BLACK;
  84.     }
  86.     public void add(E e) {
  87.         root = add(root, e);
  89.         root.color = BLACK;
  90.     }
  93.     private Node add(Node node, E e) {
  94.         if (node == null) {
  95.             size++;
  96.             return new Node(e);
  97.         }
  99.         if (e.compareTo(node.e) < 0) {
  100.             node.left = add(node.left, e);
  101.         } else if (e.compareTo(node.e) > 0) {
  102.             node.right = add(node.right,e);
  103.         }
  105.         if (isRed(node.right) && !isRed(node.left))
  106.             node = leftRotate(node);
  107.         if (isRed(node.left) && isRed(node.left.left))
  108.             node = rightRotate(node);
  109.         if (isRed(node.left) && isRed(node.right))
  110.             flipColors(node);
  112.         return node;
  113.     }
  115.     public boolean contains(E e) {
  116.         return contains(root, e);
  117.     }
  119.     private boolean contains(Node node, E e) {
  120.         if (node == null) {
  121.             return false;
  122.         }
  124.         if (e.equals(node.e)) {
  125.             return true;
  126.         } else if (e.compareTo(node.e) < 0) {
  127.             return contains(node.left, e);
  128.         } else {
  129.             return contains(node.right,e);
  130.         }
  131.     }
  132. }