2-3查找树

定义

一棵2-3查找树或为一颗空树，或由以下节点组成：

• 2-节点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于该节点。
• 3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。

查找

对于查找操作和二叉查找树基本相同，递归比较要查找的键和树的根节点，小于就向左继续查找，大于就向右查找，相等就查找命中。不同的就是对于3节点，还要有中间节点的情况，在三节点两个键的大小之间的情况，要向中间子树递归。最后如果查找到叶节点的空连接就直接返回null。

插入

2-3树的插入相对来说是比较复杂的，因为它是保证树本身平衡性的关键。我们分几种情况来论述。

向2节点插入

插入先是要查找，查找到了就直接更新，如果未命中就插入新元素，插入新元素一定是在叶节点的空连接上，如果叶节点是一个2节点，那么就直接插入，让特们合成一个3节点。显然这时树高没有变化。示意图如下

这就是向一个2节点插入的情况。

向3节点插入

假如向一个3节点中插入，我们首先可以做的是像2节点一样把他们暂时合在一起形成一个4节点（有三个元素），然后再对这个4节点进行分解，将中间的元素插入他们的父元素剩下两个元素变成两个2节点。注意： 只能是中间的元素拿上去，因为这样才能保证树的有序性，即左边和右边的元素相对于根元素的大小关系 ，然后再考察父节点，如父节点原来是一个2节点，那么此时直接插入将其变成一个3节点，插入操作就完成了。如果原来父节点就是一个3节点，那么依然可以再重复这个过程，不断将中间元素加入父节点，如果这个过程持续到了根节点，那么我们就分裂形成的一个暂时的4节点的根节点，得到三个2节点，同时整个的树高增加1。

上图为根节点分裂的示意图

这种插入相当于把元素插入这个会引起树的高度变化的不利因素放在3节点中储存起来，随着3节点的插入将这种不利因素不断传导至根节点，然后通过根节点的分裂将整个的树高加1，可以看出，3节点以及相关的插入方法是保证平衡性的关键，也可以看出2-3树的生长是从下往上通过根节点生长的。 2-3树就可以实现在最坏条件下也有对数性能。

2. 性质

2-3 查找树插入操作的变换都是局部的，除了相关的节点和链接之外不必修改或者检查树的其它部分，而这些局部变换不会影响树的全局有序性和平衡性。

2-3 查找树的查找和插入操作复杂度和插入顺序无关，在最坏的情况下查找和插入操作访问的节点必然不超过 logN 个，含有 10 亿个节点的 2-3 查找树最多只需要访问 30 个节点就能进行任意的查找和插入操作。

2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。

红黑树

参考

算法4上红黑树解释很好，插入时是当做2-3查找树来的，删除时当做2-3-4查找树来的

此时红链接就是2-3查找树的3节点，因此就有了到叶子黑链接数量一致的那种性质，

将红链接画平，此时就是个2-3树

颜色表示，每个结点都有只有一条指向自己的链接，将链接的颜色保存在结点中，如color，如果指向它的是红链接，就为true, 否则为false, 约定空链接为黑色

由此可得如下红黑树性质：

• 性质1. 节点是红色或黑色。
• 性质2. 根节点是黑色。
• 性质3 每个叶节点（NIL节点，空节点）是黑色的。
• 性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

前文已经提到3节点是实现平衡性的关键，这里我们用 红链接 即一条红色的左链接来表示3节点

而2节点就用普通的黑色连接来表示。
那么一棵红黑树应该是完美黑色平衡的，即从任意空连接出发到根节点所经历的黑连接数目应该是相同的。再加入一个条件： 没有任意一个节点同时和两个红链接相连 ，那么此时红黑树就可以和2-3树一一对应。

节点代码

​

    private static final boolean RED = true;//定义RED为true
        private static final boolean BLACK = false;
        private Node root;
        private class Node{
            Key key;
            Value value;
            int N;
            Node left, right;
            boolean color;//表示颜色 
    
            Node(Key key, Value value,int N,boolean color){
                this.key = key;
                this.value = value;
                this.N = N;
                this.color = color;
            }
        }
        private boolean isRed(Node x){
            if (x==null) return false;
            return x.color == RED;
        }

我们在这里加入了一个表示颜色的布尔变量。这里的一个关键是一个节点的颜色指的是指向这个节点的连接的颜色。

旋转

旋转是一项非常重要的操作。我们在不改变树的有序性的情况下，将某个红链接从左链接变成右链接，或者从右链接变成左链接，这在处理一些情况比如对应于2-3树中向3节点插入元素的时候，更新整个树是很有用的。

