红黑树

什么是红黑树

红黑树是一种常见的自均衡二分搜寻树，罕用于关联数组、字典，在各种语言的底层实现中被广泛应用。

满足红黑树的五个性质

每个节点是红色或者是彩色
根节点是彩色
每一个叶子节点（最初的空节点）是彩色
如果一个节点是红色的，那么它的孩子节点都是彩色的
从任意一个节点到叶子节点，通过的彩色节点是一样的

2-3树的定义

红黑树和2-3树有相似之处，咱们先理解一下什么是2-3树

满足二分搜寻树的根本性质，然而2-3树并不是二叉树

2-3树有两个节点，一个能够寄存1个元素，一个能够寄存2个元素

满足2-3树的三个性质

满足二叉搜寻树的性质
节点能够寄存一个或两个元素
每个节点有两个或三个子节点

每个节点都有2个子节点或者3个子节点，所以就叫做2-3树

右边节点都比42小，而左边节点都比42大，所以是满足二分搜寻树的性质。留神，13和33这个节点两头是18，是比17大同时比33小。

2-3树的相对平衡性

对于2-3树来说任意一个节点，左右子树的高度肯定是相等的，而相似像AVL这种均衡二叉树左右子树的高度相差不超过1。

而2-3树是如何维持相对平衡性，就要从它的增加操作说起。

对于一颗空树咱们增加一个节点42，他既是根节点也是叶子节点，这个时候如果咱们想再增加一个节点37应该增加到那里呢？

按均衡二叉树构造的逻辑来讲37比42小，所以增加到42的左孩子的地位。

然而在2-3树的中并不是这样的，

在2-3中咱们仍然是从根节点登程，请留神在2-3树中新的节点永远不会增加进空的地位

发现42节点的左子树为空，2-3树就会找到最初一个叶子节点上也就是42的地位，这时候37就会和42进行交融，从一个2节点变为了3节点。这个时候还是一颗相对均衡的二叉树。

如果这个时候咱们再增加一个12节点的话，因为12节点比37小，所以去找37的左孩子，然而咱们曾经晓得，37的左孩子为空，而2-3并不会将新的节点增加到空的地位中去，这个时候咱们就会变成4节点！

然而在2-3中最多反对3个节点所以这个时候就会进行决裂，同时放弃相对均衡。

如果这个时候咱们再增加一个18节点，咱们能够很分明的晓得18会找到12节点然而12节点的子节点都为空，所以18就会和12节点进行交融。

如果这个时候咱们再增加一个6节点，大家很分明的晓得是会和12节点、18节点进行交融，这个时候变成了4节点，所以要进行决裂成为下图这样。

然而！这样咱们就不是相对均衡的二叉树了！

这个时候就须要咱们12节点去找他的父节点，发现12的父节点37是一个2节点，这个时候就简略了，咱们只须要让12和37节点进行交融为3节点，而后让6变成12和37的左孩子，让18节点变成两头孩子节点即可！

这个时候咱们顺次退出5和11节点，就会变成下图这样。

因为不满足2-3树的性质，所以咱们还是将他们进行决裂。

然而这个时候又不是相对均衡了，所以咱们须要让6去找父亲节点，然而父亲节点曾经是3节点了，不过没关系，咱们照样把他交融进去成下图这样。

这个时候咱们须要进行决裂，咱们须要把5和11别离放在6的左孩子和右孩子的地位，37也同理，造成下图这样。仍然放弃着相对平衡性。

其实咱们能够分为两种状况去了解，一种就是以后节点为3节点而父节点为2节点。

另一种就是以后节点为3节点，父节点也为3节点的状况。

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

在2-3树种，咱们能够示意2个节点和3个节点。

在红黑树中，咱们能够这样示意，而后用红色的线来示意bc是交融的，同时b是比c小的。因为红色节点是由3节点拆分而来，因而所有的红色节点都只会呈现在左子树上。

在下图中只有6和17和66是红色节点，咱们很容易得悉，因为他们都是3节点。

如果形象的话能够红色节点上移一下，咱们能够看到其实是和2-3树是一样的。

放弃根节点为彩色和左旋

在下图上，咱们晓得最初决裂当前，6持续会向上进行交融，咱们晓得向上交融的节点肯定是红色的，所以咱们晓得6是红色的，但发现曾经没有父亲节点的时候，咱们将6变为彩色。

最开始的时候咱们想增加一个42的话，咱们间接让42当根节点就好了，而后咱们须要让42变为彩色节点。

这个时候咱们增加一个37，能够间接放入到42左孩子的地位。

然而，如果咱们要插入的节点为根节点的右孩子的节点的时候，咱们须要进行左旋。

伪代码如下：

node.right = x.left;x.left = node;x.color = node.color;node.color = red;

Java代码如下：

    //   node                     x    //  /   \     左旋转         /  \    // T1   x   --------->   node   T3    //     / \              /   \    //    T2 T3            T1   T2    private Node leftRotate(Node node){        Node x = node.right;        node.right = x.left;        x.left = node;        x.color = node.color;        node.color = RED;        return x;    }

色彩翻转和右旋

