• 2-3树介绍
  • 2-3树插入元素
  • 红黑树由来(和2-3树等价)
  • 红黑树性质的理解
  • 红黑树中添加元素
  • 添加中维护红黑树的代码
  • 使用LeetCode804. Unique Morse Code Words测试红黑树

一、前言

红黑树之前，可以先看一下二叉搜索树和平衡二叉树。

二、2-3树介绍

  • 2节点: 容纳1个元素，有2个孩子；
  • 3节点: 容纳2个元素，有3个孩子；
  • 4节点: 容纳3个元素，有4个孩子；
  • ………

红黑树总结 - 图1
红黑树总结 - 图2

绝对平衡表示的是任意子树左右高度之差为0。

三、2-3树插入元素

一个原则: 添加节点将永远不会添加到一个空的位置(和二叉搜索树不同)、只会和最后找到的叶子节点做融合。
细分为四种情况:

  • 向2节点(2个孩子的节点)中添加1个元素，融合成一个3节点；
  • 向3节点(3个孩子的节点)中添加1个元素，先融合成为一个4节点、如果这个4节点是根节点，直接分裂成含有三个2节点的一棵树；

  • 如果这个4节点不是根节点，就不能分裂成含有三个2节点的一棵树；因为这样会破坏2-3树的绝对平衡性。正确的做法是向上和父亲节点做新的融合，这里又分为两种情况:

    • 第一种情况: 父亲为2节点，直接融合到父亲，变成3节点；
    • 第二种情况: 父亲为3节点，先融合到父亲，变成4节点，然后父亲分散，全部变成2节点；

下图的层次关系可能会比较清楚:

红黑树总结 - 图3

看具体的细分的四种情况:
1)、最简单的情况:
红黑树总结 - 图4

2)、插入3节点且是根:

红黑树总结 - 图5

3)、插入3节点且不是根且父亲是2节点:

红黑树总结 - 图6

红黑树总结 - 图7

4)、插入3节点且不是根且父亲是3节点:

红黑树总结 - 图8

红黑树总结 - 图9

红黑树总结 - 图10

四、红黑树由来(和2-3树等价)

<<算法4>>中提到2-3树和红黑树是等价的，则其中2节点和3节点对应红黑树的关系有两种：
1)、第一种 : 2节点转换成红黑树节点 :

红黑树总结 - 图11
2)、第二种 : 3节点转换成红黑树节点

  • 由于一般树结构一个节点只表示一个值，所以要将3节点用一种特殊的方式转换，即转换成红黑树节点；
    红黑树总结 - 图12
  • 上面的摆放只是直观的摆放，我们需要将b节点作为c节点的左孩子，但是又需要去标识b和c的对应关系(是一个3节点而且b < c) 所以我们将b、c中间的线绘制成红色；并且还原成二分搜索树的样子:
    红黑树总结 - 图13
  • 但是在二叉树的实现中没有使用相应的类来表示那条边是红色的，所以我们使用节点来表示这个特性，由于每一个节点只有一个父亲，也就是每一个节点和它父亲相连的边只有一条边，所以我们可以把这条边(红色)的信息存放在结点上，也就是把b描绘成红色，所以这就是红色节点的由来:这个红色的节点b表示的是这个节点之前在2-3树中是在一个3节点中，而且和它的父亲是存放在一起的(并列)，而且它的值比它父亲小。
    红黑树总结 - 图14

然后再看一个2-3树和红黑树转换的例子:

红黑树总结 - 图15

更加直观的看:

红黑树总结 - 图16

五、红黑树性质的理解

