4.11.1、平衡树定义

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。

4.11.2、2-3查找树

4.11.2.1、2-3查找树定义

2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。

一棵2-3查找树要么为空，要么满足下面的两个要求：

• 2-结点：
  • 含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都要小于该结点，右链接指向的2-3树中的键都大于该结点
• 3-结点：
  • 还有两个键(及其对应的值)和三条链，左链接指向2-3树中的键都要小于该结点，中链接指向的2-3树中的键都位于该结点的两个键直接，右链接指向2-3树中的键都大于该结点
    

一棵完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。

4.11.2.2、2-3查找树查找

要判断一个键是否存在树中，先将它和根节点中的键比较，如果它和其中任意一个相等，查找命中；否则就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找，如果找到了空连接上，查找未命中。

4.11.2.3、2-3查找树插入

• 向2-节点中插入新键：如果未命中查找结束于一个2-节点，直接将2-节点替换为一个3-节点，并将要插入的键保存在其中
  
• 向一颗只含3-节点的树中插入新键：先临时将新键存入唯一的3-节点中，使其成为一个4-节点，再将它转化为一颗由3个2-节点组成的2-3树，分解后树高会增加1
  
• 向一个双亲节点为2-节点的3-节点中插入新键：先构造一个临时的4-节点并将其分解，分解时将中键移动到双亲节点中(中键移动后，其双亲节点中的位置由键的大小确定)
  
• 向一个双亲节点为3-节点的3-节点中插入新键：一直向上分解构造的临时4-节点并将中键移动到更高层双亲节点，直到遇到一个-2节点并将其替换为一个不需要继续分解的3-节点，或是到达树根(3-节点)
  
• 分解根节点：如果从插入节点到根节点的路径上全是3-节点，根将最终被替换为一个临时的4-节点，将临时的4-节点分解为3个2-节点，分解后树高会增加1
  

4.11.2.4、2-3查找树性质

一棵完全平衡的2-3树具有如下性质：

• 任意空链接到根结点的路径长度都是相等的
• 4-结点变换为3-结点时，树的高度不会发生变换，只有当根结点时临时的4-结点，分解根结点时，树高+1
• 2-3树与普通二叉树最大的区别在于，普通的二叉树是自顶向下生长，而2-3树是自底向上生长

4.11.2.5、2-3查找树实现

2-3查找树实现起来比较复杂，在某些情况插入后的平衡操作可能会是的效率降低。但是2-3查找树作为一种比较重要的思想和思路对后面的红黑树、B树和B+树非常重要。

4.11.3、红黑树

4.11.3.1、红黑树定义

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树：

• 红链接均为左链接
• 没有任何一个结点同时和两条红链接相连
• 该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同

红黑树和2-3树的关系：如果我们将一棵红黑树中的红链接画平，那么所有的空链接到根节点的距离都是相同的。如果我们将由红链接相连的两个2-结点合并，得到的就是一棵2-3树。相反，如果将一棵2-3树中的3-结点画作由红色左链接相连的两个2-结点，那么不会存在能够和两条红链接相连的结点，且树必然是完美黑色平衡的，因为黑链接即为2-3树中的普通链接。

4.11.3.2、红黑树结点API设计

红黑树每个结点都只会有一条指向自己的链接（从它的父结点指向它），我们可以在之前的Node结点中添加一个布尔类型的变量color来表示链接的颜色，如果指向它的链接是红色，则该值为true，如果为黑色，该值为false。

API设计

4.11.3.3、红黑树平衡化

在对红黑树进行一些增删改查的操作后，有可能会出现红色的右链接或者两天连续的红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。

• 左旋：当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋
  • 旋转过程：
    • 让x的左子结点变为h的右子结点：h.right=x.left;
    • 让h成为x的左子节点：x.left = h;
    • 让x的color属性值变为h的color属性值：x.color = h.color;
    • 让h的color属性值变为红色：h.color = true;
      