最开始的时候咱们想增加一个42的话，咱们间接让42当根节点就好了，而后咱们须要让42变为彩色节点。

这个时候咱们增加一个37，能够间接放入到42左孩子的地位。

如果这时候咱们再向红黑树中退出66节点，会变成如下图这样。

相应的在2-3树中是这个样子。

在红黑树中红色节点的意思就是和父节点是交融在一起的。

而37和66都是红色节点，阐明它们都和父亲节点是交融在一起的。

在2-3树中，咱们解决4节点的时候会进行决裂，决裂为3个2节点。

然而在红黑树中其实彩色节点就是2个节点，咱们不须要进行旋转操作，咱们只须要让37和66进行变色为彩色，就和2-3树中节点的性质是一样的了。

在2-3树中，咱们须要持续让42节点向下来找父亲节点进行交融，相应的在红黑树中咱们只须要让42变为红色即可。

这个就是色彩翻转（flipColors）

     //色彩翻转    private void flipColors(Node node){        node.color = RED;        node.left.color = BLACK;        node.right.color = BLACK;    }

另外一种状况就是，咱们树增加成这个样子。咱们增加了12节点，其实能够了解为它们是交融在一起的。在2-3树种就是4节点，而后将它进行决裂。

然而在红黑树中咱们怎么变成这个样子呢？其实很简略，咱们只须要进行右旋转即可。

为了不便了解，咱们引入T1和T2虚构节点来演示。

咱们将x的右节点t1放到node的左孩子上，而后将node放在x的右孩子的地位即可。

别忘了，在这个时候node(42)节点其实是交融在x(37)节点上的，所以它要改为红色，37要改为彩色。

对应的伪代码：

node.left = t1;x.right = node;x.color = node.color;node.color = red;

最终咱们就能够失去和2-3树结构一样的红黑树了。

    //       node                            x    //       / \                           /   \    //      x   T2     向右旋转 (y)        y     node    //     / \       - - - - - - - ->          / \    //    y   T1                              T1  T2    private Node rightRotate(Node node){        Node x = node.left;        node.left = x.right;        x.right = node;        x.color = node.color;        node.color = RED;        return x;    }

在红黑树中增加新元素

其实还有一种状况咱们在后面没有讲到，就是在下图中增加一个元素40应该怎么做。

依据二分搜寻树的性质，咱们会将40增加进37的右孩子的地位。

然而这个时候曾经毁坏了红黑树的性质，所以咱们须要进行左旋。

这个时候咱们还须要进行右旋。

而后咱们须要将40变彩色，42变为红色。

最初咱们进行色彩翻转即可维持红黑树的性质。

总结图片如下：

如果咱们增加的第三个元素是最小的话，咱们能够间接从右旋开始。

反之咱们增加的如果是最大的元素，咱们能够间接进行色彩翻转。

    // 判断节点node的色彩    private boolean isRed(Node node){        if(node == null) {            return BLACK;        }        return node.color;    }    //   node                     x    //  /   \     左旋转         /  \    // T1   x   --------->   node   T3    //     / \              /   \    //    T2 T3            T1   T2    private Node leftRotate(Node node){        Node x = node.right;        node.right = x.left;        x.left = node;        x.color = node.color;        node.color = RED;        return x;    }    //色彩翻转    private void flipColors(Node node){        node.color = RED;        node.left.color = BLACK;        node.right.color = BLACK;    }    //       node                            x    //       / \                           /   \    //      x   T2     向右旋转 (y)        y     node    //     / \       - - - - - - - ->          / \    //    y   T1                              T1  T2    private Node rightRotate(Node node){        Node x = node.left;        node.left = x.right;        x.right = node;        x.color = node.color;        node.color = RED;        return x;    }    // 向红黑树中增加新的元素(key, value)    public void add(K key, V value){        root = add(root, key, value);        //根节点为彩色        root.color = BLACK;    }    // 向以node为根的红黑树中插入元素(key, value)，递归算法    // 返回插入新节点后红黑树的根    private Node add(Node node, K key, V value){        if(node == null){            size ++;            return new Node(key, value); //默认插入红色节点        }        if(key.compareTo(node.key) < 0) {            node.left = add(node.left, key, value);        } else if(key.compareTo(node.key) > 0) {            node.right = add(node.right, key, value);        } else // key.compareTo(node.key) == 0        {            node.value = value;        }        //右孩子为红色，左孩子为彩色，进行左旋        if(isRed(node.right) && !isRed(node.left)){            node = leftRotate(node);        }        // 左孩子为红色，并且左孩子的左孩子也是红色，进行右旋        if(isRed(node.left) && isRed(node.left.left)){            node = rightRotate(node);        }        //色彩翻转        if(isRed(node.left) && isRed(node.right)){            flipColors(node);        }        return node;    }

工夫复杂度剖析

红黑树相比于AVL树，其实是就义了平衡性的，红黑树并不齐全满足均衡二叉树的定义，红黑树的最大高度达到了2logn的高度，红色节点影响了红黑树的的平衡性。红黑树尽管就义了肯定的查问性能，然而在增删改操作的性能失去了补救，红黑树的综合性能还是要优于AVL树的。