代码在图中显示的有，所以不再重复写一遍。

还有个flipColors()的操作

可以看出这个函数就对应于2-3树中将中间元素插入父节点的操作，因为它把原来的两条红链接变成黑链接，相当于分裂成了两个2节点，而中间元素因为颜色是红的，所以就加入了父节点。flipColors()在后面还有其他的作用，所以在这里我给出它的最终形式。

​

    private void flipColors(Node h){
            h.color = !h.color;
            h.left.color = !h.left.color;
            h.right.color = !h.right.color;
        }

其实就是对颜色求反，这种形式显然是包容上图中的那种形式的。
注意：根节点都是黑色的

查找

红黑树的查找算法和二叉查找树的查找算法是完全一样的，也就是说，对于查找算法来说，红黑树中节点或者说链接的颜色是没有用到的，但是没有关系，虽然红黑树只是黑链接平衡，但是即使不考虑颜色的查找，整个树也不会出现像二叉树里面那种最极端的情况，所以性能依然是有保障的。

插入

红黑树的插入的算法是比较复杂的，对于2-3树来说相对较简单，但是在具体实现的时候，每个3节点中是有着具体结构的，那么我们在插入后就要调节这些具体的结构，才能实现2-3树中的功能。

向2节点插入

在2-3树中向2节点插入非常简单，直接合并成一个3节点就行。但是具体实现时，因为相对于父节点可能有大有小，那么在插入的时候就可能在父节点的左边或者右边，而红链接只能是左链接，那么当在右边插入的时候，就需要进行旋转操作将右链接变成左链接。

向3节点插入

向3节点插入就更加复杂了，因为此时不仅有插入方向的问题，还有父节点也是红色的问题，我们要调整几个节点的结构，实现2-3树中将中间节点插入到父节点的操作。这里主要分三种情况。

1 larger

如果插入后一个节点的两个子节点都是红色的，那么我们通过flipColors()可以很容易的实现2-3树中将中间节点插入父节点，两边节点独立成两个2节点，同时保持有序性（这里默认中间节点是黑色的，因为默认在插入之前整个树是有序的，这个可以通过正确的插入来保证）。

2 smaller

第二种情况下，需要先将第一个红链接进行右旋转，这样就变成了第一种情况，可以按照情况1 处理

3 betweeen

第三种情况下，需要先将下面的红链接进行左旋转就变成了第二种情况，然后就可以按照第二种情况处理

上图从左到右分别对应1，2，3三种情况。通过处理以上三种情况，我们就可以将红黑树的插入和2-3树的插入算法一一对应起来。下面是插入的代码。

​

    public void put(Key key,Value value){
            root = put(root,key, value);
    //查找键值，找不到就新建一个
            root.color = BLACK;
        }
        private Node put(Node h,Key key, Value value){
            if (h==null) return new Node(key, value, 1, RED);
            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))    flipColors(h);
    
            h.N = size(h.left)+size(h.right)+1;
    //更新走过的节点的N值
            return h;
        }

这里面值得注意的一点就是那三行if条件句，因为是放在递归语句之后的，所以是相当于沿着树往下走到底或者找到相等值，处理完再返回的时候运行的，可以看到这三句刚好可以将情况三处理完成，同时也容易检验，这个语句是完全可以兼容前两种情况。所以不断再返回根节点的过程运行这三句，相当于2-3树中把可能的多余节点移到。节点的过程。最后树是平衡的。

删除

删除最小值最大值和删除

删除比较麻烦，我们先考虑删除最小值，当我们删除一个3节点中的元素的时候倒还好，直接删除之后留下了一个2节点，树的平衡性没有发生变化。但是直接删除2节点会造成树的高度的变化。所以，我们还是要处理一下，从上往下进行变换，最终的目标就是保证在删除的时候当前节点不只是一个2节点。

删除最小值

最小值在最左边，我们沿着左边下去的时候需要合并三个2节点形成一个4节点，或者右边是三节点的话从右边节点“借”一个形成一个3节点或者4节点，这样就能保证当前节点大于2节点

删除最大值

删除最大值和删除最小值类似

分析

注意红黑树不是完全平衡的，是红链接变平后才是平衡的，也就是说黑结点是平衡的，加入红结点后就不平衡了

不用严格控制高度，使得插入效率更高？

红黑树相比于AVL树，牺牲了部分平衡性，以换取删除/插入操作时少量的旋转次数，整体来说，性能优于AVL树。