红黑树

 红黑树

一、 二叉查找树

二叉查找树就是以二分法思想为指导，设计出来的一种快速查找树，二叉查找树保证以下特性：

• 每一个节点关键字只会在树中出现一次。
• 任何一个节点，如果它有子节点，那么左侧的关键字一定比较小，右侧的关键字一定比较大。

基于这种结构，搜索时每次从根节点开始查找，就算找到叶子结点，也只进行了log₂n次比较，效率明显高于顺序/倒序遍历。

二、 平衡二叉树（AVL树）

极端情况下的二叉查找树可能只有左子树，进而退化为链表结构。为应对这种情况，引入了平衡二叉树：

• 它是一个空树或二叉查找树
• 左右两个子树的高度差的绝对值不超过1
• 左右两个子树都是一颗平衡二叉树

平衡二叉树的查找时间复杂度不会超过O(log₂n)，平衡二叉树在做插入或删除的时候，需要通过一系列的旋转（左旋、右旋）操作（自平衡），让其始终满足平衡二叉树的条件。

三、2-3树

一颗2-3树或为一颗空树，或有以下节点组成： 

　　2-节点，含有一个元素和两个子树（左右子树），左子树所有元素的值均小于它父节点，右子树所有元素的值均大于它父节点；

　　3-节点，还有两个元素和三个子树（左中右子树），左子树所有元素的值均小于它父节点，中子树所有元素的值都位于父节点两个元素之间，右子树所有元素的值均大于它父节点；

　　子树也是空树、2-节点或者3-节点；

　　没有元素相等的节点。

　　2-3树能够保证在插入元素之后，树依然保持平衡状态，它的最坏情况下所有子节点都是2-节点，树的高度为lgN，相比于我们普通的二叉查找树，最坏的情况下树的高度为N，确实保证了最坏情况下的时间复杂度，但是2-3树实现起来过于复杂，所以我们经常使用一种使用2-3树思想进行简单实现的红黑树来替代。

四、 红黑树

1，算法思想一

　　红黑树主要是对2-3树进行编码，红黑树的基本思想是用标准的二叉查找树（完全由2-节点构成）和一些额外的信息（替换3-节点）来表示2-3树。我们将树的链接分为两种：

　　红链接：将两个2-节点连接起来构成一个3-节点。

　　黑链接：是2-3树中的普通链接。

　　确切的说，3-节点表示为由一条左斜红色链接相连的两个2-节点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。

2，算法思想二

红黑树也是一种自平衡二叉树，但在统计上，它的性能要优于平衡二叉树。

1)      节点是红色或者黑色

2)      根节点是黑色

3)      每个叶子结点(NIL节点，虚拟的外部空节点，不真实存在)为黑色

4)      每个红色节点的两个子节点都是黑色

5)      从任一节点到其每个叶子结点的所有路径都包含相同数目的黑色节点。

根据这些性质，可以得出推论：从根到叶子的最长距离，不超过最短距离的两倍。 因为性质5约束了左支和右支黑色节点数目一定相等，性质4又约束了不会有两个相邻的红色节点，最长路径为红黑相间的节点序列，红色节点数最多为黑色节点数-1，因此红色+黑色<黑色*2。

对红黑树进行增删操作，会是树结构违背这些性质，因此像平衡二叉树一样需要在插入时进行自平衡操作。

        红黑树的节点除了和其它二叉树一样的left/right/parent节点外，还有颜色red/black属性和是否为叶子节点标记isNil。

3，算法流程（插入）

由于性质5的约束，所有新插入的节点，都是红色节点，假设插入节点为N，父节点为P，祖父节点为G，叔节点为U，定义一个函数f(A,B)，函数返回A节点相对B节点的位置（left/right）。

1)      如果该树为空树，那么N节点为根节点，根据性质2变色为黑。

2)      如果P为黑色，那么新增节点为红色，不会违背性质5，满足红黑树性质，不做任何操作。

3)      如果P为红色，那么分多种子情况：

