红黑树剖析

学习Java 的过程中，很多时候都会涉及到红黑树，HashMap、ConcurrentHashMap 在 jdk1.8 版本中，就引入了红黑树节点，以前一直没有去研究，现在打算来仔细研究下。

起点-二叉查找树

二叉查找树又名二叉排序树、二叉搜索树

二叉查找树的特点是

1. 如果左子树不为空，左子树的所有节点均小于它的根节点的值
2. 如果右子树不为空，右子树的所有节点均大于它的根节点的值
3. 左右子树也分别是二叉排序树

二叉查找数的缺点

如果根节点足够大，它的左子树，十分臃肿；如果根节点足够小，它的右子树十分臃肿。就跟一个独角兽。

引入红黑树

红黑树时间复杂度为O(logn) 且，一个含n个节点的红黑树的高度至多为 2log(n+1)

红黑树是一种平衡的二叉查找树，这的平衡指的是，不会像二叉树一样成为一个独角兽。

特性

1. 节点要么是红色要么是黑色
2. 根节点是黑色
3. 每个叶子的节点都是黑色的空节点(NULL)
4. 每个红色节点的两个子节点都是黑色的(红的子节点为黑)
5. 从任意节点到其每个叶子节点的所有路径都包含相同的黑色节点数

在红黑树中：最常路径不会超过最短路径的两倍

分析左旋

左旋就是 将 x 的右子树绕 x 逆时针旋转，使得 x 的右子树成为 x 的父亲，同时修改相关节点的引用。反正就是要满足二叉查找树的属性

在网上找到了个动图，满分！

左旋伪代码：

LEFT-ROTATE(T, x)  
     y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式操作
     right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”，
     p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”
     p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
    
     if p[x] = nil[T]       
     then root[T] ← y        // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
     else if x = left[p[x]]  
		then left[p[x]] ← y // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
     else right[p[x]] ← y    // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
     
     left[y] ← x             // 将 “x” 设为 “y的左孩子”
     p[x] ← y                // 将 “x的父节点” 设为 “y”

分析右旋

右旋的过程是将 x 的左子树绕 x 顺时针旋转，使得 x 的左子树成为 x 的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。

在网上找到了个右旋的动图，满分啊！

右旋伪代码:

RIGHT-ROTATE(T, y)  
     x ← left[y]             // 前提：这里假设y的左孩子为x。下面开始正式操作
     left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”，
     p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”，
     p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
    
     if p[y] = nil[T]       
     then root[T] ← x                 // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
     else if y = right[p[y]]  
		then right[p[y]] ← x   // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
     else left[p[y]] ← x    // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
     
     right[x] ← y            // 将 “y” 设为 “x的右孩子”
     p[y] ← x                // 将 “y的父节点” 设为 “x”

put 插入节点过程

1. 将红黑树当做二叉查找数，将节点插入

   红黑树本身就是二叉查找树，我们往中插入数据不会影响二叉查找树的性质，而且左旋和右旋也不会影响二叉查找树的性质

2. 将插入的节点着色为红色

   为什么着色为红色？这样只可能违背 特性(如果一个节点是红色的，它的子节点必须是黑色的)。我们处理的情况就越少。

3. 通过一系列的旋转或着色操作等操作，使之重新成为一颗红黑树

性质T： 红下必为黑

一个清晰的递归算法呈现在我们面前：

1. 新增节点渲染成红色；
2. 如果它的父亲是红色，则违反了性质T；
3. 如果它的叔叔也是红色，则通过同时修改其父亲和叔叔的颜色为黑色来恢复性质T ；
4. 如果它的爷爷不是根节点，则有可能在另外的路径上再次违反性质T，于是我们把它的爷爷改成红色；
5. 可是如果他的太爷爷也是红色呢？很自然地，我们重新回到步骤2；
6. 不断循环，直到第二步满足就可以结束。

综述一下吧，大概就存在三种情况：

1. 当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。

   解决方法：

   • 将父节点设置为黑色
   • 将叔节点设置为黑色
   • 将祖父节点设置为红色
   • 将祖父节点设为当前节点，之后继续对当前节点进行操作

2. 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子

   解决方法：

   • 将父节点设置为当前节点
   • 以新的当前节点进行左旋

3. 当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子

   解决方法：

   • 将父节点设为黑色
   • 将祖父节点设为红色
   • 对祖父节点进行右旋

手撸个红黑树吧：

package lijun;

import lombok.Getter;

/**
 * Class lijun.RedBlackTree ...
 *
 * @author LiJun
 * Created on 2019/3/29
 */
public class RedBlackTree {
    // 红黑色着色
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private static final class TreeNode {
        int value;
        TreeNode parent;
        TreeNode left;
        TreeNode right;
        boolean color = BLACK;

        public TreeNode(int value, TreeNode parent) {
            this.value = value;
            this.parent = parent;
            this.left = this.right = null;
        }

        @Override
        public String toString() {
            return "value = " + value + " " + "color = " + (color == RED ? "red" : "block");
        }
    }

    @Getter
    private TreeNode root;
    /**
     * The number of nodes
     */
    private int size = 0;

    // 默认采用无参的构造方法