红黑树总结 - 图17

  • 第一条: 这个很简单，是红黑树的定义；
  • 第二条: 由于在2-3树中根节点或者是2节点，或者是3节点，这两种节点转换成红黑树节点之后根节点都是黑色的；
    红黑树总结 - 图18
  • 第三条: 与其说是性质，不如说是定义，不过要注意这里的叶子节点指的是最后的空节点，都指定为黑色的节点，如果是空树，则同时满足2、3条性质；
  • 第四条: 也是和2-3树密切关系，一个红色节点，在2-3树中是3节点的左边节点，它的左右孩子在2-3树中都要么是2节点，要么是3节点，但是他们的根都是黑色的；
    红黑树总结 - 图19
  • 第五条: 是最重要的一条性质，最主要的原因是2-3树是绝对平衡的，如果途中经过的是一个3节点也不要紧，反正都是有一个黑色节点，所以经过的黑色节点的数量是一样多的；所以红黑树是保持”黑平衡”的二叉树，本质就是2-3树是绝对平衡的；

红黑树总结 - 图20

六、红黑树中添加元素

一个原则: 新插入的结点永远是红色

红黑树总结 - 图21

有几个子过程步骤以及相关需要维护的地方

  • 第一个：维护根节点为黑色，因为我们第二条性质是根节点永远为黑色，所以我们在插入完节点之后，要维护根节点为黑色；
    1)、插入: 红黑树总结 - 图22
    2)、更一般的情况对于根的维护:
    红黑树总结 - 图23

  • 第二个：也是插入的第二种情况，这个很简单，也不需要维护，直接插入就好　:
    红黑树总结 - 图24

  • 第三个：也是插入的第三种情况，也就是待插入的红色结点比根节点大(插在右边)，这个需要维护，和AVL中一样，类似RR型，需要进行左旋转:
    红黑树总结 - 图25

过程如下:

红黑树总结 - 图26

但是这样还不够，我们还需要维护颜色: 此时x成为了新的根节点，所以x.color = node.color(x颜色变成之前根节点的颜色)；　而node.color = RED，因为形成的还是3节点：(注意之前的node.color有可能是红色，但是后续还要处理 )

红黑树总结 - 图27

代码:

  1.  /**左旋转
  3.          node                   x
  4.         /   \          -->    /   \
  5.        T1    x              node  T3
  6.            /   \            /  \
  7.           T2    T3         T1  T2
  8.      */
  9.     private Node leftRotate(Node node){
  10.         Node x = node.right;
  11.         Node T2 = x.left;
  13.         x.left = node;
  14.         node.right = T2;
  16.         //update color
  17.         x.color = node.color;
  18.         node.color = RED;
  20.         return x;
  21.     }
  • 第四个: 也是插入的第四种情况，也是另一种维护情况:>颜色反转， 在根节点的右侧插入: 其实相当于在2-3树中的3节点中插入元素，然后分散:
    红黑树总结 - 图28

在2-3树中散开之后都成为了2节点，所以需要变成全都是黑色节点:

红黑树总结 - 图29

最后融合，根节点又需要变回红色，因为这个根节点要向上去和它的父亲节点去融合:

红黑树总结 - 图30

整体如下图 (需要经过两次换色)

红黑树总结 - 图31

代码:

  1.    //三个节点的颜色反转 根->RED  两个孩子->BLACK
  2.     private void flipColors(Node node){
  3.         node.color = RED;
  4.         node.left.color = BLACK;
  5.         node.right.color = BLACK;
  6.     }
  • 第五个:也是插入的第五种情况，在根节点的左边的左边，也就是向2-3树中的3结点的左边添加元素:

红黑树总结 - 图32

等价于在2-3树中这样插入:
红黑树总结 - 图33

然后需要进行右旋转:
红黑树总结 - 图34

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

然后又需要维护颜色(前两部同左旋转，最后一步是颜色翻转(filpColors))

红黑树总结 - 图35

  • 第六个: 在根节点的左孩子的右边添加，类似2-3树中添加在3节点的中间，这个只需要运用前面的那些步骤综合即可完成:

红黑树总结 - 图36

a)、先对37进行左旋转 :

红黑树总结 - 图37

b)、对上面的结果进行右旋转，并且调整颜色 :

红黑树总结 - 图38

c)、最后进行之前的颜色翻转(filpColors):

红黑树总结 - 图39

  • 总结 : 所以我们发现，其实就是三种基本操作: 左旋转，右旋转，颜色翻转的结合