• U为红色，把P、U改为黑色、G改为红色。G改为红色后，由于G的父节点也可能是红色，从而违背性质4，这时把G节点视为新插入的节点，递归进行插入操作。

 

• U为黑色，且f(P,G)=f(N,P)，则将P、G变色，对G为根节点的树做单向旋转（f(P,G)=L则LL右旋转，为R则RR左旋转），旋转是为了保证子树上黑色节点总数一致。

 

• U为黑色，且f(P,G)!=f(N,P)，对P进行一次单向旋转，转化为f(P,G)=f(P,N)情况。

 

总结：红黑树的插入过程主要操作有两种。

变色，用于调整两个红色节点相邻的情况，以适应性质4

旋转，用于调整左右子树黑色节点数目不等的情况，以适应情况5

4，算法实现

  1 package io.guangsoft;
  2 
  3 public class RedBlackTree<Key extends Comparable, Value> {
  4     private class Node<Key, Value> {
  5         //存储键
  6         public Key key;
  7         //存储值
  8         public Value value;
  9         //记录左节点
 10         public Node left;
 11         //记录右节点
 12         public Node right;
 13         //由其父节点指向它的颜色
 14         public boolean color;
 15         public Node(Key key, Value value, Node left, Node right, boolean color) {
 16             this.key = key;
 17             this.value = value;
 18             this.left = left;
 19             this.right = right;
 20             this.color = color;
 21         }
 22     }
 23     //记录根节点
 24     private Node root;
 25     //记录树中元素个数
 26     private int n;
 27     //红色链接标志
 28     private static final boolean RED = true;
 29     //黑色链接标志
 30     private static final boolean BLACK = false;
 31     //获取树中元素个数
 32     public int size() {
 33         return n;
 34     }
 35     //判断当前节点的父指向链接是否为红色
 36     private boolean isRed(Node x) {
 37         if(x == null) return false;
 38         return x.color == RED;
 39     }
 40     //左旋调整
 41     private Node rotateLeft(Node h) {
 42         //获取h节点的右子节点，表示为x
 43         Node x = h.right;
 44         //让x节点的左子节点成为h节点的右子节点
 45         h.right = x.left;
 46         //让h成为x节点的左子节点
 47         x.left = h;
 48         //让x节点的color属性等于h节点的color属性
 49         x.color = h.color;
 50         //让h节点的color属性变为红色
 51         h.color = RED;
 52         return x;
 53     }
 54     //右旋调整
 55     private Node rotateRight(Node h) {
 56         //获取h节点的左子节点，表示为x
 57         Node x = h.left;
 58         //让x节点的右子节点成为h节点的左子节点
 59         h.left = x.right;
 60         //让h节点成为x节点的右子节点
 61         x.right = h;
 62         //让x节点的color属性等于h节点的color属性
 63         x.color = h.color;
 64         //让h节点的color属性为红色
 65         h.color = RED;
 66         return x;
 67     }
 68     //颜色反转，相当于完成拆分4-节点
 69     private void flipColors(Node h) {
 70         //当前节点变为红色
 71         h.color = RED;
 72         //左子节点和右子节点变成黑色
 73         h.left.color = BLACK;
 74         h.right.color = BLACK;
 75     }
 76     //在整个树完成插入操作
 77     private void put(Key key, Value val) {
 78         root = put(root, key, val);
 79         //根节点的颜色总是黑色
 80         root.color = BLACK;
 81     }
 82     //在指定树中完成插入操作，并返回添加元素后的新树
 83     private Node put(Node h, Key key, Value val) {
 84         //判断h是否为空，如果为空直接返回一个红色节点
 85         if(h == null) {
 86             n++;
 87             return new Node(key, val, null, null, RED);
 88         }
 89         //比较h节点的键和key的大小
 90         int cmp = key.compareTo(h.key);
 91         if(cmp < 0) {
 92             //继续往左
 93             h.left = put(h.left, key, val);
 94         } else if(cmp > 0) {
 95             //继续往右
 96             h.right = put(h.right, key, val);
 97         } else {
 98             //发生值的替换
 99             h.value = val;
100         }
101         //进行左旋，当当前节点h的左子节点为黑色，右子节点为红色，需要左旋
102         if(isRed(h.right) && !isRed(h.left)) {
103             h = rotateLeft(h);
104         }
105         //进行右旋，当当前节点的左子节点和左子节点的左子节点都为红色，需要右旋
106         if(isRed(h.left) && isRed(h.left.left)) {
107             h = rotateRight(h);
108         }
109         //颜色反转，当前节点的左子节点和右子节点都为红色时，需要颜色反转
110         if(isRed(h.left) && isRed(h.right)) {
111             flipColors(h);
112         }
113         return h;
114     }
115     //根据key，从树中找出对应值
116     public Value get(Key key) {
117         return get(root, key);
118     }
119     //从指定树x中，找出key的对应值
120     private Value get(Node x, Key key) {
121         if(x == null) {
122             return null;
123         }
124         //比较x节点的键和key的大小
125         int cmp = key.compareTo(x.key);
126         if(cmp < 0) {
127             return (Value) get(x.left, key);
128         } else if(cmp > 0) {
129             return (Value) get(x.right, key);
130         } else {
131             return (Value) x.value;
132         }
133     }
134     //主类
135     public static void main(String args[]) {
136         //创建红黑树
137         RedBlackTree<String, String> redBlackTree = new RedBlackTree<>();
138         //往树中插入元素
139         redBlackTree.put("A", "黑暗森林");
140         redBlackTree.put("B", "逻辑传");
141         redBlackTree.put("C", "章北海传");
142         //从树中获取元素
143         System.out.println(redBlackTree.get("A"));
144         System.out.println(redBlackTree.get("C"));
145         System.out.println(redBlackTree.get("B"));
146     }
147 }

