红黑树 订阅
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 [1]  红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 [2]  红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 [2]  它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。 [2] 展开全文
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 [1]  红黑树是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 [2]  红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 [2]  它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。 [2]
信息
外文名
RED-BLACK-TREE
发明人
鲁道夫·贝尔
发明时间
1972年
别    名
对称二叉B树
用    途
实现关联数组 [1]
中文名
红黑树
性    质
平衡二叉查找树 [3]
学    科
计算机
红黑树简介
红黑树是一种特定类型的二叉树,它是在计算机科学中用来组织数据比如数字的块的一种结构。若一棵二叉查找树是红黑树,则它的任一子树必为红黑树. [4]  红黑树是一种平衡二叉查找树的变体,它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉树(AVL),但 对之进行平衡的代价较低, 其平均统计性能要强于 AVL 。 [2]  由于每一颗红黑树都是一颗二叉排序树,因此,在对红黑树进行查找时,可以采用运用于普通二叉排序树上的查找算法,在查找过程中不需要颜色信息。 [5] 
收起全文
精华内容
下载资源
问答
  • 红黑树的认识总结

    万次阅读 多人点赞 2020-05-12 17:06:50
    一、对红黑树的基本理解 (一)对红黑树的基本定义理解 (二)对红黑树是“近似平衡”的理解 1.将红色节点从红黑树中去掉,分析包含黑色节点的红黑树的高度 2.把红色节点加回去,分析高度变化 (三)红黑树与...

    目录

    一、对红黑树的基本理解

    (一)对红黑树的基本定义理解

    (二)对红黑树是“近似平衡”的理解

    1.将红色节点从红黑树中去掉,分析包含黑色节点的红黑树的高度

    2.把红色节点加回去,分析高度变化

    (三)红黑树与AVL树的比较:

    二、实现红黑树的基本思想分析

    (一)理解左旋(rotate left)、右旋(rotate right)操作

    (二)插入操作的平衡调整

    情况一:如果关注节点是 a,它的叔叔节点 d 是红色

    情况二:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的右子节点

    情况三:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的左子节点

    以上具体代码如下:

    (三)删除操作的平衡调整

    1.针对删除节点初步调整

    情况一:如果要删除的节点是 a,它只有一个子节点 b

    情况二:如果要删除的节点 a 有两个非空子节点,并且它的后继节点就是节点 a 的右子节点 c

    情况三:如果要删除的是节点 a,它有两个非空子节点,并且节点 a 的后继节点不是右子节点

    2. 针对关注节点进行二次调整

    情况一:如果关注节点是 a,它的兄弟节点 c 是红色的

    情况二:如果关注节点是 a,它的兄弟节点 c 是黑色的,并且节点 c 的左右子节点 d、e 都是黑色的

    情况三:如果关注节点是 a,它的兄弟节点 c 是黑色,c 的左子节点 d 是红色,c 的右子节点 e 是黑色

    情况四:如果关注节点 a 的兄弟节点 c 是黑色的,并且 c 的右子节点是红色的

    以上具体代码可见:

    参考文献与链接:


    一、对红黑树的基本理解

    (一)对红黑树的基本定义理解

    红黑树的英文是“Red-Black Tree”,简称 R-B Tree,它是一种不严格的平衡二叉查找树

    红黑树中的节点,一类被标记为黑色,一类被标记为红色。除此之外,一棵红黑树还需要满足这样几个要求

    • 根节点是黑色的;
    • 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据(图中将黑色的、空的叶子节点都省略掉了);
    • 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
    • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

    (二)对红黑树是“近似平衡”的理解

    平衡二叉查找树的初衷,是为了解决二叉查找树因为动态更新导致的性能退化问题。所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

    一棵极其平衡的二叉树(满二叉树或完全二叉树)的高度大约是 log2n,所以如果要证明红黑树是近似平衡的,只需要分析,红黑树的高度是否比较稳定地趋近 log2n 就好了

    1.将红色节点从红黑树中去掉,分析包含黑色节点的红黑树的高度

    红色节点删除之后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点(父节点的父节点)作为父节点。所以,之前的二叉树就变成了四叉树。

    从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树。所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。

    完全二叉树的高度近似 log2n,这里的四叉“黑树”的高度要低于完全二叉树,所以去掉红色节点的“黑树”的高度也不会超过 log2n。

    2.把红色节点加回去,分析高度变化

    在红黑树中,红色节点不能相邻,也就是说,有一个红色节点就要至少有一个黑色节点,将它跟其他红色节点隔开。

    红黑树中包含最多黑色节点的路径不会超过 log2n,所以加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。

    所以,红黑树的高度只比高度平衡的 AVL 树的高度(log2n)仅仅大了一倍,在性能上,下降得并不多。这样推导出来的结果不够精确,实际上红黑树的性能更好。

    (三)红黑树与AVL树的比较:

    • AVL树的时间复杂度虽然优于红黑树,但是对于现在的计算机,cpu太快,可以忽略性能差异
    • 红黑树的插入删除比AVL树更便于控制操作
    • 红黑树整体性能略优于AVL树(红黑树旋转情况少于AVL树)

    二、实现红黑树的基本思想分析

    红黑树的平衡过程跟魔方复原非常神似,大致过程就是:遇到什么样的节点排布,我们就对应怎么去调整。只要按照这些固定的调整规则来操作,就能将一个非平衡的红黑树调整成平衡的。

    如上,一棵合格的红黑树需要满足的四个基本要求中,在插入、删除节点的过程中,第三、第四点要求可能会被破坏,而“平衡调整”实际上就是要把被破坏的第三、第四点恢复过来。具体分析如下:

    (一)理解左旋(rotate left)、右旋(rotate right)操作

    左旋就是围绕某个节点的左旋,图中的 a,b,r 表示子树,可以为空。

    具体代码实现:

    /**
         * 功能描述:左旋右侧需要平衡
         *
         * @author yanfengzhang
         * @date 2020-05-27 14:57
         */
        private void rotateLeft(Entry<K, V> p) {
            if (p != null) {
                /*拿到根节点的右子节点 */
                Entry<K, V> r = p.right;
                /*把根节点的右子节点的左节点,赋值*/
                p.right = r.left;
                if (r.left != null)
                    /*将根节点这个值赋值到当前断开的跟节点上*/ {
                    r.left.parent = p;
                }
                /*r 将来要成为新的根节点 p.parent 为根 ,使得他为新的跟节点 */
                r.parent = p.parent;
                if (p.parent == null) {
                    root = r;
                }
                /*如果p 为左孩子,让他还是成为左孩子 同理*/
                else if (p.parent.left == p) {
                    p.parent.left = r;
                } else {
                    p.parent.right = r;
                }
                /*最后 将当前交换的跟换值*/
                r.left = p;
                p.parent = r;
            }
        }

    右旋就是围绕某个节点的右旋,图中的 a,b,r 表示子树,可以为空。

    具体代码实现:

        /**
         * 功能描述:右旋代码
         *
         * @author yanfengzhang
         * @date 2020-05-27 14:58
         */
        private void rotateRight(Entry<K, V> p) {
            if (p != null) {
                Entry<K, V> 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;
            }
        }

    (二)插入操作的平衡调整

    红黑树规定,插入的节点必须是红色的。而且,二叉查找树中新插入的节点都是放在叶子节点上。

    关于插入操作的平衡调整,有这样两种特殊情况:

    • 如果插入节点的父节点是黑色的,那我们什么都不用做,它仍然满足红黑树的定义。
    • 如果插入的节点是根节点,那我们直接改变它的颜色,把它变成黑色就可以了。

    除此之外,其他情况都会违背红黑树的定义,需要进行调整,调整的过程包含两种基础的操作:左右旋转和改变颜色

    红黑树的平衡调整过程是一个迭代的过程。把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理,而不断发生变化。最开始的关注节点就是新插入的节点。新节点插入之后,如果红黑树的平衡被打破,那一般会有下面三种情况

    备注:我们只需要根据每种情况的特点,不停地调整,就可以让红黑树继续符合定义,也就是继续保持平衡。为了简化描述,把父节点的兄弟节点叫作叔叔节点,父节点的父节点叫作祖父节点。

    情况一:如果关注节点是 a,它的叔叔节点 d 是红色

    具体操作为:将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色;将关注节点 a 的祖父节点 c 的颜色设置成红色;关注节点变成 a 的祖父节点 c;跳到情况二或者情况三。

    情况二:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的右子节点

    具体操作为:关注节点变成节点 a 的父节点 b;围绕新的关注节点b 左旋;跳到情况三。

    情况三:如果关注节点是 a,它的叔叔节点 d 是黑色,关注节点 a 是其父节点 b 的左子节点

    具体操作为:围绕关注节点 a 的祖父节点 c 右旋;将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换,调整结束。

    以上具体代码如下:

        /**
         * 功能描述:插入一个节点
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:07
         */
        private void insert(RBTreeNode<T> node) {
            int cmp;
            RBTreeNode<T> root = this.rootNode;
            RBTreeNode<T> parent = null;
    
            /*定位节点添加到哪个父节点下*/
            while (null != root) {
                parent = root;
                cmp = node.key.compareTo(root.key);
                if (cmp < 0) {
                    root = root.left;
                } else {
                    root = root.right;
                }
            }
    
            node.parent = parent;
            /*表示当前没一个节点,那么就当新增的节点为根节点*/
            if (null == parent) {
                this.rootNode = node;
            } else {
                //找出在当前父节点下新增节点的位置
                cmp = node.key.compareTo(parent.key);
                if (cmp < 0) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
    
            /*设置插入节点的颜色为红色*/
            node.color = COLOR_RED;
    
            /*修正为红黑树*/
            insertFixUp(node);
        }
    
        /**
         * 功能描述:红黑树插入修正
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:07
         */
        private void insertFixUp(RBTreeNode<T> node) {
            RBTreeNode<T> parent, gparent;
            /*节点的父节点存在并且为红色*/
            while (((parent = getParent(node)) != null) && isRed(parent)) {
                gparent = getParent(parent);
    
                /*如果其祖父节点是空怎么处理, 若父节点是祖父节点的左孩子*/
                if (parent == gparent.left) {
                    RBTreeNode<T> uncle = gparent.right;
                    if ((null != uncle) && isRed(uncle)) {
                        setColorBlack(uncle);
                        setColorBlack(parent);
                        setColorRed(gparent);
                        node = gparent;
                        continue;
                    }
    
                    if (parent.right == node) {
                        RBTreeNode<T> tmp;
                        leftRotate(parent);
                        tmp = parent;
                        parent = node;
                        node = tmp;
                    }
    
                    setColorBlack(parent);
                    setColorRed(gparent);
                    rightRotate(gparent);
                } else {
                    RBTreeNode<T> uncle = gparent.left;
                    if ((null != uncle) && isRed(uncle)) {
                        setColorBlack(uncle);
                        setColorBlack(parent);
                        setColorRed(gparent);
                        node = gparent;
                        continue;
                    }
    
                    if (parent.left == node) {
                        RBTreeNode<T> tmp;
                        rightRotate(parent);
                        tmp = parent;
                        parent = node;
                        node = tmp;
                    }
    
                    setColorBlack(parent);
                    setColorRed(gparent);
                    leftRotate(gparent);
                }
            }
            setColorBlack(this.rootNode);
        }

    (三)删除操作的平衡调整

    删除操作的平衡调整分为两步

    第一步是针对删除节点初步调整。初步调整只是保证整棵红黑树在一个节点删除之后,仍然满足最后一条定义的要求,也就是说,每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

    第二步是针对关注节点进行二次调整,让它满足红黑树的第三条定义,即不存在相邻的两个红色节点。

    1.针对删除节点初步调整

    红黑树的定义中“只包含红色节点和黑色节点”,经过初步调整之后,为了保证满足红黑树定义的最后一条要求,有些节点会被标记成两种颜色,“红 - 黑”或者“黑 - 黑”。如果一个节点被标记为了“黑 - 黑”,那在计算黑色节点个数的时候,要算成两个黑色节点。

    备注:如果一个节点既可以是红色,也可以是黑色,图中用一半红色一半黑色来表示。如果一个节点是“红 - 黑”或者“黑 - 黑”,图中用左上角的一个小黑点来表示额外的黑色。

    情况一:如果要删除的节点是 a,它只有一个子节点 b

    具体操作为:删除节点 a,并且把节点 b 替换到节点 a 的位置,这一部分操作跟普通的二叉查找树的删除操作一样;节点 a 只能是黑色,节点 b 也只能是红色,其他情况均不符合红黑树的定义。这种情况下,我们把节点 b 改为黑色;调整结束,不需要进行二次调整。

    情况二:如果要删除的节点 a 有两个非空子节点,并且它的后继节点就是节点 a 的右子节点 c

    具体操作为:如果节点 a 的后继节点就是右子节点 c,那右子节点 c 肯定没有左子树。我们把节点 a 删除,并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异;然后把节点 c 的颜色设置为跟节点 a 相同的颜色;如果节点 c 是黑色,为了不违反红黑树的最后一条定义,我们给节点 c 的右子节点 d 多加一个黑色,这个时候节点 d 就成了“红 - 黑”或者“黑 - 黑”;这个时候,关注节点变成了节点 d,第二步的调整操作就会针对关注节点来做。

    情况三:如果要删除的是节点 a,它有两个非空子节点,并且节点 a 的后继节点不是右子节点

    具体操作为:找到后继节点 d,并将它删除,删除后继节点 d 的过程参照 CASE 1;将节点 a 替换成后继节点 d;把节点 d 的颜色设置为跟节点 a 相同的颜色;如果节点 d 是黑色,为了不违反红黑树的最后一条定义,我们给节点 d 的右子节点 c 多加一个黑色,这个时候节点 c 就成了“红 - 黑”或者“黑 - 黑”;这个时候,关注节点变成了节点 c,第二步的调整操作就会针对关注节点来做。

    2. 针对关注节点进行二次调整

    初步调整之后,关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点,再分四种情况来进行二次调整。

    备注:二次调整是为了让红黑树中不存在相邻的红色节点。

    情况一:如果关注节点是 a,它的兄弟节点 c 是红色的

    具体操作:围绕关注节点 a 的父节点 b 左旋;关注节点 a 的父节点 b 和祖父节点 c 交换颜色;关注节点不变;继续从四种情况中选择适合的规则来调整。

    情况二:如果关注节点是 a,它的兄弟节点 c 是黑色的,并且节点 c 的左右子节点 d、e 都是黑色的

    具体操作:将关注节点 a 的兄弟节点 c 的颜色变成红色;从关注节点 a 中去掉一个黑色,这个时候节点 a 就是单纯的红色或者黑色;给关注节点 a 的父节点 b 添加一个黑色,这个时候节点 b 就变成了“红 - 黑”或者“黑 - 黑”;关注节点从 a 变成其父节点 b;继续从四种情况中选择符合的规则来调整。

    情况三:如果关注节点是 a,它的兄弟节点 c 是黑色,c 的左子节点 d 是红色,c 的右子节点 e 是黑色

    具体操作:围绕关注节点 a 的兄弟节点 c 右旋;节点 c 和节点 d 交换颜色;关注节点不变;跳转到 CASE 4,继续调整。

    情况四:如果关注节点 a 的兄弟节点 c 是黑色的,并且 c 的右子节点是红色的

    具体操作:围绕关注节点 a 的父节点 b 左旋;将关注节点 a 的兄弟节点 c 的颜色,跟关注节点 a 的父节点 b 设置成相同的颜色;将关注节点 a 的父节点 b 的颜色设置为黑色;从关注节点 a 中去掉一个黑色,节点 a 就变成了单纯的红色或者黑色;将关注节点 a 的叔叔节点 e 设置为黑色;调整结束。

    以上具体代码可见:

        /**
         * 功能描述:删除节点
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:11
         */
        private void remove(RBTreeNode<T> node) {
            RBTreeNode<T> child, parent;
            boolean color;
            /*被删除节点左右孩子都不为空的情况*/
            if ((null != node.left) && (null != node.right)) {
    
                /*获取到被删除节点的后继节点*/
                RBTreeNode<T> replace = node;
    
                replace = replace.right;
                while (null != replace.left) {
                    replace = replace.left;
                }
    
                /*node节点不是根节点*/
                if (null != getParent(node)) {
                    /*node是左节点*/
                    if (getParent(node).left == node) {
                        getParent(node).left = replace;
                    } else {
                        getParent(node).right = replace;
                    }
                } else {
                    this.rootNode = replace;
                }
    
                child = replace.right;
                parent = getParent(replace);
                color = getColor(replace);
    
                if (parent == node) {
                    parent = replace;
                } else {
                    if (null != child) {
                        setParent(child, parent);
                    }
                    parent.left = child;
    
                    replace.right = node.right;
                    setParent(node.right, replace);
                }
    
                replace.parent = node.parent;
                replace.color = node.color;
                replace.left = node.left;
                node.left.parent = replace;
                if (color == COLOR_BLACK) {
                    removeFixUp(child, parent);
                }
    
                node = null;
                return;
            }
    
            if (null != node.left) {
                child = node.left;
            } else {
                child = node.right;
            }
    
            parent = node.parent;
            color = node.color;
            if (null != child) {
                child.parent = parent;
            }
    
            if (null != parent) {
                if (parent.left == node) {
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            } else {
                this.rootNode = child;
            }
    
            if (color == COLOR_BLACK) {
                removeFixUp(child, parent);
            }
            node = null;
        }
    
        /**
         * 功能描述:删除修复
         *
         * @author yanfengzhang
         * @date 2020-05-27 15:11
         */
        private void removeFixUp(RBTreeNode<T> node, RBTreeNode<T> parent) {
            RBTreeNode<T> other;
            /*node不为空且为黑色,并且不为根节点*/
            while ((null == node || isBlack(node)) && (node != this.rootNode)) {
                /*node是父节点的左孩子*/
                if (node == parent.left) {
                    /*获取到其右孩子*/
                    other = parent.right;
                    /*node节点的兄弟节点是红色*/
                    if (isRed(other)) {
                        setColorBlack(other);
                        setColorRed(parent);
                        leftRotate(parent);
                        other = parent.right;
                    }
    
                    /*node节点的兄弟节点是黑色,且兄弟节点的两个孩子节点也是黑色*/
                    if ((other.left == null || isBlack(other.left)) &&
                            (other.right == null || isBlack(other.right))) {
                        setColorRed(other);
                        node = parent;
                        parent = getParent(node);
                    } else {
                        /*node节点的兄弟节点是黑色,且兄弟节点的右孩子是红色*/
                        if (null == other.right || isBlack(other.right)) {
                            setColorBlack(other.left);
                            setColorRed(other);
                            rightRotate(other);
                            other = parent.right;
                        }
                        /*node节点的兄弟节点是黑色,且兄弟节点的右孩子是红色,左孩子是任意颜色*/
                        setColor(other, getColor(parent));
                        setColorBlack(parent);
                        setColorBlack(other.right);
                        leftRotate(parent);
                        node = this.rootNode;
                        break;
                    }
                } else {
                    other = parent.left;
                    if (isRed(other)) {
                        setColorBlack(other);
                        setColorRed(parent);
                        rightRotate(parent);
                        other = parent.left;
                    }
    
                    if ((null == other.left || isBlack(other.left)) &&
                            (null == other.right || isBlack(other.right))) {
                        setColorRed(other);
                        node = parent;
                        parent = getParent(node);
                    } else {
                        if (null == other.left || isBlack(other.left)) {
                            setColorBlack(other.right);
                            setColorRed(other);
                            leftRotate(other);
                            other = parent.left;
                        }
    
                        setColor(other, getColor(parent));
                        setColorBlack(parent);
                        setColorBlack(other.left);
                        rightRotate(parent);
                        node = this.rootNode;
                        break;
                    }
                }
            }
            if (node != null) {
                setColorBlack(node);
            }
        }

    参考文献与链接:

    1.https://tech.meituan.com/2016/12/02/redblack-tree.html

    2.《数据结构与算法之美》,王争(前Google工程师),极客时间,2019

    3.https://blog.csdn.net/tanrui519521/article/details/80980135

    4.https://blog.csdn.net/jjc120074203/article/details/78780221

    5.https://blog.csdn.net/aa1215018028/article/details/92660140

    展开全文
  • 红黑树

    万次阅读 2011-02-11 21:56:00
    介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和Robert Sedgewick改成一个比较摩登的...

     

    介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和Robert Sedgewick改成一个比较摩登的名字:红黑树。

    红黑树和之前所讲的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。不过在我了解了红黑树的实现原理后,并不相信这是真的,关于这一点我们会在后面进行讨论。

    红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。之前我们在讲解AVL树时,已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。

    首先来一个Silverlight做的红黑树的动画,它有助于帮你理解什么是红黑树。这里需要注意,必须安装Silverlight 2.0 RTW 才能正常运行游戏,下载地址:

    http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0

     

    使用注意事项:

    l         结点只接收整数,如果在添加和删除操作中输入非法字串,则会随机添加或删除一个0~99之间的整数。

    l         可以不在编辑框中输入数字,直接单击添加和删除按钮进行添加和删除操作。

    l         可以拖动拖动条控制动画速度。

    红黑树的平衡

    红黑树首先是一棵二叉查找树,它每个结点都被标上了颜色(红色或黑色),红黑树满足以下5个性质:

    1、 每个结点的颜色只能是红色或黑色。

    2、 根结点是黑色的。

    3、 每个叶子结点都带有两个空的黑色结点(被称为黑哨兵),如果一个结点n的只有一个左孩子,那么n的右孩子是一个黑哨兵;如果结点n只有一个右孩子,那么n的左孩子是一个黑哨兵。

    4、 如果一个结点是红的,则它的两个儿子都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

    5、 对于每个结点来说,从该结点到其子孙叶结点的所有路径上包含相同数目的黑结点。

    红黑树的这5个性质中,第3点是比较难理解的,但它却非常有必要。我们看图1中的左边这张图,如果不使用黑哨兵,它完全满足红黑树性质,结点50到两个叶结点8和叶结点82路径上的黑色结点数都为2个。但如果加入黑哨兵后(如图1右图中的小黑圆点),叶结点的个数变为8个黑哨兵,根结点50到这8个叶结点路径上的黑高度就不一样了,所以它并不是一棵红黑树。

     

     

    要看真正的红黑树请在以上动画中添加几个结点,看看是否满足以上性质。

    红黑树的旋转操作

    红黑树的旋转操作和AVL树一样,分为LL、RR、LR、RL四种旋转类型,差别在于旋转完成后改变的是结点的颜色,而不是平衡因子。旋转动画演示请参考AVL这篇文章中的Flash动画:

    http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html

    红黑树上结点的插入

    在讨论红黑树的插入操作之前必须要明白,任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解,因为插入黑点会增加某条路径上黑结点的数目,从而导致整棵树黑高度的不平衡。但如果新结点父结点为红色时(如图2所示),将会违返红黑树性质:一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

     

     

     

    为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点;使用“父”字表示新插入点的父结点;使用“叔”字表示“父”结点的兄弟结点;使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况:

    1黑父

    如图3所示,如果新点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见,从而使红黑树需要旋转的几率相对AVL树来说会少一些。

     

     

     

    2.红父

    如果新点的父结点为红色,这时就需要进行一系列操作以保证整棵树红黑性质。如图3所示,由于父结点为红色,此时可以判定,祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作,而每次进行不平衡判断的起始点(我们可将其视为新点)都不一样。所以我们在此使用一个蓝色箭头指向这个起始点,并称之为判定点。

     

     

     

    2.1 红叔

    当叔父结点为红色时,如图4所示,无需进行旋转操作,只要将父和叔结点变为黑色,将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色,从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上进行平衡操作。

     

     

    需要注意,无论“父”在“叔”的左边还是右边,无论“新”是“父”的左孩子还是右孩子,它们的操作都完全一样。

     

    2.2 黑叔

    当叔父结点为黑色时,需要进行旋转,以下图示了所有的旋转可能

    情形1:

     

     

    情形2:

     

    情形3:

     

     

    情形4:

     

     

    可以观察到,当旋转完成后,新的旋转根全部为黑色,此时不需要再向上回溯进行平衡操作,插入操作完成。需要注意,上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

    其实红黑树的插入操作不是很难,甚至比AVL树的插入操作还更简单些。但删除操作就远远比AVL树复杂得多,下面就介绍红黑树的删除操作。

    红黑树上结点的删除

    红黑树本身是一棵二叉查找树,它的删除和二叉查找树的删除类似。首先要找到真正的删除点,当被删除结点n存在左右孩子时,真正的删除点应该是n的中序遍在前驱,关于这一点请复习二叉查找树的删除。如图9所示,当删除结点20时,实际被删除的结点应该为18,结点20的数据变为18。

     

     

     

    所以可以推断出,在进行删除操作时,真正的删除点必定是只有一个孩子或没有孩子的结点。而根据红黑树的性质可以得出以下两个结论:

    1、 删除操作中真正被删除的必定是只有一个红色孩子或没有孩子的结点

    2、 如果真正的删除点是一个红色结点,那么它必定是一个叶子结点

    理解这两点非常重要,如图10所示,除了情况(a)外,其他任一种况结点N都无法满足红黑树性质。

     

     

     

    在以下讨论中,我们使用蓝色箭头表示真正的删除点,它也是旋转操作过程中的第一个判定点;真正的删除点使用“旧”标注,旧点所在位置将被它的的孩子结点所取代(最多只有一个孩子),我们使用“新”表示旧点的孩子结点。删除操作可分为以下几种情形:

    1、旧点为红色结点

    若旧点为红色结点,则它必定是叶子结点,直接删除即可。如图11所示

     

     

     

    2、一红一黑

    当旧点为黑色结点,新点为红色结点时,将新点取代旧点位置后,将新点染成黑色即可(如图12所示)。这里需要注意:旧点为红色,新点为黑色的情况不可能存在。

     

     

     

    3、双黑

    当旧点和新点都为黑色时(新点为空结点时,亦属于这种情况),情况比较复杂,需要根据旧点兄弟结点的颜色来决定进行什么样的操作。我们使用“兄”来表示旧点的兄弟结点。这里可分为红兄和黑兄两种情况:

    3.1 红兄

    由于兄弟结点为红色,所以父结点必定为黑色,而旧点被删除后,新点取代了它的位置。下图演示了两种可能的情况:

     

     

     

    红兄的情况需要进行RR或LL型旋转,然后将父结点染成红色,兄结点染成黑色。然后重新以新点为判定点进行平衡操作。我们可以观察到,旋转操作完成后,判定点没有向上回溯,而是降低了一层,此时变成了黑兄的情况。

    3.2 黑兄

    黑兄的情况最为复杂,需要根据黑兄孩子结点(这里用“侄”表示)和父亲结点的颜色来决定做什么样的操作。

    3.2.1 黑兄二黑侄红父

    如图14所示,这种情况比较简单,只需将父结点变为黑色,兄结点变为黑色,新结点变为黑色即可,删除操作到此结束。

     

     

     

    3.2.2 黑兄二黑侄黑父

    如图15所示,此时将父结点染成新结点的颜色,新结点染成黑色,兄结点染成红色即可。当新结点为红色时,父结点被染成红色,此时需要以父结点为判定点继续向上进行平衡操作。

     

     

     

    3.2.3 黑兄红侄

    黑兄红侄有以下四种情形,下面分别进行图示:

    情形1:

     

     

    情形2:

     

    情形3:

     

    情形4:

     

     

     

    由以上图例所示,看完以上四张图的兄弟有可能会有一个疑问,如果情形1和情形2中的两个侄子结点都为红色时,是该进行LL旋转还是进行LR旋转呢?答案是进行LL旋转。情形3和情形4则是优先进行RR旋转的判定。

     

     

     

     

     

     

     

     

        教你透彻了解红黑树

     

    作者 July、saturnman   2010年12月29日

    本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。
    本人声明:个人原创,转载请注明出处。

    推荐阅读:Left-Leaning Red-Black TreesDagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008.

    ------------------------------
    红黑树系列,四篇文章于今日已经完成。[二零一一年一月九日]

    教你透彻了解红黑树:
    http://blog.csdn.net/v_JULY_v/archive/2010/12/29/6105630.aspx
    红黑树算法的层层剖析与逐步实现  [此文被推荐]
    http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx
    教你彻底实现红黑树:红黑树的c源码实现与剖析
    http://blog.csdn.net/v_JULY_v/archive/2011/01/03/6114226.aspx
    一步一图一代码,一定要让你真正彻底明白红黑树 [最后更新]
    http://blog.csdn.net/v_JULY_v/archive/2011/01/09/6124989.aspx

    ------------------------------

     

    一、红黑树的介绍

    先来看下算法导论对R-B Tree的介绍:
    红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。
    通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其
    他路径长出俩倍,因而是接近平衡的。

     

    前面说了,红黑树,是一种二叉查找树,既然是二叉查找树,那么它必满足二叉查找树的一般性质。
    下面,在具体介绍红黑树之前,咱们先来了解下 二叉查找树的一般性质:
    1.在一棵二叉查找树上,执行查找、插入、删除等操作,的时间复杂度为O(lgn)。
        因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,一般操作的执行时间为O(lgn)。
        //至于n个结点的二叉树高度为lgn的证明,可参考算法导论 第12章 二叉查找树 第12.4节。
    2.但若是一棵具有n个结点的线性链,则此些操作最坏情况运行时间为O(n)。

     

    红黑树,能保证在最坏情况下,基本的动态几何操作的时间均为O(lgn)。

    ok,我们知道,红黑树上每个结点内含五个域,color,key,left,right。如果相应的指针域没有,则设为NIL。

    一般的,红黑树,满足以下性质,即只有满足以下全部性质的树,我们才称之为红黑树:

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

     

    下图所示,即是一颗红黑树:

    此图忽略了叶子和根部的父结点。

     

    二、树的旋转知识

    当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。

    为了保持红黑树的性质,我们可以通过对树进行旋转,即修改树种某些结点的颜色及指针结构,以达到对红黑树进行

    插入、删除结点等操作时,红黑树依然能保持它特有的性质(如上文所述的,五点性质)。

     

    树的旋转,分为左旋和右旋,以下借助图来做形象的解释和介绍:

    1.左旋

    如上图所示:

    当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为树内任意右孩子而不是NIL[T]的结点。

    左旋以pivot到y之间的链为“支轴”进行,它使y成为该孩子树新的根,而y的左孩子b则成为pivot的右孩子。

    来看算法导论对此操作的算法实现(以x代替上述的pivot):

     LEFT-ROTATE(Tx)
    1  y  right[x Set y.
    2  right[x left[y]       Turn y's left subtree into x's right subtree.

    3  p[left[y]]  x
    4  p[y p[x]              Link x's parent to y.
    5  if p[x] = nil[T]
    6     then root[T y
    7     else if x = left[p[x]]
    8             then left[p[x]]  y
    9             else right[p[x]]  y
    10  left[y x              Put x on y's left.
    11  p[x y

     

    2.右旋

    右旋与左旋差不多,再此不做详细介绍。

     

    对于树的旋转,能保持不变的只有原树的搜索性质,而原树的红黑性质则不能保持,

    在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。

     

    至于有些书如 STL源码剖析有对双旋的描述,其实双旋只是单旋的两次应用,并无新的内容,

    因此这里就不再介绍了,而且左右旋也是相互对称的,只要理解其中一种旋转就可以了。

     

    三、红黑树插入、删除操作的具体实现

       三、I、ok,接下来,咱们来具体了解红黑树的插入操作。
    向一棵含有n个结点的红黑树插入一个新结点的操作可以在O(lgn)时间内完成。

    算法导论:
    RB-INSERT(T, z)
     1  y ← nil[T]
     2  x ← root[T]
     3  while x ≠ nil[T]
     4      do y ← x
     5         if key[z] < key[x]
     6            then x ← left[x]
     7            else x ← right[x]
     8  p[z] ← y
     9  if y = nil[T]
    10     then root[T] ← z
    11     else if key[z] < key[y]
    12             then left[y] ← z
    13             else right[y] ← z
    14  left[z] ← nil[T]
    15  right[z] ← nil[T]
    16  color[z] ← RED
    17  RB-INSERT-FIXUP(T, z)

    咱们来具体分析下,此段代码:
    RB-INSERT(T, z),将z插入红黑树T 之内。

    为保证红黑性质在插入操作后依然保持,上述代码调用了一个辅助程序RB-INSERT-FIXUP
    来对结点进行重新着色,并旋转。

    14  left[z] ← nil[T]
    15  right[z] ← nil[T]  //保持正确的树结构
    第16行,将z着为红色,由于将z着为红色可能会违背某一条红黑树的性质,
    所以,在第17行,调用RB-INSERT-FIXUP(T,z)来保持红黑树的性质。

    RB-INSERT-FIXUP(T, z),如下所示:
     1 while color[p[z]] = RED
     2     do if p[z] = left[p[p[z]]]
     3           then y ← right[p[p[z]]]
     4                if color[y] = RED
     5                   then color[p[z]] ← BLACK                    ▹ Case 1
     6                        color[y] ← BLACK                       ▹ Case 1
     7                        color[p[p[z]]] ← RED                   ▹ Case 1
     8                        z ← p[p[z]]                            ▹ Case 1
     9                   else if z = right[p[z]]
    10                           then z ← p[z]                       ▹ Case 2
    11                                LEFT-ROTATE(T, z)              ▹ Case 2
    12                           color[p[z]] ← BLACK                 ▹ Case 3
    13                           color[p[p[z]]] ← RED                ▹ Case 3
    14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3
    15           else (same as then clause
                             with "right" and "left" exchanged)
    16 color[root[T]] ← BLACK

     
    ok,参考一网友的言论,用自己的语言,再来具体解剖下上述俩段代码。
    为了保证阐述清晰,我再写下红黑树的5个性质:

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

     

    在对红黑树进行插入操作时,我们一般总是插入红色的结点,因为这样可以在插入过程中尽量避免对树的调整。
    那么,我们插入一个结点后,可能会使原树的哪些性质改变列?
    由于,我们是按照二叉树的方式进行插入,因此元素的搜索性质不会改变。

    如果插入的结点是根结点,性质2会被破坏,如果插入结点的父结点是红色,则会破坏性质4。
    因此,总而言之,插入一个红色结点只会破坏性质2或性质4。
    我们的回复策略很简单,
    其一、把出现违背红黑树性质的结点向上移,如果能移到根结点,那么很容易就能通过直接修改根结点来恢复红黑树的性质。直接通过修改根结点来恢复红黑树应满足的性质。
    其二、穷举所有的可能性,之后把能归于同一类方法处理的归为同一类,不能直接处理的化归到下面的几种情况,

     //注:以下情况3、4、5与上述算法导论上的代码RB-INSERT-FIXUP(T, z),相对应:

     

    情况1:插入的是根结点。
    原树是空树,此情况只会违反性质2。
      对策:直接把此结点涂为黑色。
    情况2:插入的结点的父结点是黑色。
    此不会违反性质2和性质4,红黑树没有被破坏。
      对策:什么也不做。
    情况3:当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色。
    此时父结点的父结点一定存在,否则插入前就已不是红黑树。
    与此同时,又分为父结点是祖父结点的左子还是右子,对于对称性,我们只要解开一个方向就可以了。

    在此,我们只考虑父结点为祖父左子的情况。
    同时,还可以分为当前结点是其父结点的左子还是右子,但是处理方式是一样的。我们将此归为同一类。
      对策:将当前节点的父节点和叔叔节点涂黑,祖父结点涂红,把当前结点指向祖父节点,从新的当前节点重新开始算法。

    针对情况3,变化前(图片来源:saturnman)[插入4节点]:

    变化后:

    情况4:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

    对策:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。

    如下图所示,变化前[插入7节点]:

     

    变化后:

     

     

    情况5:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左子

    解法:父节点变为黑色,祖父节点变为红色,在祖父节点为支点右旋

    如下图所示[插入2节点]

    变化后:

     

     

    ==================

       三、II、ok,接下来,咱们最后来了解,红黑树的删除操作:

    算法导论一书,给的算法实现: 

    RB-DELETE(T, z)   单纯删除结点的总操作
     1 if left[z] = nil[T] or right[z] = nil[T]
     2    then y ← z
     3    else y ← TREE-SUCCESSOR(z)
     4 if left[y] ≠ nil[T]
     5    then x ← left[y]
     6    else x ← right[y]
     7 p[x] ← p[y]
     8 if p[y] = nil[T]
     9    then root[T] ← x
    10    else if y = left[p[y]]
    11            then left[p[y]] ← x
    12            else right[p[y]] ← x
    13 if y 3≠ z
    14    then key[z] ← key[y]
    15         copy y's satellite data into z
    16 if color[y] = BLACK
    17    then RB-DELETE-FIXUP(T, x)
    18 return y

     

    RB-DELETE-FIXUP(T, x)   恢复与保持红黑性质的工作
     1 while x ≠ root[T] and color[x] = BLACK
     2     do if x = left[p[x]]
     3           then w ← right[p[x]]
     4                if color[w] = RED
     5                   then color[w] ← BLACK                        ▹  Case 1
     6                        color[p[x]] ← RED                       ▹  Case 1
     7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
     8                        w ← right[p[x]]                         ▹  Case 1
     9                if color[left[w]] = BLACK and color[right[w]] = BLACK
    10                   then color[w] ← RED                          ▹  Case 2
    11                        x p[x]                                  ▹  Case 2
    12                   else if color[right[w]] = BLACK
    13                           then color[left[w]] ← BLACK          ▹  Case 3
    14                                color[w] ← RED                  ▹  Case 3
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3
    16                                w ← right[p[x]]                 ▹  Case 3
    17                         color[w] ← color[p[x]]                 ▹  Case 4
    18                         color[p[x]] ← BLACK                    ▹  Case 4
    19                         color[right[w]] ← BLACK                ▹  Case 4
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
    21                         x ← root[T]                            ▹  Case 4
    22        else (same as then clause with "right" and "left" exchanged)
    23 color[x] ← BLACK

     

    为了保证以下的介绍与阐述清晰,我第三次重写下红黑树的5个性质

    1)每个结点要么是红的,要么是黑的。
    2)根结点是黑的。
    3)每个叶结点,即空结点(NIL)是黑的。
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。
    5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

    (相信,重述了3次,你应该有深刻记忆了。:D)

     

     saturnman:
    红黑树删除的几种情况:

    -------------------------------------------------
    博主提醒:
    以下所有的操作,是针对红黑树已经删除结点之后,
    为了恢复和保持红黑树原有的5点性质,所做的恢复工作。

    前面,我已经说了,因为插入、或删除结点后,
    可能会违背、或破坏红黑树的原有的性质,
    所以为了使插入、或删除结点后的树依然维持为一棵新的红黑树,
    那就要做俩方面的工作:
    1、部分结点颜色,重新着色
    2、调整部分指针的指向,即左旋、右旋。

    而下面所有的文字,则是针对红黑树删除结点后,所做的修复红黑树性质的工作。

     二零一一年一月七日更新。
    ------------------------------------------------------------

    (注:以下的情况3、4、5、6,与上述算法导论之代码RB-DELETE-FIXUP(T, x) 恢复与保持
    中case1,case2,case3,case4相对应。)
    情况1:当前节点是红色
        解法,直接把当前节点染成黑色,结束。
        此时红黑树性质全部恢复。
    情况2:当前节点是黑色且是根节点
        解法:什么都不做,结束

    情况3:当前节点是黑色,且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。
        解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。
        然后,针对父节点做一次左旋。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况。

                         3.变化前:

     

                         3.变化后: 

     

    情况4:当前节点是黑色,且兄弟是黑色,且兄弟节点的两个子节点全为黑色。
          解法:把当前节点和兄弟节点中抽取一重黑色追加到父节点上,把父节点当成新的当前节点,重新进入算法。(此变换后性质5不变)

                            4.变化前

     

                            4.变化后

     

    情况5:当前节点颜色是黑色,兄弟节点是黑色,兄弟的左子是红色,右子是黑色。
        解法:把兄弟结点染红,兄弟左子节点染黑,之后再在兄弟节点为支点解右旋,
    之后重新进入算法。此是把当前的情况转化为情况6,而性质5得以保持。

                  5.变化前:

     

                      5.变化后:

     

    情况6:当前节点颜色是黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意。

        解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,

    之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确。

                        6.变化前:

                  6.变化后:

     

    限于篇幅,不再过多赘述。更多,可参考算法导论或下文我写的第二篇文章。

    完。

    July、二零一零年十二月二十九日初稿。三十日凌晨修订。行文3个小时以上。

    ----------------

     

    今下午画红黑树画了好几个钟头,贴俩张图:

      红黑树插入的3种情况:

     

      红黑树删除的4种情况:

     

    ok,只贴俩张,更多,参考我写的关于红黑树的第二篇文章:

    红黑树算法的层层剖析与逐步实现[推荐]
    http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx

    这篇文章针对算法实现源码分十层,层层、逐层剖析,相信,更清晰易懂。

    //尤其文末针对红黑树的删除情况,层次清晰。

     

                 July、二零一零年十二月三十一日、最后更新。

     

    展开全文
  • 教你初步了解红黑树

    万次阅读 多人点赞 2010-12-29 18:36:00
    教你透彻了解红黑树 作者:July、saturnman 2010年12月29日本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。推荐阅读:Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, ...

                     教你初步了解黑树


     

    作者:July、saturnman   2010年12月29日

    本文参考:Google、算法导论、STL源码剖析、计算机程序设计艺术。

    推荐阅读

    1. Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data Structures, Wadern, Germany, February, 2008,直接下载:http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
    2. 本文的github优化版:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md

     

    一、红黑树的介绍

    先来看下算法导论对R-B Tree的介绍:
    红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。
    通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

     

    红黑树,作为一棵二叉查找树,满足二叉查找树的一般性质。下面,来了解下 二叉查找树的一般性质。

    二叉查找树

    二叉查找树,也称有序二叉树(ordered binary tree),或已排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

    • 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    • 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    • 任意节点的左、右子树也分别为二叉查找树。
    • 没有键值相等的节点(no duplicate nodes)。

    因为一棵由n个结点随机构造的二叉查找树的高度为lgn,所以顺理成章,二叉查找树的一般操作的执行时间为O(lgn)。但二叉查找树若退化成了一棵具有n个结点的线性链后,则这些操作最坏情况运行时间为O(n)。

    红黑树虽然本质上是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

    但它是如何保证一棵n个结点的红黑树的高度始终保持在logn的呢?这就引出了红黑树的5个性质:

    1. 每个结点要么是红的要么是黑的。  
    2. 根结点是黑的。  
    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。  
    4. 如果一个结点是红的,那么它的两个儿子都是黑的。  
    5.  对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。 

    正是红黑树的这5条性质,使一棵n个结点的红黑树始终保持了logn的高度,从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

    :上述第3、5点性质中所说的NULL结点,包括wikipedia.算法导论上所认为的叶子结点即为树尾端的NIL指针,或者说NULL结点。然百度百科以及网上一些其它博文直接说的叶结点,则易引起误会,因,此叶结点非子结点

    如下图所示,即是一颗红黑树(下图引自wikipedia:http://t.cn/hgvH1l):


    此图忽略了叶子和根部的父结点。同时,上文中我们所说的 "叶结点" 或"NULL结点",如上图所示,它不包含数据而只充当树在此结束的指示,这些节点在绘图中经常被省略,望看到此文后的读者朋友注意。 


    二、树的旋转知识

        当在对红黑树进行插入和删除等操作时,对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质,可以通过对结点进行重新着色,以及对树进行相关的旋转操作,即通过修改树中某些结点的颜色及指针结构,来达到对红黑树进行插入或删除结点等操作后继续保持它的性质或平衡的目的

        树的旋转分为左旋和右旋,下面借助图来介绍一下左旋和右旋这两种操作。

    1.左旋

    如上图所示当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为任何不是NIL[T]的左子结点。左旋以pivot到Y之间的链为“支轴”进行,它使Y成为该子树新根,而Y的左孩子b则成为pivot的右孩子。

    LeftRoate(T, x)
    y ← x.right				       //定义y:y是x的右孩子
    x.right ← y.left	            //y的左孩子成为x的右孩子
    if y.left ≠ T.nil
        y.left.p ← x	
    y.p ← x.p				       //x的父结点成为y的父结点
    if x.p = T.nil
    	then T.root ← y
    else if x = x.p.left
    	then x.p.left ← y
    else x.p.right ← y 
    y.left ← x                       //x作为y的左孩子
    x.p ← y

    2.右旋

    右旋与左旋差不多,再此不做详细介绍。

     

    树在经过左旋右旋之后,树的搜索性质保持不变树的红黑性质则被破坏了所以,红黑树插入和删除数据后,需要利用旋转颜色重涂来重新恢复树的红黑性质

        至于有些书如《STL源码剖析》有对双旋的描述,其实双旋只是单旋的两次应用,并无新的内容,因此这里就不再介绍了,而且左右旋也是相互对称的,只要理解其中一种旋转就可以了。

     

    三、红黑树的插入

    要真正理解红黑树的插入,还得先理解二叉查找树的插入。磨刀不误砍柴工,咱们再来了解下二叉查找树的插入红黑树的插入

    如果要在二叉查找树中插入一个结点,首先要查找到结点插入的位置,然后进行插入假设插入的结点为z的话,插入的伪代码如下:

    TREE-INSERT(T, z)
    y ← NIL
    x ← T.root
    while x ≠ NIL
    	do y ←  x
    	if z.key < x.key
    		then x ← x.left
    	else x ← x.right
    z.p ← y
    if y == NIL
    	then T.root ← z       
    else if z.key < y.key
    	then y.left ← z
    else y.right ← z

    红黑树的插入和插入修复

    现在我们了解了二叉查找树的插入,接下来,咱们便来具体了解红黑树的插入操作。红黑树的插入相当于在二叉查找树插入的基础上,为了重新恢复平衡,继续做了插入修复操作。

    假设插入的结点为z,红黑树的插入伪代码具体如下所示:

    RB-INSERT(T, z)
    y ← nil
    x ← T.root
    while x ≠ T.nil
    	do y ← x
    	if z.key < x.key
    		then x ← x.left
    	else x ← x.right
    z.p ← y
    if y == nil[T]
    	then T.root ← z
    else if z.key < y.key
    	then y.left ← z
    else y.right ← z
    z.left ← T.nil
    z.right ← T.nil
    z.color ← RED
    RB-INSERT-FIXUP(T, z)

    把上面这段红黑树的插入代码,跟之前看到的二叉查找树的插入代码比较一下可以看出,RB-INSERT(T, z)前面的第1~13行代码基本上就是二叉查找树的插入代码,然后第14~16行代码把z的左孩子和右孩子都赋为叶结点nil,再把z结点着为红色,最后为保证红黑性质在插入操作后依然保持,调用一个辅助程序RB-INSERT-FIXUP来对结点进行重新着色,并旋转。

    换言之,如果插入的是根结点,由于原树是空树,此情况只会违反性质2因此直接把此结点涂为黑色;如果插入的结点的父结点是黑色,由于此不会违反性质2和性质4,红黑树没有被破坏,所以此时什么也不做。

    但当遇到下述3种情况时又该如何调整呢?

    • ● 插入修复情况1:如果当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色

      ● 插入修复情况2:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

      ● 插入修复情况3:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左子

    答案就是根据红黑树插入代码RB-INSERT(T, z)最后一行调用的RB-INSERT-FIXUP ( T z )函数 所示 的步骤进行操作 ,具体如下所示:

    RB-INSERT-FIXUP(T, z)
    while z.p.color == RED
    	do if z.p == z.p.p.left
    		then y ← z.p.p.right
    		if y.color == RED
    			then z.p.color ← BLACK               ▹ Case 1
    			y.color ← BLACK                    ▹ Case 1
    			z.p.p.color ← RED                    ▹ Case 1
    			z ← z.p.p                            ▹ Case 1
    		else if z == z.p.right
    			then z ← z.p                          ▹ Case 2
    			LEFT-ROTATE(T, z)                   ▹ Case 2
    		z.p.color ← BLACK                        ▹ Case 3
    		z.p.p.color ← RED                         ▹ Case 3
    		RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3
    	else (same as then clause with "right" and "left" exchanged)
    T.root.color ← BLACK

    下面,咱们来分别处理上述3种插入修复情况

    • 插入修复情况1:当前结点的父结点是红色,祖父结点的另一个子结点(叔叔结点)是红色。

    如下代码所示:

    while z.p.color == RED
    	do if z.p == z.p.p.left
    		then y ← z.p.p.right
    		if y.color == RED

    此时父结点的父结点一定存在,否则插入前就已不是红黑树。与此同时,又分为父结点是祖父结点的左孩子还是右孩子,根据对称性,我们只要解开一个方向就可以了。这里只考虑父结点为祖父左孩子的情况,如下图所示(勘误:图中15节点应改为13,特此说明,下同):

    对此,我们的解决策略是:将当前节点的父节点和叔叔节点涂黑,祖父结点涂红,把当前结点指向祖父节点,从新的当前节点重新开始算法。即如下代码所示:

    			then z.p.color ← BLACK               ▹ Case 1
    			y.color ← BLACK                    ▹ Case 1
    			z.p.p.color ← RED                    ▹ Case 1
    			z ← z.p.p                            ▹ Case 1  

    所以,变化后如下图所示

    于是,插入修复情况1转换成了插入修复情况2

    • 插入修复情况2:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子

    此时,解决对策是:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。即如下代码所示:

    		else if z == z.p.right
    			then z ← z.p                          ▹ Case 2
    			LEFT-ROTATE(T, z)                   ▹ Case 2
    所以红黑树由之前的:

     

    变化成:

     

    从而插入修复情况2转换成了插入修复情况3

    • 插入修复情况3:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的左孩子

    解决对策是:父节点变为黑色,祖父节点变为红色,在祖父节点为支点右旋,操作代码为:

    		z.p.color ← BLACK                        ▹ Case 3
    		z.p.p.color ← RED                         ▹ Case 3
    		RIGHT-ROTATE(T, z.p.p)                  ▹ Case 3

    最后,把根结点涂为黑色,整棵红黑树便重新恢复了平衡。所以红黑树由之前的:

    变化成:


    回顾:经过上面情况3、情况4、情况5等3种插入修复情况的操作示意图,读者自会发现,后面的情况4、情况5都是针对情况3插入节点4以后,进行的一系列插入修复情况操作,不过,指向当前节点N指针一直在变化。所以,你可以想当然的认为:整个下来,情况3、4、5就是一个完整的插入修复情况的操作流程


    四、红黑树的删除

    接下来,咱们最后来了解,红黑树的删除操作。

    "我们删除的节点的方法与常规二叉搜索树中删除节点的方法是一样的,如果被删除的节点不是有双非空子女,则直接删除这个节点,用它的唯一子节点顶替它的位置,如果它的子节点分是空节点,那就用空节点顶替它的位置,如果它的双子全为非空,我们就把它的直接后继节点内容复制到它的位置,之后以同样的方式删除它的后继节点,它的后继节点不可能是双子非空,因此此传递过程最多只进行一次。”

    二叉查找树的删除

    继续讲解之前,补充说明下二叉树结点删除的几种情况,待删除的节点按照儿子的个数可以分为三种:

    1. 没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。
    2. 只有一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。
    3. 有两个儿子。这是最麻烦的情况,因为你删除节点之后,还要保证满足搜索二叉树的结构。其实也比较容易,我们可以选择左儿子中的最大元素或者右儿子中的最小元素放到待删除节点的位置,就可以保证结构的不变。当然,你要记得调整子树,毕竟又出现了节点删除。习惯上大家选择左儿子中的最大元素,其实选择右儿子的最小元素也一样,没有任何差别,只是人们习惯从左向右。这里咱们也选择左儿子的最大元素,将它放到待删结点的位置。左儿子的最大元素其实很好找,只要顺着左儿子不断的去搜索右子树就可以了,直到找到一个没有右子树的结点。那就是最大的了。

    二叉查找树的删除代码如下所示:

    TREE-DELETE(T, z)
     1  if left[z] = NIL or right[z] = NIL
     2      then y ← z
     3      else y ← TREE-SUCCESSOR(z)
     4  if left[y] ≠ NIL
     5      then x ← left[y]
     6      else x ← right[y]
     7  if x ≠ NIL
     8      then p[x] ← p[y]
     9  if p[y] = NIL
    10      then root[T] ← x
    11      else if y = left[p[y]]
    12              then left[p[y]] ← x
    13              else right[p[y]] ← x
    14  if y ≠ z
    15      then key[z] ← key[y]
    16           copy y's satellite data into z
    17  return y

    红黑树的删除和删除修复

    OK,回到红黑树上来,红黑树结点删除的算法实现是:

    RB-DELETE(T, z) 单纯删除结点的总操作

     1 if left[z] = nil[T] or right[z] = nil[T]  
     2    then y ← z  
     3    else y ← TREE-SUCCESSOR(z)  
     4 if left[y] ≠ nil[T]  
     5    then x ← left[y]  
     6    else x ← right[y]  
     7 p[x] ← p[y]  
     8 if p[y] = nil[T]  
     9    then root[T] ← x  
    10    else if y = left[p[y]]  
    11            then left[p[y]] ← x  
    12            else right[p[y]] ← x  
    13 if y ≠ z  
    14    then key[z] ← key[y]  
    15         copy y's satellite data into z  
    16 if color[y] = BLACK  
    17    then RB-DELETE-FIXUP(T, x)  
    18 return y  

    “在删除节点后,原红黑树的性质可能被改变,如果删除的是红色节点,那么原红黑树的性质依旧保持,此时不用做修正操作,如果删除的节点是黑色节点,原红黑树的性质可能会被改变,我们要对其做修正操作。那么哪些树的性质会发生变化呢,如果删除节点不是树唯一节点,那么删除节点的那一个支的到各叶节点的黑色节点数会发生变化,此时性质5被破坏。如果被删节点的唯一非空子节点是红色,而被删节点的父节点也是红色,那么性质4被破坏。如果被删节点是根节点,而它的唯一非空子节点是红色,则删除后新根节点将变成红色,违背性质2。”

    RB-DELETE-FIXUP(T, x) 恢复与保持红黑性质的工作

     1 while x ≠ root[T] and color[x] = BLACK  
     2     do if x = left[p[x]]  
     3           then w ← right[p[x]]  
     4                if color[w] = RED  
     5                   then color[w] ← BLACK                        ▹  Case 1  
     6                        color[p[x]] ← RED                       ▹  Case 1  
     7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1  
     8                        w ← right[p[x]]                         ▹  Case 1  
     9                if color[left[w]] = BLACK and color[right[w]] = BLACK  
    10                   then color[w] ← RED                          ▹  Case 2  
    11                        x ← p[x]                                ▹  Case 2  
    12                   else if color[right[w]] = BLACK  
    13                           then color[left[w]] ← BLACK          ▹  Case 3  
    14                                color[w] ← RED                  ▹  Case 3  
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3  
    16                                w ← right[p[x]]                 ▹  Case 3  
    17                         color[w] ← color[p[x]]                 ▹  Case 4  
    18                         color[p[x]] ← BLACK                    ▹  Case 4  
    19                         color[right[w]] ← BLACK                ▹  Case 4  
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4  
    21                         x ← root[T]                            ▹  Case 4  
    22        else (same as then clause with "right" and "left" exchanged)  
    23 color[x] ← BLACK  

    “上面的修复情况看起来有些复杂,下面我们用一个分析技巧:我们从被删节点后来顶替它的那个节点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的节点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父节点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。"--saturnman。

    如果是以下情况,恢复比较简单:

    • a)当前节点是红+黑色
      解法,直接把当前节点染成黑色,结束此时红黑树性质全部恢复。
    • b)当前节点是黑+黑且是根节点, 解法:什么都不做,结束。

    但如果是以下情况呢?:

    • 删除修复情况1:当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)
    • 删除修复情况2:当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色
    • 删除修复情况3:当前节点颜色是黑+黑,兄弟节点是黑色,兄弟的左子是红色,右子是黑色
    • 删除修复情况4:当前节点颜色是黑-黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意

    此时,我们需要调用RB-DELETE-FIXUP(T, x),来恢复与保持红黑性质的工作。

    下面,咱们便来分别处理这4种删除修复情况。

    删除修复情况1:当前节点是黑+黑且兄弟节点为红色(此时父节点和兄弟节点的子节点分为黑)。

    解法:把父节点染成红色,把兄弟结点染成黑色,之后重新进入算法(我们只讨论当前节点是其父节点左孩子时的情况)。此变换后原红黑树性质5不变,而把问题转化为兄弟节点为黑色的情况(注:变化前,原本就未违反性质5,只是为了把问题转化为兄弟节点为黑色的情况)。 即如下代码操作:

    //调用RB-DELETE-FIXUP(T, x) 的1-8行代码
     1 while x ≠ root[T] and color[x] = BLACK
     2     do if x = left[p[x]]
     3           then w ← right[p[x]]
     4                if color[w] = RED
     5                   then color[w] ← BLACK                        ▹  Case 1
     6                        color[p[x]] ← RED                       ▹  Case 1
     7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
     8                        w ← right[p[x]]                         ▹  Case 1

    变化前:

     

    变化后: 

     

    删除修复情况2:当前节点是黑加黑且兄弟是黑色且兄弟节点的两个子节点全为黑色。

    解法:把当前节点和兄弟节点中抽取一重黑色追加到父节点上,把父节点当成新的当前节点,重新进入算法。(此变换后性质5不变),即调用RB-INSERT-FIXUP(T, z) 的第9-10行代码操作,如下:

    //调用RB-DELETE-FIXUP(T, x) 的9-11行代码
    9                if color[left[w]] = BLACK and color[right[w]] = BLACK
    10                   then color[w] ← RED                          ▹  Case 2
    11                        x p[x]                                  ▹  Case 2

    变化前

     

    变化后

     

    删除修复情况3:当前节点颜色是黑+黑,兄弟节点是黑色,兄弟的左子是红色,右子是黑色。

    解法:把兄弟结点染红,兄弟左子节点染黑,之后再在兄弟节点为支点解右旋,之后重新进入算法。此是把当前的情况转化为情况4,而性质5得以保持,即调用RB-INSERT-FIXUP(T, z) 的第12-16行代码,如下所示:

    //调用RB-DELETE-FIXUP(T, x) 的第12-16行代码
    12                   else if color[right[w]] = BLACK
    13                           then color[left[w]] ← BLACK          ▹  Case 3
    14                                color[w] ← RED                  ▹  Case 3
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3
    16                                w ← right[p[x]]                 ▹  Case 3

    变化前:

     

    变化后:

    删除修复情况4:当前节点颜色是黑-黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意。

    解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确,即调用RB-INSERT-FIXUP(T, z)的第17-21行代码,如下所示:

    //调用RB-DELETE-FIXUP(T, x) 的第17-21行代码
    17                         color[w] ← color[p[x]]                 ▹  Case 4
    18                         color[p[x]] ← BLACK                    ▹  Case 4
    19                         color[right[w]] ← BLACK                ▹  Case 4
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
    21                         x ← root[T]                            ▹  Case 4

    变化前:

     

    变化后:

    最后值得一提的是上述删除修复的情况1~4都只是树的局部,并非树的整体全部,且删除修复情况3、4在经过上面的调整后,调整还没结束(还得继续调整直至重新恢复平衡,只是图并没有画出来)。
    后面会继续修改完善下本文,感谢关注,thanks。

    July、二零一四年九月十五日修订。

    ----------------

    之前在学校寝室画红黑树画了好几个钟头,贴俩张图:

      红黑树插入修复的3种情况:

     

      红黑树删除修复的4种情况:


    updated

    继续请看本文的github优化版本:https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md,或看看这个PPT:http://vdisk.weibo.com/s/zrFL6OXJNfNVU。另,对应新书《编程之法:面试和算法心得》3.1节。July、二零一四年五月三日。

    展开全文
  • 程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结 作者:July--结构之法算法之道blog之博主。 时间:2010年10月-2018年5月,一直在不断更新中.. 出处:...

       程序员面试、算法研究、编程艺术、红黑树、机器学习5大经典原创系列集锦与总结


    作者:July--结构之法算法之道blog之博主。
    时间:2010年10月-2018年5月,一直在不断更新中..
    出处:http://blog.csdn.net/v_JULY_v 
    说明:本博客中部分文章经过不断修改、优化,已集结出版成书编程之法:面试和算法心得》。

    前言
        开博4年有余,回首这4年,自己的研究兴趣从最初的编程、面试、数据结构、算法,转移到最近的数据挖掘、机器学习之上,而自己在本blog上也着实花费了巨大的时间和精力,写的东西可能也够几本书的内容了。然不管怎样,希望我能真真正正的为读者提供实实在在的价值与帮助。

        下面,敬请观赏。有任何问题,欢迎随时不吝指正(同时,若你也能帮助回复blog内留言的任何朋友的问题,欢迎你随时不吝分享&回复,我们一起讨论,互帮互助,谢谢)。

    无私分享,造福天下
        以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列,及数据挖掘十大算法等5大经典原创系列作品与一些重要文章的集锦:
    一、微软面试100题系列

        上述微软面试100题系列(共计11篇文章,300多道面试题)的PDF文档近期已经制作出来,其下载地址为:微软面试100题系列之高清完整版PDF文档[带目录+标签]by_July_pdf-C++文档类资源-CSDN下载

    二、十五个经典算法研究与总结、目录+索引

        最新的十五个经典算法研究的PDF文档0积分下载地址如下(1个月5000+人次下载)scikit-learn机器学习:常用算法原理及编程实战电子书,黄永昌-文档类-CSDN下载

       「此外原来的十三个经典算法研究[带目录+标签]的PDF文档,Csdn下载地址:http://download.csdn.net/source/3427838新浪爱问共享下载地址:十五个经典算法研究与总结、目录+索引(by_... - 爱问共享资料 

    三、程序员编程艺术第一~四十章集锦与总结

        程序员编程艺术第1~37章带标签的最新PDF下载地址为(3天3000人下载):VIP会员电子书,CSDN-文档类-CSDN下载

       编程艺术github优化版阅读地址:The-Art-Of-Programming-By-July/Readme.md at master · julycoding/The-Art-Of-Programming-By-July · GitHub

       重大消息:经过反复修改、优化,编程艺术系列最终成书出版,并改名为《编程之法:面试和算法心得》,目前京东、当当、亚马逊等各大网店均已有现货销售。京东抢购地址:《编程之法:面试和算法心得(异步图书出品)》(July)【摘要 书评 试读】- 京东图书

    四、红黑树、B树、R树、Trie树

    五、数学·数据挖掘·机器学习·深度学习系列

    六、其它重要文章节选

    后记
        世上本无路,走的人多了,也就成了路。世上本无免费的午餐,分享的人多了,也就造就了开源的辉煌。

        如果你发现了本blog中的任何一问题,请一定不吝指正,thanks。此外,你可以永久通过搜索引擎搜索本博客名称的前4个字,即:“结构之法” 这4个关键字,进入本博客。

        最后,感谢CSDN,感谢所有一直以来关注本blog的所有朋友。谢谢大家,谢谢。

    转发送书

        欢迎大家转发下条微博:Sina Visitor System我会不定期抽奖,经典IT图书大赠送(同时,下面个人最喜欢的三篇文章已收录到今2015年10月14日上市销售的我的新书《编程之法:面试和算法心得》中:《编程之法:面试和算法心得(异步图书出品)》(July)【摘要 书评 试读】- 京东图书):


    2015年,July团队正式创业,上半年推出在线教育网站:精品课程(面试、算法、机器学习在线课程)。July、二零一五年九月十五日。

    另,我的新书《编程之法:面试和算法心得》终于在2015年10月14日上架开卖了!京东抢购地址《编程之法:面试和算法心得(异步图书出品)》(July)【摘要 书评 试读】- 京东图书。目前,京东、当当、亚马逊等各大网店均已有现货销售。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 132,211
精华内容 52,884
关键字:

红黑树