红黑树总结 - 图40

所以这是一个维护链，放在add中代码如下:

  1.      /** 向红黑树中添加新的元素(key, value) */
  2.     public void add(K key, V value) {//相当于JDK的put操作
  3.         root = add(root, key, value);
  4.         root.color = BLACK; /**子过程一: 保持最终根节点为黑色  --> 第二条性质 */
  5.     }
  7.     // 向以node为根的红黑树树中插入元素(key, value)，递归算法,返回插入新节点后红黑树树的根
  8.     private Node add(Node node, K key, V value) {
  10.         if (node == null) {
  11.             size++;
  12.             return new Node(key, value);
  13.         }
  15.         if (key.compareTo(node.key) < 0)
  16.             node.left = add(node.left, key, value);
  17.         else if (key.compareTo(node.key) > 0)
  18.             node.right = add(node.right, key, value);
  19.         else   // key.compareTo(node.key) == 0
  20.             node.value = value;
  22.         /**维护链: 注意三个if不是互斥的  就是一个维护链的关系 */
  23.         if(isRed(node.right) && !isRed(node.left)){ //右红，左黑  -> 左旋
  24.             node = leftRotate(node);
  25.         }
  26.         if(isRed(node.left) && isRed(node.left.left)){ //左红 左左红  ->  右旋
  27.             node = rightRotate(node);
  28.         }
  29.         if(isRed(node.left) && isRed(node.right)){//左红右红自己黑  -->颜色翻转
  30.             flipColors(node);
  31.         }
  32.         return node;
  33.     }

重点在这段代码，就是三种基本的维护组成的维护链:

  1.       /**维护链: 注意三个if不是互斥的  就是一个维护链的关系 */
  2.         if(isRed(node.right) && !isRed(node.left)){ //右红，左黑  -> 左旋
  3.             node = leftRotate(node);
  4.         }
  5.         if(isRed(node.left) && isRed(node.left.left)){ //左红 左左红  ->  右旋
  6.             node = rightRotate(node);
  7.         }
  8.         if(isRed(node.left) && isRed(node.right)){//左红右红自己黑  -->颜色翻转
  9.             flipColors(node);
  10.         }

七、添加中维护红黑树的代码