    /**
     * put
     *
     * @param value the value is what we want to insert
     */
    public boolean put(int value) {

        TreeNode t = root;
        // 如果根节点为空，初始化根节点的内容
        if (t == null) {
            root = new TreeNode(value, null);
            size = 1;
            return true;
        }
        // 如果根节点不为空
        TreeNode parent = null;
        while (t != null) {
            // 记录当前节点
            parent = t;
            if (t.value < value) {
                // 如果当前遍历的节点小于我们要插入的值，向右走
                t = t.right;
            } else if (t.value > value) {
                // 如果当前遍历的节点大于我们要插入的值，向左走
                t = t.left;
            } else {
                // 不允许插入同样的值
                return false;
            }
        }
        // 到这的时候，我们已经找到了改插入的位置了，t=null
        // 我们也记录了相应的parent位置
        // 这个时候的话，先创建一个节点吧,并将其着色为红
        TreeNode node = new TreeNode(value, parent);
        node.color = RED;
        // 这里判断下应该放在左，还是放在右
        if (parent.value > value) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        // 节点数加一
        size++;
        // 对树进行调整，使得满足红黑树特性
        fixAfterInsertion(node);
        return true;
    }
    
    /**
     * 当我们插入一个节点后，可能已经破坏了红黑树的特性
     * 这个时候我们需要重新调整树，使得满足红黑树特性
     *
     * @param node 节点
     */
    private void fixAfterInsertion(TreeNode node) {
        // 获取当前节点的父节点
        TreeNode parent = node.parent;
        // 如果父节点不为空，且颜色为红色
        while ((parent != null) && (RED == parent.color)) {
            // 获取祖父节点
            TreeNode grandfather = parent.parent;
            // 如果是左孩子
            if (parent == grandfather.left) {
                TreeNode uncle = grandfather.right;
                // uncle 存在为红
                if ((uncle != null) && (uncle.color == RED)) {
                    // 这里将父节点和叔节点设置为黑色
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    // 将祖父节点设置为红色
                    grandfather.color = RED;
                    // 将祖父节点设置为当前节点
                    node = grandfather;
                    parent = node.parent;
                } else {// uncle不存在或者为黑节点
                    if (node == parent.right) {
                        rotateLeft(parent);
                        TreeNode temp = parent;
                        node = parent;
                        parent = node;
                    }
                    // 将父节点设为黑色
                    // 将祖父节点设为红色
                    // 对祖父节点进行右旋
                    rotateRight(grandfather);
                    parent.color = BLACK;
                    grandfather.color = RED;
                }
            } else { // parent == grandfather.right，这里的处理和上面的大致一样
                TreeNode uncle = grandfather.left;
                // uncle 存在为红
                if ((uncle != null) && (uncle.color == RED)) {
                    parent.color = BLACK;
                    uncle.color = BLACK;
                    grandfather.color = RED;

                    node = grandfather;
                    parent = node.parent;
                } else {// uncle不存在或者为黑节点
                    if (node == parent.right) {
                        rotateRight(parent);
                        TreeNode temp = parent;
                        node = parent;
                        parent = node;
                    }
                    rotateLeft(grandfather);
                    parent.color = BLACK;
                    grandfather.color = RED;
                }
            }
        }
        root.color = BLACK;
    }

    /**
     * 右旋
     *
     * @param p 节点
     */
    private void rotateRight(TreeNode p) {
        if (p != null) {
            TreeNode l = p.left;
            p.left = l.right;
            if (l.right != null) {
                l.right.parent = p;
            }
            l.parent = p.parent;
            if (p.parent == null) {
                root = l;
            } else if (p.parent.right == p) {
                p.parent.right = l;
            } else {
                p.parent.left = l;
            }
            l.right = p;
            p.parent = l;
        }
    }

    /**
     * 左旋
     *
     * @param p node
     */
    private void rotateLeft(TreeNode p) {
        if (p != null) {
            TreeNode r = p.right;
            p.right = r.left;
            if (r.left != null) {
                r.left.parent = p;
            }
            r.parent = p.parent;
            if (p.parent == null) {
                root = r;
            } else if (p.parent.left == p) {
                p.parent.left = r;
            } else {
                p.parent.right = r;
            }
            r.left = p;
            p.parent = r;
        }
    }

    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        // 通过数组构造一颗树
        int[] array = {80, 40, 120, 20, 60, 100, 140, 10, 50, 90, 10, 30};
        for (int i = 0; i < array.length; i++) {
            tree.put(array[i]);
        }

        tree.preOrder(tree.getRoot());
        System.out.println("-----------------------------");
        tree.inOrder(tree.getRoot());
        // 得到的结果如下

        /*
value = 80 color = block
value = 40 color = red
value = 20 color = block
value = 10 color = red
value = 30 color = red
value = 60 color = block
value = 50 color = red
value = 120 color = red
value = 100 color = block
value = 90 color = red
value = 140 color = block
-----------------------------
value = 10 color = red
value = 20 color = block
value = 30 color = red
value = 40 color = red
value = 50 color = red
value = 60 color = block
value = 80 color = block
value = 90 color = red
value = 100 color = block
value = 120 color = red
value = 140 color = block
*/

    }


    /**
     * 在这里我将三种遍历都写出来了，我们稍后通过遍历构造出树，看是不是我们需要的
     *
     * @param node
     */
    public void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node);
        inOrder(node.right);

    }

    public void afterOrfer(TreeNode node) {
        if (node == null) {
            return;
        }
        afterOrfer(node.left);
        afterOrfer(node.right);
        System.out.println(node);
    }
}

remove 删除操作