5，算法分析

通过"数学归纳法"开始论证高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。

(01) 当树的高度h=0时，
    内节点个数是0，bh(x) 为0，2^bh(x)-1 也为 0。显然，原命题成立。

(02) 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2^bh(x)-1-1。这个是根据(01)推断出来的！

    下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2^bh(x)-1”。

    当树的高度为 h 时，
    对于节点x(x为根节点)，其黑高度为bh(x)。
    对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。
    根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2^bh(x)-1-1 个"；

    所以，节点x所包含的节点至少为 ( 2^bh(x)-1-1 ) + ( 2^bh(x)-1-1 ) + 1 = 2^^bh(x)-1。即节点x所包含的节点至少为 2^bh(x)-1。
    因此，原命题成立。

    由(01)、(02)得出，"高度为h的红黑树，它的包含的内节点个数至少为 2^^bh(x)-1个"。
    因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

结论

　　红黑树的时间复杂度为: O(lgn)

6，算法应用

红黑树在HashMap中的应用

1)      treeifyBin方法

当table容量小于最小建树容量64时，调整table大小。最小建树容量的意义在于，重新规划table大小和树化某个哈希桶（哈希值对应下标的容器），都可以提高查询效率。这里取一个经验数字64作为衡量，当table容量超过64，调用TreeNode.treeify方法把链表转化为红黑树。

2)      putTreeVal方法

执行二叉树查找，每一次都比较当前节点和待插入节点大小，如果带插入节点较小，那么从当前节点左子树查找，否则从右子树查找，这种查询效率等同于二分法，时间复杂度为O(log₂n),待找到空位可以存放节点值之后，执行两个方法。

balanceInsertion(root,x)，平衡插入，一方面把节点插入红黑树中，一方面对红黑树进行变换使之平衡。

moveRootToFront(table, root)由于红黑树重新平衡之后，root节点可能发生了变化，table里记录的节点不再是红黑树的root，需要重置。

3)      balanceInsertion方法

此方法即上边插入分析的代码实现。

4)      rotateLeft和rotateRight方法

左旋与右旋，改变节点左右子树引用即可实现。