这里完成了左倾红黑树的add操作 : ，没有实现remove()，完整测试源码如下:

  1. package DataStructure.Tree.RB;
  4. import java.util.Arrays;
  6. /**
  7.  * 红黑树实现  BSTMap中拷贝过来的
  8.  */
  9. public class RBTree<K extends Comparable<K>, V>  {
  11.     private final static boolean RED = true;
  12.     private final static boolean BLACK = false;
  14.     private class Node {
  15.         public K key;
  16.         public V value;
  17.         public Node left, right;
  18.         public boolean color;
  20.         public Node(K key, V value) {
  21.             this.key = key;
  22.             this.value = value;
  23.             left = null;
  24.             right = null;
  25.             // 一开始添加的时候都是红结点
  26.             color = RED; //为什么一开始是红色,因为在2-3结点中添加一个结点，永远是和叶子结点进行融合，所以是3节点，所以设置成红色
  27.         }
  28.     }
  30.     private Node root;
  31.     private int size;
  33.     public RBTree() {
  34.         root = null;
  35.         size = 0;
  36.     }
  38.     public int getSize() {
  39.         return size;
  40.     }
  42.     public boolean isEmpty() {
  43.         return size == 0;
  44.     }
  46.     /** 判断节点node的颜色 */
  47.     private boolean isRed(Node node){
  48.         if(node == null) return BLACK;
  49.         return node.color;
  50.     }
  53.     /**左旋转
  55.          node                   x
  56.         /   \          -->    /   \
  57.        T1    x              node  T3
  58.            /   \            /  \
  59.           T2    T3         T1  T2
  60.      */
  61.     private Node leftRotate(Node node){
  62.         Node x = node.right;
  63.         Node T2 = x.left;
  65.         x.left = node;
  66.         node.right = T2;
  68.         //update color
  69.         x.color = node.color;
  70.         node.color = RED;
  72.         return x;
  73.     }
  75.     /**右旋转
  76.            node                 x
  77.           /    \              /   \
  78.          x     T1    -->     y    node
  79.         / \                 / \   /  \
  80.        y   T2              T4 T3 T2  T1
  81.       / \
  82.      T4 T3
  83.      */
  84.     private Node rightRotate(Node node){
  85.         Node x = node.left;
  86.         Node T2 = x.right;
  87.         x.right = node;
  88.         node.left = T2;
  90.         //update color
  91.         x.color = node.color;
  92.         node.color = RED;
  94.         return x;
  95.     }
  97.     /**三个节点的颜色反转 根->RED  两个孩子->BLACK */
  98.     private void flipColors(Node node){
  99.         node.color = RED;
  100.         node.left.color = BLACK;
  101.         node.right.color = BLACK;
  102.     }
  104.     /** 向红黑树中添加新的元素(key, value) */
  105.     public void add(K key, V value) {//相当于JDK的put操作
  106.         root = add(root, key, value);
  107.         root.color = BLACK; /**子过程一: 保持最终根节点为黑色  --> 第二条性质 */
  108.     }
  110.     // 向以node为根的红黑树树中插入元素(key, value)，递归算法,返回插入新节点后红黑树树的根
  111.     private Node add(Node node, K key, V value) {
  113.         if (node == null) {
  114.             size++;
  115.             return new Node(key, value);
  116.         }
  118.         if (key.compareTo(node.key) < 0)
  119.             node.left = add(node.left, key, value);
  120.         else if (key.compareTo(node.key) > 0)
  121.             node.right = add(node.right, key, value);
  122.         else   // key.compareTo(node.key) == 0
  123.             node.value = value;
  125.         /**维护链: 注意三个if不是互斥的  就是一个维护链的关系 */
  126.         if(isRed(node.right) && !isRed(node.left)){ //右红，左黑  -> 左旋
  127.             node = leftRotate(node);
  128.         }
  129.         if(isRed(node.left) && isRed(node.left.left)){ //左红 左左红  ->  右旋
  130.             node = rightRotate(node);
  131.         }
  132.         if(isRed(node.left) && isRed(node.right)){
  133.             flipColors(node);
  134.         }
  135.         return node;
  136.     }
  138.     // 返回以node为根节点的红黑树中，key所在的节点
  139.     private Node getNode(Node node, K key) {
  141.         if (node == null)
  142.             return null;
  144.         if (key.equals(node.key))
  145.             return node;
  146.         else if (key.compareTo(node.key) < 0)
  147.             return getNode(node.left, key);
  148.         else   // if(key.compareTo(node.key) > 0)
  149.             return getNode(node.right, key);
  150.     }
  152.     public boolean contains(K key) {
  153.         return getNode(root, key) != null;
  154.     }
  156.     public V get(K key) {
  157.         Node node = getNode(root, key);
  158.         return node == null ? null : node.value;
  159.     }
  161.     public void set(K key, V newValue) {
  162.         Node node = getNode(root, key);
  163.         if (node == null)
  164.             throw new IllegalArgumentException(key + " doesn't exist!");
  166.         node.value = newValue;
  167.     }
  169.     // 返回以node为根的红黑树的最小值所在的节点
  170.     private Node minimum(Node node) {
  171.         if (node.left == null)
  172.             return node;
  173.         return minimum(node.left);
  174.     }
  176.     // 删除掉以node为根的红黑树中的最小节点,返回删除节点后新的红黑树的根
  177.     private Node removeMin(Node node) {
  178.         if (node.left == null) {
  179.             Node rightNode = node.right;
  180.             node.right = null;
  181.             size--;
  182.             return rightNode;
  183.         }
  184.         node.left = removeMin(node.left);
  185.         return node;
  186.     }
  188.     //没有实现remove中的调整
  189.     public V remove(K key) {
  190.         throw new UnsupportedOperationException("No remove in RBTree!");
  191.     }
  193.     public void printTree(){
  194.         printTree(root,0,"H",8);
  195.     }
  196.     public void printTree(Node head,int height,String to,int len){
  197.         if(head == null)return;
  198.         printTree(head.right,height + 1,"v",len);
  200.         String val = to + head.key + to;  //两边指示的字符
  201.         int lenV = val.length();
  202.         int lenL = (len - lenV)/2;  //左边的空格(分一半)
  203.         int lenR = len - lenV - lenL; // 右边的空格
  204.         System.out.println( getSpace(len * height) + getSpace(lenL) + val + getSpace(lenR));
  206.         printTree(head.left,height + 1,"^",len);
  207.     }
  208.     public static String getSpace(int len){
  209.         StringBuffer str = new StringBuffer();
  210.         for(int i = 0; i < len; i++) str.append(" ");
  211.         return str.toString();
  212.     }
  214.     public static void main(String[] args) {
  215.         Integer[] arr = {42,33,50,17,37,48,88,12,18,66,6};
  216. //        Arrays.sort(arr); //排序后插入也会保持平衡  但是BST会退化成链表
  217.         RBTree<Integer,Integer>rbTree = new RBTree<>();
  218.         for(int i = 0; i < arr.length; i++){
  219.             rbTree.add(arr[i],null);
  220.         }
  221.         rbTree.printTree();
  222.     }
  224. }