• 右旋：当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋
  • 旋转过程：
    • 让x的右子结点变为h的左子结点：h.left=x.right;
    • 让h成为x的右子节点：x.right = h;
    • 让x的color属性值变为h的color属性值：x.color = h.color;
    • 让h的color属性值变为红色：h.color = true;
      
      从上面可以发现，其实右旋后不满足红黑树的定义，右边还是出现了红链接，那么后面我们可以通过颜色变化进行解决。

4.11.3.4、红黑树插入

• 向单个2-结点中插入新键
  • 如果新键小于当前结点的键，只需要新增一个红色的节点即可，新的红黑树和单个3-结点完全等价
    
  • 如果新键大于当前结点，那么新增的红色结点将会产生一条红色的右链接，此时需要通过左旋，把红色的右链接变成左链接，插入操作才算完成。形成的新的红黑树依然和3-结点等价，其中含有两个键，一条红色的链接
    
• 向底部的2-结点插入新键
  • 用和二叉查找树相同的方式向一棵红黑树中插入一个新键，会在树的底部新增一个结点（可以保证有序性），唯一区别的地方就是我们会用红链接将新结点和父结点相连，然后需要进行左旋。
    
• 颜色反转
  • 当一个结点的左子结点和右子结点的color都是红色是，也就是出现了临时的4-结点，此时值需要把左子结点和右子结点的颜色变为黑色，同时让当前结点的颜色变为red即可。
    
• 向一棵双键树(即一个3-结点)中插入新键
  • 新键大于原树中的两个键
    
  • 新键小于原树中的两个键
    
    
  • 新键介于两个键之间
    
    

4.11.3.5、红黑树API设计

4.11.3.6、红黑树实现

实现类

package cn.test.algorithm.datastruct;

public class RedBlackTree<Key extends Comparable<Key>, Value> {
    private Node root;//根结点
    private int N;//元素个数
    private static final boolean RED = true;//红链接
    private static final boolean BLACK = false;//黑链接

    //结点类
    private class Node {
        public Key key;
        public Value value;
        public Node left;
        public Node right;
        public boolean color;

        public Node(Key key, Value value, Node left, Node right, boolean color) {
            this.key = key;
            this.value = value;
            this.right = right;
            this.left = left;
            this.color = color;
        }
    }

    //获取元素个数
    public int size() {
        return N;
    }

    //判断当前结点是否是红结点
    public boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }

    //左旋转
    private Node rotateLeft(Node h) {
        //获取h结点的右子结点，表示为x
        Node x = h.right;

        h.right = x.left;

        x.left = h;

        x.color = h.color;

        x.color = RED;

        return x;
    }

    //右旋转
    private Node rotateRight(Node h) {
        //获取h结点的右子结点变为x
        Node x = h.right;

        h.left = x.right;

        x.right = h;

        x.color = h.color;

        h.color = RED;

        return x;
    }

    //颜色反转
    private void filpColors(Node h) {
        //当前结点变为红色
        h.color = RED;
        //当前结点的左右子结点编程黑色
        h.right.color = BLACK;
        h.left.color = BLACK;
    }


    //在整个树上插入
    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;//根结点始终为黑色
    }

    //在指定结点插入
    private Node put(Node h, Key key, Value value) {
        //如果h为空，直接返回一个松散的节点节课
        if (h == null) {
            N++;
            return new Node(key, value, null, null, RED);
        }

        //比较h结点的键和key的大小
        int cmp = key.compareTo(h.key);
        if (cmp < 0) {
            h.left = put(h.left, key, value);
        } else if (cmp > 0) {
            h.right = put(h.right, key, value);
        } else {
            h.value = value;
        }

        //进行左旋
        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)) {
            filpColors(h);
        }
        return h;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (x == null) {
            return null;
        }

        //比较x结点的键和key的大小
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return x.value;
        }
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.RedBlackTree;

public class RedBlackTreeTest {
    public static void main(String[] args) {
        RedBlackTree<String, String> tree = new RedBlackTree<>();

        tree.put("1", "张三");
        tree.put("3", "李四");
        tree.put("2", "王五");

        System.out.println(tree.get("1"));
        System.out.println(tree.get("2"));
        System.out.println(tree.get("3"));

        System.out.println(tree.size());
    }
}

运行结果

张三
王五
李四
3