红黑树

作者: 山东大葱哥 | 来源:发表于2019-07-13 00:27 被阅读38次

数据结构—树—红黑树
TreeMap
数据结构与算法-AVL 红黑树
[转载]红黑树
拿下红黑树
红黑树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除
Golang红黑树
数据结构红黑树添加、修改原理分析

红黑树首先是一种树形结构，同时又是一个二叉树（每个节点最多只能有两个孩子节点，左节点小于等于父节点，右节点大于父节点），为了保证树的左右孩子树相对平衡（深度相同），红黑树使用了节点标色的方式，将节点标记为红色或者黑色，在计算树的深度时只统计黑色节点的数量，不统计红色节点数量。

image.png

而保持左右子树深度相同的原因是减少树的最大深度，从而提高查询的效率，尽量维持左右子树的深度一致，避免某个子树深度过深的情况出现，如果某个子树深度过深，查找算法的时间复杂度就下降为链表的时间复杂度O(n)，为了保证左右子树的平衡，红黑树定义了一些规则或者特点来维持平衡。

主要特点（规则）

每个节点要么是黑色，要么是红色。（节点非黑即红）
根节点是黑色。
每个叶子节点（NULL）是黑色（为了简单期间，一般会省略该节点）。
如果一个节点是红色的，则它的子节点必须是黑色的。（也就是说父子节点不能同时为红色）
从一个节点到该节点的每一个叶子子孙节点的所有路径上包含相同数目的黑节点。（这一点是平衡的关键）
新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行操作。

红黑树必须保持上述特点，而在对红黑树进行添加或者删除操作时可能会破坏这些特点，所以红黑树采取了很多方式来维护这些特点，从而维持平衡。

HashMap在进行插入和删除时有可能会触发红黑树的插入平衡调整（balanceInsertion方法）或删除平衡调整（balanceDeletion ）方法，调整的方式主要有以下手段：左旋转（rotateLeft方法）、右旋转（rotateRight方法）、颜色反转（x.red = false、x.red = true），进行调整的原因是为了维持红黑树的数据结构。

左旋rotateLeft

将树以某个节点为中心向左进行旋转操作以保持树的平衡。如果下图所示：

image.png

左旋相当于以要旋转的节点C为中心（注意：A节点可以存在父节点，该左旋操作对A的父节点的结构几乎不影响，只只是影响父节点的子节点指向），将子树整体向左旋转，该节点变成子树的根节点（或者说替代A节点的位置，可以有父节点），原来的父节点A变成了C的左孩子，如果C有左孩子D，则D变为A的右孩子。当节点A向左旋转之后，C的左孩子D可以理解为因为重力作用掉到A的右孩子位置。经过左旋操作，A结点移到左边，A结点的右结点C来到了A的位置，并且C结点的左结点成为A结点的右结点。

对应到具体代码中，p即上图的A节点，r指向右孩子即C，rl指向右孩子的左孩子即D，pp为p的父节点。

        static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root,
                                                TreeNode<K, V> p) {
            //即将左旋的是p，r是p的右子树，如果p和r都不为空进行左旋
            TreeNode<K, V> r, pp, rl;
            if (p != null && (r = p.right) != null) {
                //1.r1是r的左子树，r1不为空，将他挂到p的右边。
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                //2.如果p的父节点为空，那么r就是根节点，并且标记为黑色
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                else if (pp.left == p)//p是父节点的左节点，那么r挂到pp的左子树
                    pp.left = r;
                else //p是父节点的右节点，那么r挂到pp的右子树
                    pp.right = r;

                // 3.最后把p挂到r的左子树，就完成了左旋操作
                r.left = p;
                p.parent = r;
            }
            return root;
        }

右旋rotateRight

右旋相当于以要旋转的节点C为中心（注意：A节点可以存在父节点，该左旋操作对A的父节点的结构几乎不影响，只只是影响父节点的子节点指向），将子树整体向右旋转，该节点变成子树的根节点（或者说替代A节点的位置，可以有父节点），原来的父节点A变成了C的右孩子，如果C有右孩子E，则E变为A的左孩子。当节点A向右旋转之后，C的右孩子E可以理解为因为重力作用掉到A的左孩子位置。经过右旋操作，A结点移到右边，A结点的左结点C来到了A的位置，并且C结点的右结点成为A结点的左结点。

对应到具体代码中，p即图中的A节点，l指向左孩子即C，lr指向左孩子的右孩子即E，pp为p的父节点。

image.png

        static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root,
                                                 TreeNode<K, V> p) {
            //即将右旋的是p，l是p的左子树，如果p和l都不为空进行右旋
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                //1.lr是l的右子树，lr不为空，将他挂到p的左边。
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                //2.如果p的父节点为空，那么r就是根节点，并且标记为黑色
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                else if (pp.right == p)//p是父节点的右节点，那么r挂到pp的右子树
                    pp.right = l;
                else //p是父节点的左节点，那么r挂到pp的左子树
                    pp.left = l;
                // 3.最后把p挂到l的右子树，就完成了右旋操作
                l.right = p;
                p.parent = l;
            }
            return root;
        }