测试结果:
红黑树总结 - 图41

和这颗红黑树是一样的:

红黑树总结 - 图42

二叉树打印见这里。

八、使用LeetCode804. Unique Morse Code Words测试红黑树

题目链接

题目

红黑树总结 - 图43

解析

题目很简单，就是要你解析字符串之后看有多少种不同的翻译，使用HashSet和TreeSet都可以做，这里用RBTree改装的Set来测试(类似JDK中的TreeSet):

  1. class Solution {
  2.     public int uniqueMorseRepresentations(String[] words) {
  4.         String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
  5.         RBTree<String, Object> set = new RBTree<>();
  6.         for(String word: words){
  7.             StringBuilder res = new StringBuilder();
  8.             for(int i = 0 ; i < word.length() ; i ++)
  9.                 res.append(codes[word.charAt(i) - 'a']);
  11.             set.add(res.toString(), null);
  12.         }
  14.         return set.getSize();
  15.     }
  18.     private class RBTree<K extends Comparable<K>, V>  {
  21.         private final static boolean RED = true;
  22.         private final static boolean BLACK = false;
  24.         private class Node {
  25.             public K key;
  26.             public V value;
  27.             public Node left, right;
  28.             public boolean color;
  30.             public Node(K key, V value) {
  31.                 this.key = key;
  32.                 this.value = value;
  33.                 left = null;
  34.                 right = null;
  35.                 // 一开始添加的时候都是红结点
  36.                 color = RED; //为什么一开始是红色,因为在2-3结点中添加一个结点，永远是和叶子结点进行融合，所以是3节点，所以设置成红色
  37.             }
  38.         }
  40.         private Node root;
  41.         private int size;
  43.         public RBTree() {
  44.             root = null;
  45.             size = 0;
  46.         }
  48.         public int getSize() {
  49.             return size;
  50.         }
  52.         public boolean isEmpty() {
  53.             return size == 0;
  54.         }
  56.         /** 判断节点node的颜色 */
  57.         private boolean isRed(Node node){
  58.             if(node == null) return BLACK;
  59.             return node.color;
  60.         }
  63.         /**左旋转
  65.              node                   x
  66.             /   \          -->    /   \
  67.            T1    x              node  T3
  68.                /   \            /  \
  69.               T2    T3         T1  T2
  70.          */
  71.         private Node leftRotate(Node node){
  72.             Node x = node.right;
  73.             Node T2 = x.left;
  75.             x.left = node;
  76.             node.right = T2;
  78.             //update color
  79.             x.color = node.color;
  80.             node.color = RED;
  82.             return x;
  83.         }
  85.         /**右旋转
  86.                node                 x
  87.               /    \              /   \
  88.              x     T1    -->     y    node
  89.             / \                 / \   /  \
  90.            y   T2              T4 T3 T2  T1
  91.           / \
  92.          T4 T3
  93.          */
  94.         private Node rightRotate(Node node){
  95.             Node x = node.left;
  96.             Node T2 = x.right;
  97.             x.right = node;
  98.             node.left = T2;
  100.             //update color
  101.             x.color = node.color;
  102.             node.color = RED;
  104.             return x;
  105.         }
  107.         /**三个节点的颜色反转 根->RED  两个孩子->BLACK */
  108.         private void flipColors(Node node){
  109.             node.color = RED;
  110.             node.left.color = BLACK;
  111.             node.right.color = BLACK;
  112.         }
  114.         /** 向红黑树中添加新的元素(key, value) */
  115.         public void add(K key, V value) {//相当于JDK的put操作
  116.             root = add(root, key, value);
  117.             root.color = BLACK; /**子过程一: 保持最终根节点为黑色  --> 第二条性质 */
  118.         }
  120.         // 向以node为根的红黑树树中插入元素(key, value)，递归算法,返回插入新节点后红黑树树的根
  121.         private Node add(Node node, K key, V value) {
  123.             if (node == null) {
  124.                 size++;
  125.                 return new Node(key, value);
  126.             }
  128.             if (key.compareTo(node.key) < 0)
  129.                 node.left = add(node.left, key, value);
  130.             else if (key.compareTo(node.key) > 0)
  131.                 node.right = add(node.right, key, value);
  132.             else   // key.compareTo(node.key) == 0
  133.                 node.value = value;
  135.             /**维护链: 注意三个if不是互斥的  就是一个维护链的关系 */
  136.             if(isRed(node.right) && !isRed(node.left)){ //右红，左黑  -> 左旋
  137.                 node = leftRotate(node);
  138.             }
  139.             if(isRed(node.left) && isRed(node.left.left)){ //左红 左左红  ->  右旋
  140.                 node = rightRotate(node);
  141.             }
  142.             if(isRed(node.left) && isRed(node.right)){
  143.                 flipColors(node);
  144.             }
  145.             return node;
  146.         }
  148.         // 返回以node为根节点的红黑树中，key所在的节点
  149.         private Node getNode(Node node, K key) {
  151.             if (node == null)
  152.                 return null;
  154.             if (key.equals(node.key))
  155.                 return node;
  156.             else if (key.compareTo(node.key) < 0)
  157.                 return getNode(node.left, key);
  158.             else   // if(key.compareTo(node.key) > 0)
  159.                 return getNode(node.right, key);
  160.         }
  162.         public boolean contains(K key) {
  163.             return getNode(root, key) != null;
  164.         }
  166.         public V get(K key) {
  167.             Node node = getNode(root, key);
  168.             return node == null ? null : node.value;
  169.         }
  171.         public void set(K key, V newValue) {
  172.             Node node = getNode(root, key);
  173.             if (node == null)
  174.                 throw new IllegalArgumentException(key + " doesn't exist!");
  176.             node.value = newValue;
  177.         }
  179.         // 返回以node为根的红黑树的最小值所在的节点
  180.         private Node minimum(Node node) {
  181.             if (node.left == null)
  182.                 return node;
  183.             return minimum(node.left);
  184.         }
  186.         // 删除掉以node为根的红黑树中的最小节点,返回删除节点后新的红黑树的根
  187.         private Node removeMin(Node node) {
  188.             if (node.left == null) {
  189.                 Node rightNode = node.right;
  190.                 node.right = null;
  191.                 size--;
  192.                 return rightNode;
  193.             }
  194.             node.left = removeMin(node.left);
  195.             return node;
  196.         }
  198.         //没有实现remove中的调整
  199.         public V remove(K key) {
  200.             throw new UnsupportedOperationException("No remove in RBTree!");
  201.         }
  202.     }
  203. }