精华内容
下载资源
问答
  • 这种情况下,S的左孩子与右孩子必NIL,否则原来的红黑树就不平衡. 那么在对P的向上递归过程中,也会出现这种情况,即对应的S及S的孩子全为黑色. NIL结点的意义之一是不是就在于:向上递归的过程中识别出这种情况? 又...
  • 这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都 O(logn)。它的统计性能要好于平衡二叉树(AVL树),这也正解释了红黑树为什么使用这么广的原因。 红黑树的5个特性: 每个结点要么是红色,...

    红黑树介绍

    红黑树本质上是一种二叉查找树,但它在二叉查找树的基础上额外添加了一个标记(颜色),同时具有一定的规则。这些规则使红黑树保证了一种平衡,插入、删除、查找的最坏时间复杂度都为 O(logn)。它的统计性能要好于平衡二叉树(AVL树),这也正解释了红黑树为什么使用这么广的原因。

    红黑树的5个特性:

    1. 每个结点要么是红色,要么是黑色。

    2. 根节点永远是黑色的。

    3. 所有叶子结点(nil结点)都是黑色的。(这里说的叶子结点是NULL结点)

    4. 每个红色结点的两个子结点一定都是黑色(不能有两个连续(父-子连续)的红色结点,可以有连续的黑色结点)。

    5. 从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点。(黑高相同)

    正由于平衡二叉树一样,由性质决定了二叉树是不是一个平衡二叉树,当向平衡二叉树插入一个结点后可能失衡的依据也是性质决定的,性质定义了什么是平衡二叉树。所以说,红黑树的性质解释了什么是红黑树,以及插入结点后,树是否还能保持红黑树的性质。

    红黑树是一个自平衡(不是像AVL绝对的平衡)的二叉查找树BST,但是也是需要保持平衡,它不是像AVL那样,刻意的保持平衡,而是由红黑树的性质间接保持了Reb-Black-Tree的平衡,如不能有两个连续的红色结点,连续插入两个结点必然会使性质 4不成立,通过recolor或者rotation来满足性质4,调整的过程也间接使红黑树维持了相对平衡。如果熟悉了AVL如何调整平衡,那么我感觉Red-Black-Tree的调整平衡应该也不在话下。

    如下图,就是一棵红黑树,NIL是一个黑色的空结点。

    在这里插入图片描述

    红黑树结点的插入

    红黑树结点的插入操作:

    1. 红黑树本身是一棵二叉查找树,所以在插入新结点时,完全可以按照二叉查找树插入结点的方法,找到新结点插入的位置。
    2. 将插入的结点初始化为红色,为什么是红色而不是黑色?若为黑色,则违背性质5。
    3. 插入结点后,可能会破坏红黑树的性质,此时需要调整二叉查找树,通过recolor或者rotatin,使其重新成为红黑树。

    红黑树的调整主要有两个操作,比AVL树多了一个操作:

    1. recolor(变色,重新标记为黑色或红色)
    2. rotation(旋转)

    优先recolor,recolor不能解决在rotation。

    红黑树中插入结点后,主要有3大种6小种:

    • 红色结点作为根节点,涂黑,直接插入。
    • 父结点是黑结点,直接插入红色结点。
    • 父结点是红色结点,这时候直接插入红色结点,不满足性质4。这时候就需要根据其叔叔结点是红色还是黑色分别处理。(分为6小种)
      • 叔叔结点是红色,uncle and parent discolor, 左右支处理情况相同
      • 叔叔结点是黑色,父结点位于祖父结点的左分支,插入结点位于父结点的左分支,旋转加变色;插入结点位于父结点的右分支,旋转旋转加变色。
      • 叔叔结点是黑色,父结点位于祖父结点的右分支,插入结点位于父结点的右分支,旋转加变色;插入结点位于父结点的左分支,旋转旋转加变色。
        在这里插入图片描述

    在这里插入图片描述

    图(4)中存在一个错误,即旋转后P应该是C的子结点,代码中需要提前x = x->parent,然后下次循环时x->parent->parent才能正确处理。

    图(3)中U也可以看做是NIL结点(空结点),对于图(1)根节点变红,这不是违背了性质2,代码最后对根结点做了处理,最后总会变黑的!

    在看代码之前,我觉得有必要了解红黑树结构的代码定义以及初始化一棵红黑树。

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef enum {RED, BLACK} ColorType;
    typedef int ElemType;
    /*树结点类型定义*/
    typedef struct RBNode {
        ElemType key;
        struct RBNode * lchild;
        struct RBNode * rchild;
        struct RBNode * parent;
        ColorType color;
    } RBNode, *RBTree;
    
    /*我把它理解为树的头结点*/
    typedef struct RBTRoot {
        RBTree root;
        RBTree nil;
    } RBTRoot;
    
    /**
    * 初始化一棵红黑树头结点
    */
    RBTRoot* RBTree_Init() {
       RBTRoot* T = (RBTRoot*) malloc(sizeof(RBTRoot));
       T->nil = (RBTree) malloc(sizeof(RBNode));
       if (T == NULL || T->nil == NULL)
            exit(-1);
       T->nil->lchild = T->nil->rchild = NULL;
       T->nil->parent = NULL;
       T->nil->color = BLACK;
    
       T->root = T->nil;
       return T;
    }
    

    下面以插入元素{10,9,8,7,6,5,4,3,2,1}为例,查看红黑树如何从0构造为一棵树。结合动图看代码,我觉得能更容易理解代码:

    首先插入元素10和9
    在这里插入图片描述

    继续插入8之后,破坏了红黑树,此时需要旋转加变色了。

    在这里插入图片描述

    看下涉及到的具体代码

    /**
    * 插入结点
    * @param T 红黑树的根
    * @param key 插入结点值
    * @description 找到位置,初始化结点,插入结点,调整红黑树
    */
    void RBTree_Insert(RBTRoot** T, ElemType key) {
        RBTree pre; // pre保存了上一个x位置的指针(引用)
        RBTree x = (*T)->root;
        pre = x;
        while (x != (*T)->nil) {
            pre = x;
            if (x->key == key) {
                printf("\n%d已存在\n",key);
                return;
            } else if (key < x->key)
                x = x->lchild;
            else
                x = x->rchild;
        }
    
        // 初始化插入结点,将结点设为红色
        x = (RBTree) malloc(sizeof(RBNode));
        x->key = key;
        x->lchild = x->rchild = (*T)->nil;
        x->color = RED;
        x->parent = pre;
    
        // 根节点引用没有发生变化,
        // 插入根节点,直接插入,否则,向保存x父结点的pre左孩子或者右孩子插入x
        if ((*T)->root == (*T)->nil)
            (*T)->root = x;
        else if (key < pre->key)
            pre->lchild = x;
        else
            pre->rchild = x;
        // 插入之后,进行修正处理
        RBTree_Insert_FixUp(*T, x);
    }
    
    /**
    * 红黑树插入修正函数
    * @param T 红黑树的根
    * @param x 插入的结点
    * @description 用到变色和旋转
    */
    void RBTree_Insert_FixUp(RBTRoot* T, RBTree x) {
       // 当前结点的父结点为红色需调整 注:根节点 parent是指向nil
       // (1) 叔叔结点是红色: (1.1,1.2)左右分支,一样处理,变色即可
       // (2) 叔叔结点是黑色:(2.1,2.2)左分支下左右孩子 (2.3,2.4)右分支下左右孩子
    
       while (x->parent->color == RED) {
            // 首先父结点是祖父结点的左分支还是右分支
            if (x->parent == x->parent->parent->lchild) {
                // 判断叔叔结点颜色
                if (x->parent->parent->rchild->color == RED) {
                    // 将父结点和叔叔结点改为黑色,祖父结点改为红色
                    x->parent->color = BLACK;
                    x->parent->parent->rchild->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                } else {
                    // 叔叔结点的颜色为黑色:分父结点的(1)左孩子 (2)右孩子
                    // (1)父结点左孩子:父结点颜色变为BLACK,祖父节点变RED,右旋处理
                    if (x->parent->lchild == x) {
                        x->parent->color = BLACK;
                        x->parent->parent->color = RED;
                        // 注意这里是x->parent->parent 以祖父节点作为旋转的根节点
                        RBTree_R_Rotate(T, x->parent->parent);
                    } else {
                    // (2)右孩子,先左旋转,转为上面(1)父结点左孩子的情况
                    // 借助循环下次就会运行到(1)然后右旋
    
                        RBTree_L_Rotate(T, x->parent);
                    }
                }
            } else {
                // 祖父结点的右分支
                if (x->parent->parent->lchild->color == RED) {
                    // 叔叔结点为红色,左右分支都一样处理
                    x->parent->color = BLACK;
                    x->parent->parent->lchild->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                } else {
                    // 叔叔为黑色
                    // 父结点的右分支
                    if (x->parent->rchild == x) {
                        x->parent->color = BLACK;
                        x->parent->parent->color = RED;
                        RBTree_L_Rotate(T, x->parent->parent);  // 左旋
                    } else {
                        // 父结点的左分支
                        RBTree_R_Rotate(T, x->parent);  // 右旋
                    }
                }
            }
            // 每次循环结束需要将根节点涂黑,因为可能在某次变色时,根节点变为红色
            // 不可放在循环外部
            // T->root->color = BLACK;
       }
        T->root->color = BLACK;
    }
    
    void RBTree_R_Rotate(RBTRoot* T, RBTree x) {
        RBTree lc;
        lc = x->lchild;
        x->lchild = lc->rchild;
        if (lc->rchild != T->nil)
            lc->rchild->parent = x;
    
        lc->parent = x->parent;
        if (lc->parent == T->nil)
            T->root = lc;
        else if (x->parent->lchild == x)
            x->parent->lchild = lc;
        else if (x->parent->rchild == x)
            x->parent->rchild = lc;
        x->parent = lc;
        lc->rchild = x;
    }
    

    动手构建一棵红黑树,构建的过程中去代码中找构建的规律,去编写代码理解代码。接下来把剩余的结点插入。
    在这里插入图片描述

    这一个地方需要关注一下在插入3之后,眼看红黑树慢慢演变为单支树,但是由于其性质,避免了单支树的产生。这也是为什么红黑树也是一棵自平衡树。

    在这里插入图片描述

    参考

    展开全文
  • 删除结点同时存在左子树和右子(双支节点),此时可以将它的直接前驱或者直接后继代替删除结点的位置,删除该结点就转化删除它的直接后继或者直接前驱的结点,而删除结点的直接后继或者直接前驱结点只有两种情况...

    红黑树结点的删除

    首先来回顾一下二叉树结点的删除,总共分为了三种情况:

    1. 删除叶子结点,此时可以直接删除
    2. 删除结点有左子树或者右子树的单支结点,将左子树或者右子树结点直接推到删除的结点即可
    3. 删除结点同时存在左子树和右子树(双支节点),此时可以将它的直接前驱或者直接后继代替删除结点的位置,删除该结点就转化为删除它的直接后继或者直接前驱的结点,而删除结点的直接后继或者直接前驱结点只有两种情况,要么是叶子结点要么是单支结点,此时问题就间接转化为了1,2两种情况,这里涉及到两个转化,一定要理解透彻。

    红黑树的删除,确实不容易理解,主要是情况有点多,并且这多种情况有的可以转化,也有的情况根本不存在。红黑树的删除终究是围绕二叉查找树的删除为基础,在其上增加了颜色和红黑树的性质,限制了红黑树删除结点后需要做出相应的调整,以满足删除结点后不改变红黑树。

    红黑树的删除:

    (1)删除叶子结点(无论哪种情况,我们最终处理的就是删除叶子结点的过程2,3情况最后还是转化为删除叶子结点)

    红色:直接删除,此时不影响红黑树。

    黑色:情况多,后面会主要讨论

    在这里插入图片描述

    (2)删除单支结点(结点只存在左孩子或者右孩子)

    只能是黑红单支(B-R)

    在这里插入图片描述

    竖线代表分支可左可右。

    上述三种形态(6种)的单支结点,根本不可能存在,所以说删除单支结点只能是删除黑红单支的黑结点。删除黑色结点后,黑高减1,将红色子结点直接推到删除结点,并且将红色结点涂黑,此时黑高又恢复到未删除结点之前的状态。(删除红色子节点—>情况1)

    在这里插入图片描述

    (3)删除双支节点

    前面我们已经讲过了,删除的结点如果是双支节点存在左右子树的情况下,我们通常用删除结点的前驱节点的值或者后继结点的值代替,然后将问题转化为删除它的前驱或者后继结点。这里以后继为例(删除结点的右孩子的左子树最左的结点),删除的后继结点只有两种情况,D’是叶子结点或者单支结点,问题可以进一步转化为(1)、(2)两种情形。进一步细分的话情形1有红黑两种情况,情形2删除的结点D‘必定是黑结点直接转为(2)处理。

    单支结点必定是黑红

    在这里插入图片描述

    这里的图特意将黑色的NULL节点给加上,这是因为删除节点被摘掉后,我们可以用一个黑色的节点接上,从而进行统一处理。

    为什么删除黑色叶子结点这么复杂

    删除红色叶子结点、删除单支结点,删除的如果是这些类型的结点,在经过一定的算法调整后,黑高bh一定不会发生变化,通过局部调整,子树黑高没变化,那么整棵树的黑高也就不会发生变化。

    但是当删除的结点是黑色叶子结点的时候,在经过算法调整后,黑高就不一定不会变化了。某些情况调整后,它的黑高不会变化,但是某些情况调整后,黑高会变化,此时就需要递归向上处理,直至根节点,这种情况属于牵一发而动全身。

    删除结点并不代表删除所在位置的结点结构

    红黑树中,删除某个结点采取的是值覆盖的方法,将整个删除结点的过程转化成删除“用来覆盖的值”所在结点的过程,这个被拿来做值覆盖所在的结点一定是叶子结点删除过程最终转化为删除红黑树中重复值的叶子结点

    下面分析删除黑色叶子结点,也就是情况最复杂的一种:

    删除黑色叶子结点后,红黑树的调整需要考虑到父结点、兄弟结点和兄弟结点的左右孩子结点,我们把这些结点的情况列出进行分析。

    在这里插入图片描述

    在这里插入图片描述

    换种方式去理解

    红黑树删除黑色叶子结点调整的核心

    在这里插入图片描述

    黑高

    从某一结点到叶子结点(其子孙结点)的黑色结点数目,用bh(x)来表示。

    bh(A->B->叶子)表示从A走到B再走到某一个叶子路径的黑色节点数量(A与B,B与叶子之间可能间隔了多个节点)。

    本文余下内容均指的是删除黑色的叶子节点后引发的一系列平衡操作。比如P->D->N,删除D(黑色)后,N接至父节点:P->N。

    这里所指的叶子结点不是NULL结点,删除D后,N可以看做是填补的一个黑色nil结点

    因为删除了一个黑色节点(N的父节点D),经过N的路径的黑色数量减1,即bh(P->N->叶子) 比 bh(P->S->叶子) 少1。平衡的方式有:

    • bh(P->N->叶子)不变,bh(P->S->叶子)减1,此时已经子平衡;然而h(GP->P->叶子)还是会比bh(GP -> U ->叶子)少1。此时需要将P当作新的N,向上递归处理,这种情况就好像牵一发而动全身。[黑高变化]
    • bh(P->N->叶子)加1,bh(P->S->叶子)不变,也就是恢复了原来的状态,此时已经平衡,因为bh(GP->P->叶子)=bh(GP -> U ->叶子)。[黑高不变]

    平衡的思路主要就是基于以上两种方式,另外要注意的是,红色和红色不能连一起的约束也不能违反。理解这个比较重要。

    下面讨论删除黑色叶子结点的各种情况:

    在这里插入图片描述

    1、当前结点为黑根结点

    删除黑根叶子结点,无需做平衡处理,因为树已经变成空树了。

    2、兄弟结点为黑色(S=黑)

    • 2.1、 兄弟的子结点全黑(SL/SR=黑)

      兄弟节点的子节点全为黑色,也就意味着兄弟节点(S)可以涂红而不会和子冲突。S涂红后,也就实现了子平衡,这时候我们看父节点是红是黑,再做处理。

      • 2.1.1、父结点为黑色(P=黑)

        此时将S涂红,父节点作为新的平衡节点N,递归上去处理。 这个也就是之前提到的bh(P->N->叶子)不变,bh(P->S->叶子)减1;而bh(GP->P->叶子),依然会比bh(GP -> U ->叶子)少1,所以要递归上去处理。

        在这里插入图片描述

        结点意义:N、SL、SR看做NIL结点去理解,N是D删除之后填补的一个结点

        注:每种情况的红黑树都是不平衡的(不满足红黑树性质),N在每种情况里面都是充当了一个填补的NIL结点,填补被删除的D。

      • 2.1.2、父结点为红色(P=红)

        此时将S涂红,P涂黑,平衡结束。 S涂红后,h(P->N->叶子)不变,h(P->S->叶子)-1,实现子平衡;因为P节点是红色的,如果将它涂黑,h(P->N->叶子)和h(P->S->叶子)均会+1,就可以恢复原来的状态了,而不用递归上去。

      在这里插入图片描述

    • 2.2、兄弟子结点非全黑

      所谓的不全黑包括:[SL红, SR红]、[SL黑,SR红]、[SL红,SR黑]。如果其中一个为黑,另外一个肯定是红
      以全黑/非全黑作为分类,是因为全黑时无论N是在左子还是右子,其处理方式是一样的。 而非全黑则要看N所处的位置(或者说S所处的位置)进行特定方向的旋转。

      • 2.2.1、S在左分支,SL红;S在右分支,SR红

        P为支点右旋;交换P和S颜色,SL涂黑;平衡结束。
        这里的平衡思路其实就是:h(P->S->叶子)不变(因为SL涂黑补回来了),h(P->N->叶子)+1(因为多了个黑色P)。

        在这里插入图片描述

        结点意义:SL一定是真实结点,SR可以看做是真实红结点或者NIL结点,N是NIL结点

        在代码中,S的颜色不一定是黑色,S的颜色是由P决定的,s->color = s->parent->color,这样做的目的是防止旋转后的结点S与GP冲突。

        比如P颜色为红色,旋转后如果S不改成P结点的颜色值,就会导致bh+1,破坏红黑树的性质。

        所以说为了不破坏红黑树的性质,通常直接将P的颜色给S。

        明白了上面,这个,与其对称的一种情形就好理解了。

        在这里插入图片描述

        结点意义:SR一定是真实结点,SL可以看做是真实红结点或者NIL结点,N是NIL结点

      • 2.2.2、S在左分支,SR红,S在右分支,SL红

        S为支点左旋,交换S和SR颜色(SR涂黑,S涂红) ,此时转至情形2.2.1-(1) S左-SL红 进行处理。

        转化为单支只能是黑红!

      在这里插入图片描述

      结点意义:SR一定是真实结点,SL可以看做是真实红结点或者NIL结点,N是NIL结点。并且SL排除在了虚线框内,它对红黑树意义不大。

      同理也存在与其对称的一种情况

      在这里插入图片描述

      结点意义:SL一定是真实结点,SR可以看做是真实红结点或者NIL结点,N是NIL结点

    3、兄弟结点为红色(S=红)

    兄弟结点为红色,则父子结点颜色必为黑色,否则不满足性质4

    S在左分支,以P进行右旋;S在右分支,以P进行左旋;旋转后交换P和S的颜色(S涂黑,P涂红),N兄弟结点变为黑色,转化为情况2处理。

    在这里插入图片描述

    结点意义:SL、SR一定是真实结点,N是NIL结点

    至此,我们介绍完了删除结点是黑色叶子结点的所有情况,在实际编程中,如何进行考虑?

    1. 删除结点是红色,简单处理
    2. 删除结点是黑色,看兄弟结点颜色
      1. 兄红,以父结点旋转涂色,转为兄黑处理。
      2. 兄黑,看兄弟结点的子结点是否全黑
        1. 全黑,根据父结点的颜色进行相应处理
        2. 不全黑,看兄弟所在位置及兄弟孩子的颜色和位置。

    代码实现

    /**
    * 删除指定元素的结点
    * @param T 红黑树的头结点
    * @param key 删除的元素值
    * @description 找到结点元素等于key的结点,删除结点,调整红黑树
    */
    void RBTree_Delete(RBTRoot** T, ElemType key) {
        RBTree target, realDel, child;
        // 1.在红黑树中查找指定元素等于key的结点,可以以下逻辑封装到方法里面
        // target = RBTreeSearch(root, key);
        target = (*T)->root;
        while (key != target->key && target != (*T)->nil) {
            if (key < target->key)
                target = target->lchild;
            else if (key > target->key)
                target = target->rchild;
        }
        if (target == (*T)->nil)
            return; //树中没有key结点
    
        // 2. 判断删除结点是叶子、单支、双支,找到删除结点的真正位置
        // 2.1 如果为叶子结点或者单支结点,删除结点的真正位置就是其本身
        // 2.2 如果为双支结点,删除结点的真正位置为后继结点(Successor)右孩子左子树最左边的结点
        if (target->lchild == (*T)->nil || target->rchild == (*T)->nil)
            realDel = target;
        else {
            realDel = target->rchild;
            while (realDel->lchild != (*T)->nil) {
                realDel = realDel->lchild;
            }
            // 处理完毕之后,readDel不会存在左分支
        }
    
        // 处理完毕之后,readDel最多有一个孩子
        //找到删除结点的孩子结点,之后移植结点需要用到child
        if (realDel->lchild != (*T)->nil)
            child = realDel->lchild;    // 只有左单支走这一步
        else
            child = realDel->rchild;    // 叶子结点或者右单支走这一步
    
        // 3. 移植结点:结点变化父结点,左右子树
    
        // 建立结点关联
    
        // 如果是nil结点,则将空的叶子结点推到删除空缺的位置,
        // 这一步其实就是让nil结点代替删除的结点,虚设黑结点
        // 否则将子结点推到父结点
        child->parent = realDel->parent;
    
        if (realDel->parent == (*T)->nil)
            (*T)->root = child;
        else if (realDel->parent->lchild == realDel)
            realDel->parent->lchild = child;
        else if (realDel->parent->rchild == realDel)
            realDel->parent->rchild = child;
    
        // 4. 如果删除结点发生了转化,比如删除结点为双支结点,那么就转化为后继结点被删
        // 而为了不移动大量指针,这里只是将值复制到删除结点,然后在删除后继结点
        if (target != realDel)
            target->key = realDel->key;
    
        // 5.删除结点是黑色的需要调整,调整的是已经移植的树,传递child,而非realDel
        if (realDel->color == BLACK)
            RBTree_Delete_FixUp(*T, child);
    
        // 6. 释放结点
        free(realDel);
    }
    
    /**
    * 红黑树删除修正函数
    * @param T 头结点
    * @param p 删除结点的父结点
    * @param n 删除结点
    * @description 找到结点元素等于key的结点,删除结点,调整红黑树
    */
    void RBTree_Delete_FixUp(RBTRoot* T, RBTree n) {
        RBTree s;
        // 单支黑红结点不会进入while,因为替代结点n为红色,n结点变色即可
        // 进入循环体的一定 叶子结点 为黑色的这种情况
        while (n != T->root && n->color == BLACK) {
    
            // 兄在右子树
            if (n == n->parent->lchild) {
                s = n->parent->rchild;  // 找到其兄弟结点,其子必为双黑
                // 第一种情况:兄红
                if (s->color == RED) {
                    s->color = BLACK;
                    n->parent->color = RED;
                    RBTree_L_Rotate(T, n->parent);
                    // 此时,兄弟结点必为黑色,转为情况2,3,4处理
                    s = n->parent->rchild;
                }
                // 第二种情况:兄黑,子全黑
                // 处理方式,兄涂红色,n指向父结点,下次while循环,如果父为红色,结束循环,
                // 循环跳出后会设置父结点为黑,也就是笔记提到的2.1.1情况。如果父为黑色,此时就需要
                // 递归向上处理,以parent为n,再找其兄弟结点,通过局部平衡达到全局平衡。
                // s->color == BLACK判断并没有多大意义,
                // 第一种情况被处理后兄结点为黑,其他情况兄结点一定为黑,所以说判断可加可不加
    
                if (s->color == BLACK &&
                    s->lchild->color == BLACK &&
                    s->rchild->color == BLACK) {
                    s->color = RED;
                    n = n->parent;
                }
    
                // 3,4两种情况包括了红红,红黑,黑红,但是必须有一个if存在限制,
                // 防止左右双红都会进入if处理
                // 第三种情况:兄黑,兄在右子树,左孩子红色
                if (s->rchild->color == BLACK &&
                    s->lchild->color == RED ) {
                    s->color = RED;
                    s->lchild->color = BLACK;
                    RBTree_R_Rotate(T, s);
                    s = n->parent->rchild;
                    // 一环接一环,处理后s变为情况4
                    // 转为情况4处理
                }
                // 第四种情况:兄黑,兄在右子树,右孩子红色
                if (s->rchild->color == RED) {
                    // 左红右红或者右红左黑都进入该条件处理
                    // 使用父结点的颜色,目的是旋转S结点(新的父结点)不会和GP冲突
                    s->color = n->parent->color;
                    n->parent->color = BLACK;
                    s->rchild->color = BLACK;
                    RBTree_L_Rotate(T, n->parent);
                    s = T->root;
                }
            } else {
            // 兄在左子树
                s = n->parent->lchild;
                if (s->color == RED) {
                    s->color = BLACK;
                    n->parent->color = RED;
                    RBTree_R_Rotate(T, n->parent);
                    s = n->parent->lchild;
                }
                if (s->lchild->color == BLACK && s->rchild->color == BLACK) {
                    s->color = RED;
                    n = n->parent;
                }
                if (s->lchild->color == BLACK && s->rchild->color == RED) {
                    s->color = RED;
                    s->rchild->color = BLACK;
                    RBTree_L_Rotate(T, s);
                    s = n->parent->lchild;
                }
                if (s->lchild->color == RED) {
                    s->color = n->parent->color;
                    n->parent->color = BLACK;
                    s->lchild->color = BLACK;
                    RBTree_R_Rotate(T, n->parent);
                    n = T->root;
                }
            }
        }
    
        n->color = BLACK;
    }
    
    

    看图时刻:

    (1) 删除结点是红色叶子结点(001)和单支结点(002)的动态演示。

    (2) 删除结点是双支结点(009),这里将其转化为删除前驱结点处理。而其前驱有位红色叶子结点,直接删除即可。
    在这里插入图片描述

    (3) 删除结点是双支结点(009),转为前驱处理,换一种角度来想,也可以是直接删除(008)结点,只不过删除(009)多了一步查找转化的过程。这里前驱是黑色结点,要根据兄弟结点,父结点进行分析。

    在这里插入图片描述

    分析下面这张动图

    在这里插入图片描述

    不难发现(008)的兄弟结点都为红色,当然是按最简单的方式处理,即兄黑左分支,兄左孩子红,直接旋转涂色即可。

    上面介绍的这两种情况都属于兄弟子结点为非全黑的情况

    回想一下代码中的处理是怎样的。

    (4) 假若删除(0012)结点,情况属于兄黑子全黑,(0014)哪有子全黑?对于每个叶子结点都有一个nil结点,这里可以把(0014)的子结点理解为nil结点。第一次调整以11为根的子树达到局部平衡,但是他的黑高相比之前的以12结点为根的子树差一个单位,所以就必须以11为N,情况好像转为以11为待删除结点,兄结点(007)为黑,继续调整。另外也可以网上大多数贴子介绍的那样理解,这里11具有了双重黑色,需要把双重黑色继续上移至根节点,之后去除一层黑色。

    在这里插入图片描述

    兄黑子全黑

    这种情况如果细分的话就属于:兄黑子全黑,父结点为黑的情况。

    同样你也可以自己推导兄黑子全黑,父为红的情况。

    (5) 最后列出兄红的情况,最终转为兄黑处理。

    在这里插入图片描述

    从上面几个双支结点的例子我们可以看出,双支结点的处理实质还是转化为单支结点或者叶子结点的处理,就是平衡查找树删除的那两种情况。在删除调整函数中,也主要是对删除叶子结点为黑色的进行逻辑处理判断。

    完整代码:

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef enum {RED, BLACK} ColorType;
    typedef int ElemType;
    /*树结点类型定义*/
    typedef struct RBNode {
        ElemType key;
        struct RBNode * lchild;
        struct RBNode * rchild;
        struct RBNode * parent;
        ColorType color;
    } RBNode, *RBTree;
    
    /*我把它理解为树的头结点*/
    typedef struct RBTRoot {
        RBTree root;
        RBTree nil;
    } RBTRoot;
    
    /**
    * 初始化一棵红黑树头结点
    */
    RBTRoot* RBTree_Init() {
       RBTRoot* T = (RBTRoot*) malloc(sizeof(RBTRoot));
       T->nil = (RBTree) malloc(sizeof(RBNode));
       if (T == NULL || T->nil == NULL)
            exit(-1);
       T->nil->lchild = T->nil->rchild = NULL;
       T->nil->parent = NULL;
       T->nil->color = BLACK;
    
       T->root = T->nil;
       return T;
    }
    
    
    /**
    * 相比于AVL,RBtree涉及的点多,但是
    * 旋转只管旋转,不管颜色.
    * 旋转:变化左右孩子,父结点
    * 注:这里用到的是一级指针,因为改变的是结构体内部变量的地址引用,
    * 并没有改变*T或者x所指的引用地址,都是在其地址上操作的,所以
    * 用一级指针就可以生效。
    */
    void RBTree_L_Rotate(RBTRoot* T, RBTree x) {
        RBTree rc;
        rc = x->rchild;
        x->rchild = rc->lchild;
        // 如果根节点左子树有右孩子,需更改父结点
        if (rc->lchild != T->nil)
            rc->lchild->parent = x;
        // 更改rc的父结点
        rc->parent = x->parent;
        // 判断之前的结点是否是根节点,根节点parent指向nil
        if (x->parent == T->nil) {
            T->root = rc;
        } else if (x->parent->lchild == x) {
            x->parent->lchild = rc;
        } else if (x->parent->rchild == x) {
            x->parent->rchild = rc;
        }
        x->parent = rc;
        rc->lchild = x;
    }
    
    void RBTree_R_Rotate(RBTRoot* T, RBTree x) {
        RBTree lc;
        lc = x->lchild;
        x->lchild = lc->rchild;
        if (lc->rchild != T->nil)
            lc->rchild->parent = x;
    
        lc->parent = x->parent;
        if (lc->parent == T->nil)
            T->root = lc;
        else if (x->parent->lchild == x)
            x->parent->lchild = lc;
        else if (x->parent->rchild == x)
            x->parent->rchild = lc;
        x->parent = lc;
        lc->rchild = x;
    }
    
    /**
    * 红黑树插入修正函数
    * @param T 红黑树的根
    * @param x 插入的结点
    * @description 用到变色和旋转
    */
    void RBTree_Insert_FixUp(RBTRoot* T, RBTree x) {
       // 当前结点的父结点为红色需调整 注:根节点 parent是指向nil
       // (1) 叔叔结点是红色: (1.1,1.2)左右分支,一样处理,变色即可
       // (2) 叔叔结点是黑色:(2.1,2.2)左分支下左右孩子 (2.3,2.4)右分支下左右孩子
    
       while (x->parent->color == RED) {
            // 首先父结点是祖父结点的左分支还是右分支
            if (x->parent == x->parent->parent->lchild) {
                // 判断叔叔结点颜色
                if (x->parent->parent->rchild->color == RED) {
                    // 将父结点和叔叔结点改为黑色,祖父结点改为红色
                    x->parent->color = BLACK;
                    x->parent->parent->rchild->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                } else {
                    // 叔叔结点的颜色为黑色:分父结点的(1)左孩子 (2)右孩子
                    // (1)父结点左孩子:父结点颜色变为BLACK,祖父节点变RED,右旋处理
                    if (x->parent->lchild == x) {
                        x->parent->color = BLACK;
                        x->parent->parent->color = RED;
                        // 注意这里是x->parent->parent 以祖父节点作为旋转的根节点
                        RBTree_R_Rotate(T, x->parent->parent);
                    } else {
                    // (2)右孩子,先左旋转,转为上面(1)父结点左孩子的情况
                    // 借助循环下次就会运行到(1)然后右旋
                        x = x->parent;
                        RBTree_L_Rotate(T, x);
                    }
                }
            } else {
                // 祖父结点的右分支
                if (x->parent->parent->lchild->color == RED) {
                    // 叔叔结点为红色,左右分支都一样处理
                    x->parent->color = BLACK;
                    x->parent->parent->lchild->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                } else {
                    // 叔叔为黑色
                    // 父结点的右分支
                    if (x->parent->rchild == x) {
                        x->parent->color = BLACK;
                        x->parent->parent->color = RED;
                        RBTree_L_Rotate(T, x->parent->parent);  // 左旋
                    } else {
                        // 父结点的左分支
                        x = x->parent;
                        RBTree_R_Rotate(T, x);  // 右旋
                    }
                }
            }
            // 每次循环结束需要将根节点涂黑,因为可能在某次变色时,根节点变为红色
            // 不可放在循环外部
            // T->root->color = BLACK;
       }
        T->root->color = BLACK;
    }
    
    /**
    * 插入结点
    * @param T 红黑树的头结点
    * @param key 插入结点值
    * @description 找到位置,初始化结点,插入结点,调整红黑树
    */
    void RBTree_Insert(RBTRoot** T, ElemType key) {
        RBTree pre; // pre保存了上一个x位置的指针(引用)
        RBTree x = (*T)->root;
        pre = x;
        while (x != (*T)->nil) {
            pre = x;
            if (x->key == key) {
                printf("\n%d已存在\n",key);
                return;
            } else if (key < x->key)
                x = x->lchild;
            else
                x = x->rchild;
        }
    
        // 初始化插入结点,将结点设为红色
        x = (RBTree) malloc(sizeof(RBNode));
        x->key = key;
        x->lchild = x->rchild = (*T)->nil;
        x->color = RED;
        x->parent = pre;
    
        // 根节点引用没有发生变化,
        // 插入根节点,直接插入,否则,向保存x父结点的pre左孩子或者右孩子插入x
        if ((*T)->root == (*T)->nil)
            (*T)->root = x;
        else if (key < pre->key)
            pre->lchild = x;
        else
            pre->rchild = x;
        // 插入之后,进行修正处理
        RBTree_Insert_FixUp(*T, x);
    }
    
    /**
    * 红黑树删除修正函数
    * @param T 头结点
    * @param p 删除结点的父结点
    * @param n 删除结点
    * @description 找到结点元素等于key的结点,删除结点,调整红黑树
    */
    void RBTree_Delete_FixUp(RBTRoot* T, RBTree n) {
        RBTree s;
        // 单支黑红结点不会进入while,因为替代结点n为红色,n结点变色即可
        // 进入循环体的一定 叶子结点 为黑色的这种情况
        while (n != T->root && n->color == BLACK) {
    
            // 兄在右子树
            if (n == n->parent->lchild) {
                s = n->parent->rchild;  // 找到其兄弟结点,其子必为双黑
                // 第一种情况:兄红
                if (s->color == RED) {
                    s->color = BLACK;
                    n->parent->color = RED;
                    RBTree_L_Rotate(T, n->parent);
                    // 此时,兄弟结点必为黑色,转为情况2,3,4处理
                    s = n->parent->rchild;
                }
                // 第二种情况:兄黑,子全黑
                // 处理方式,兄涂红色,n指向父结点,下次while循环,如果父为红色,结束循环,
                // 循环跳出后会设置父结点为黑,也就是笔记提到的2.1.1情况。如果父为黑色,此时就需要
                // 递归向上处理,以parent为n,再找其兄弟结点,通过局部平衡达到全局平衡。
                // s->color == BLACK判断并没有多大意义,
                // 第一种情况被处理后兄结点为黑,其他情况兄结点一定为黑,所以说判断可加可不加
    
                if (s->color == BLACK &&
                    s->lchild->color == BLACK &&
                    s->rchild->color == BLACK) {
                    s->color = RED;
                    n = n->parent;
                }
    
                // 3,4两种情况包括了红红,红黑,黑红,但是必须有一个if存在限制,
                // 防止左右双红都会进入if处理
                // 第三种情况:兄黑,兄在右子树,左孩子红色
                if (s->rchild->color == BLACK &&
                    s->lchild->color == RED ) {
                    s->color = RED;
                    s->lchild->color = BLACK;
                    RBTree_R_Rotate(T, s);
                    s = n->parent->rchild;
                    // 一环接一环,处理后s变为情况4
                    // 转为情况4处理
                }
                // 第四种情况:兄黑,兄在右子树,右孩子红色
                if (s->rchild->color == RED) {
                    // 左红右红或者右红左黑都进入该条件处理
                    // 使用父结点的颜色,目的是旋转S结点(新的父结点)不会和GP冲突
                    s->color = n->parent->color;
                    n->parent->color = BLACK;
                    s->rchild->color = BLACK;
                    RBTree_L_Rotate(T, n->parent);
                    s = T->root;
                }
            } else {
            // 兄在左子树
                s = n->parent->lchild;
                if (s->color == RED) {
                    s->color = BLACK;
                    n->parent->color = RED;
                    RBTree_R_Rotate(T, n->parent);
                    s = n->parent->lchild;
                }
                if (s->lchild->color == BLACK && s->rchild->color == BLACK) {
                    s->color = RED;
                    n = n->parent;
                }
                if (s->lchild->color == BLACK && s->rchild->color == RED) {
                    s->color = RED;
                    s->rchild->color = BLACK;
                    RBTree_L_Rotate(T, s);
                    s = n->parent->lchild;
                }
                if (s->lchild->color == RED) {
                    s->color = n->parent->color;
                    n->parent->color = BLACK;
                    s->lchild->color = BLACK;
                    RBTree_R_Rotate(T, n->parent);
                    n = T->root;
                }
            }
        }
    
        n->color = BLACK;
    }
    
    /**
    * 删除指定元素的结点
    * @param T 红黑树的头结点
    * @param key 删除的元素值
    * @description 找到结点元素等于key的结点,删除结点,调整红黑树
    */
    void RBTree_Delete(RBTRoot** T, ElemType key) {
        RBTree target, realDel, child;
        // 1.在红黑树中查找指定元素等于key的结点,可以以下逻辑封装到方法里面
        // target = RBTreeSearch(root, key);
        target = (*T)->root;
        while (key != target->key && target != (*T)->nil) {
            if (key < target->key)
                target = target->lchild;
            else if (key > target->key)
                target = target->rchild;
        }
        if (target == (*T)->nil)
            return; //树中没有key结点
    
        // 2. 判断删除结点是叶子、单支、双支,找到删除结点的真正位置
        // 2.1 如果为叶子结点或者单支结点,删除结点的真正位置就是其本身
        // 2.2 如果为双支结点,删除结点的真正位置为后继结点(Successor)右孩子左子树最左边的结点
        if (target->lchild == (*T)->nil || target->rchild == (*T)->nil)
            realDel = target;
        else {
            realDel = target->rchild;
            while (realDel->lchild != (*T)->nil) {
                realDel = realDel->lchild;
            }
            // 处理完毕之后,readDel不会存在左分支
        }
    
        // 处理完毕之后,readDel最多有一个孩子
        //找到删除结点的孩子结点,之后移植结点需要用到child
        if (realDel->lchild != (*T)->nil)
            child = realDel->lchild;    // 只有左单支走这一步
        else
            child = realDel->rchild;    // 叶子结点或者右单支走这一步
    
        // 3. 移植结点:结点变化父结点,左右子树
    
        // 建立结点关联
    
        // 如果是nil结点,则将空的叶子结点推到删除空缺的位置,
        // 这一步其实就是让nil结点代替删除的结点,虚设黑结点
        // 否则将子结点推到父结点
        child->parent = realDel->parent;
    
    
        if (realDel->parent == (*T)->nil)
            (*T)->root = child;
        else if (realDel->parent->lchild == realDel)
            realDel->parent->lchild = child;
        else if (realDel->parent->rchild == realDel)
            realDel->parent->rchild = child;
    
        // 4. 如果删除结点发生了转化,比如删除结点为双支结点,那么就转化为后继结点被删
        // 而为了不移动大量指针,这里只是将值复制到删除结点,然后在删除后继结点
        if (target != realDel)
            target->key = realDel->key;
    
        // 5.删除结点是黑色的需要调整,调整的是已经移植的树,传递child,而非realDel
        if (realDel->color == BLACK)
            RBTree_Delete_FixUp(*T, child);
    
        // 6. 释放结点
        free(realDel);
    }
    
    /**
    * 中序遍历二叉排序树
    */
    void InOrderTraverse(RBTRoot* T, RBTree t) {
        if(T->nil == t){
            return ;
        }
        InOrderTraverse(T,t->lchild);
        if(t->color == RED){
            printf("%dR ",t->key);
        }else{
            printf("%dB ",t->key);
        }
        InOrderTraverse(T,t->rchild);
    }
    
    int main()
    {
        int a[] = {10,9,8,7,6,5,4,3,2,1};
        //int a[] = {1,3,2};
        RBTRoot* head = RBTree_Init();
        for (int i = 0; i < 10; i++) {
            RBTree_Insert(&head, a[i]);
        }
        InOrderTraverse(head, head->root);
        for (int i = 0; i < 9; i++) {
            RBTree_Delete(&head, a[i]);
        }
        //RBTree_Delete(&head, a[6]);
        printf("\n");
        InOrderTraverse(head, head->root);
        return 0;
    }
    
    

    参考

    展开全文
  • 红黑树是平衡二叉查找树中的一种,最突出的特点是效率高。时间复杂度:O(log(n))...那么,什么红黑树的效率高呢? 根据性质3,先把红色结点跟父亲结点整合在一块,新整合出来的树称为“2-3-4 树”,它的高度原先

    红黑树是平衡二叉查找树中的一种,最突出的特点是效率高。时间复杂度:O(log(n))

    红黑树有如下4个性质:
    1).没个结点不是红色就是黑色;
    2).根结点是黑色的;
    3).每个红色结点的父亲是黑色的;
    4).根结点到达每个叶子结点的路径中黑色结点的个数是一样的;

    那么,为什么红黑树的效率高呢?
    根据性质3,先把红色结点跟父亲结点整合在一块,新整合出来的树称为“2-3-4 树”,它的高度为原先红黑树高度的1/2,如下图:

    这里写图片描述

    因为: 红黑树中,键是8个,叶子结点是9个
    所以:用归纳法可以得到叶子结点 = 键+1
    因为:在2-3-4树中,叶子结点的数量在 2^h <= 叶子结点 <= 2^h
    所以:高度 h 与键(n)的关系是:2^h <= n+1 取对数得:h <= log(n+1)
    又因为:红黑树的高度与2-3-4树的高度关系是:h = H/2
    所以:红黑树的高度与键的关系是: H <= 2log(n+1)
    高度与叶子是对数关系,而且高度一致,所以红黑树的平衡性很好,查找效率非常高。

    但是!更新操作容易对红黑树造成破坏,失去平衡性。所以,在插入/删除红黑树的结点时,要保证红黑树的`性质还在。对于这种恢复红黑树的操作,最典型的就是旋转,就是把某个结点往左/右旋转90度,如下图:

    这里写图片描述

    现在执行插入一个结点操作:

    1).插入一个15结点,根据15数值的大小,确定15放在红黑树中的位置(叶子结点就不画了,小黑圈那些)

    这里写图片描述

    2).虽然15结点插入到红黑树中,但是破坏了红黑树的性质,采取旋转或颜色转换恢复红黑树的性质

    这里写图片描述

    根据上面的例子,对于插入结点后的红黑树而言,这里有个通用的算法:

    case1:如果左右结点均为红色,进行颜色转换

    case2:如果右子结点是红色的而左子结点是黑色的,进行左旋转

    case3:如果左子结点是红色的且它的的左子结点是红色的,进行右旋转

    如下图所示:

    这里写图片描述

    在Java中,集合类TreeMap就是基于红黑树实现的

    下面看看Java实现插入结点的代码:

    package RBT;
    
    public class RedBlackBST {
    
        //根结点
        private Node root;
    
        //红黑
        private static final boolean RED = true;
        private static final boolean BLACK = false;
    
        //键
        private class Key {
            private String key;
            Key(String key) {
                this.key = key;
            }
            public int compareTo(Key key2) {
                return key.compareTo(key2.key);
            }
        }
    
        //键值
        private class Value {
            private int val;
            Value(int val) {
                this.val = val;
            }
        }
    
        //结点
        private class Node {
            //键和键值
            Key key;
            Value val;
            //左右结点
            Node left, right;
            //包含几个子结点
            int N;
            //颜色
            boolean color;
    
            Node(Key key, Value val, int N, boolean color) {
                this.key = key;
                this.val = val;
                this.N = N;
                this.color = color;
            }
        }
    
        private boolean isRed(Node h) {
            if(h == null) return false;
            return h.color = RED;
        }
    
        private int size() {
            return size(root);
        }
    
        private int size(Node h) {
            if(h == null) {
                return 0;
            }
            return h.N;
        }   
    
        //左旋
        private Node rotateLeft(Node h) {
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
    
        //右旋
        private Node rotateRight(Node h) {
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = h.color;
            h.color = RED;
            x.N = h.N;
            h.N = 1 + size(h.left) + size(h.right);
            return x;
        }
    
        //颜色转换
        private void flipColors(Node h) {
            h.color = RED;
            h.left.color = BLACK;
            h.right.color = BLACK;
        }
    
        public void put(Key key, Value val) {
            root = put(root, key, val);
            root.color = BLACK;
        }
    
        //插入结点
        public Node put(Node h, Key key, Value val) {
            if(h == null) 
                return new Node(key, val, 1, RED);
            //以下4个语句是将h根据键值大小放进红黑树中的位置
            int cmp = key.compareTo(h.key);
            if(cmp < 0) h.left = put(h.left, key, val);
            else if(cmp > 0) h.right = put(h.right, key, val);
            else h.val = val;
            //如果右子结点是红色的而左子结点是黑色的,进行左旋转
            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;
            return h;
        }
    
    }

    以上是红黑树的插入操作,至于删除操作,看了一下午,还是有点蒙,若有一天我理解了,一定分享出来!

    展开全文
  • 红黑树插入结点方法balanceInsertion的源码分析 红黑树的定义: 性质1. 节点是红色或黑色。 性质2. 根节点是黑色。 性质3.所有叶子都是黑色。(叶子是NUIL节点) 性质4. 每个红色节点的两个子节点都是黑色。(从每个...

    红黑树插入结点方法balanceInsertion的源码分析

    红黑树的定义:

    性质1. 节点是红色或黑色。

    性质2. 根节点是黑色。

    性质3.所有叶子都是黑色。(叶子是NUIL节点)

    性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

    性质5… 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    在这里插入图片描述

    这个图里面没有画出叶结点(空结点),叶结点就是结点如果没有左右结点指向,就会指向叶结点

    红黑树平衡:每一个结点到其各个子孙结点的叶结点的路径,经历的黑色结点的个数是一样的。比如,图中27到其两个叶结点经历的黑色结点个数是两个,其中包括自己和叶结点。而根结点50,到其所有的子孙结点的叶结点所经历的黑色结点个数都是三个。而红色的结点则是为了平衡黑色结点

    插入的所有情况:

    插入的时候如果父结点是黑色的,则不会对红黑树所有的性质产生影响,不要操作,而当父结点是红色的时候,则会对红黑树的性质有影响,则需要进行许多操作。插入操作是三个一组,当前结点,父结点和祖父结点。完成一组操作后还要向上检查是否满足红黑树性质。

    父结点是红色:

    情况一到三都是父结点在祖父结点的左结点

    情况一:叔结点,就是父结点的同一级不为空并且是红色。

    将叔结点和父结点都转换为黑色就可以满足红黑树

    情况二:叔结点为空,父结点是祖父结点的左结点,结点是父结点的右结点

    需要将父结点左旋,然后进入下一次循环的情况三

    情况三:叔结点为空,结点在父结点的左边,父结点在祖父结点的左边

    父结点变成黑色,祖父结点变成红色然后将祖父结点右旋

    情况四到六都是父结点在祖父结点的右结点

    情况四:叔结点不为空并且是红色

    将叔结点和父结点都转换为黑色就可以满足红黑树

    情况五:叔结点为空,如果结点是父结点的左结点(父结点是祖父结点的右结点)

    把父结点右旋,再重新进入循环进入情况六

    情况六:叔结点为空,父结点是祖父节点的右节点,当前节点也是父节点的右节点

    将父结点变成黑色,把祖父结点左旋

    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                TreeNode<K,V> x) {
        //结点的颜色默认是红色的
        x.red = true;
        //xp父结点 xpp祖父结点  xppl祖父结点的左结点 xppr祖父结点的右结点
        //循环是因为要循环判断在旋转或者变色之后的结构还是否满足红黑树规则,一直到根结点
        for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
            //如果这里是根节点,则让根结点变成黑色,返回红黑树
            if ((xp = x.parent) == null) {
                x.red = false;
                return x;
            }
            //如果当前结点的上一个结点是黑色的,就停止循环
            //因为如果父结点是黑色的,则插入红色结点不会对黑节点的平衡产生影响
            else if (!xp.red || (xpp = xp.parent) == null)
                return root;
            //判断父结点是不是祖父结点的左结点
            if (xp == (xppl = xpp.left)) {
                //情况一:判断叔结点,就是父结点的同一级不为空并且是红色的
                /*
                执行,叔结点和父结点换成黑色,祖父结点换成红色
                */
                if ((xppr = xpp.right) != null && xppr.red) {
                    xppr.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;//将当前结点换为祖父结点继续判断是不是符合红黑树规则
                }
                else {
                    //情况二:父结点是祖父结点的左结点,结点是父结点的右结点
                    /*
                    执行,将父结点和root左旋,然后重新执行循环
                    */
                    if (x == xp.right) {
                        root = rotateLeft(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    //情况三:经过情况二,结点在父结点的左边,父结点在祖父结点的左边
                    //如果当前的父结点不为空,让其变为黑色
                    if (xp != null) {
                        xp.red = false;
                        //如果祖父结点不为空,让其变为红色,再对祖父结点右旋
                        /*
                        右旋之后的情况:祖父结点 -->祖父结点的右结点
                                     当前结点 -->祖父结点的左结点
                                     父结点   -->祖父结点
                        右旋之后,还需要继续循环判断是否对上面的结点造成影响
                        */
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            }
            //此时父结点是祖父结点的右结点
            else {
                //情况四:叔结点不为空并且是红色
                /*
                将叔结点和父结点变成黑色,祖父结点变成红色,继续循环判断
                */
                if (xppl != null && xppl.red) {
                    xppl.red = false;
                    xp.red = false;
                    xpp.red = true;
                    x = xpp;
                }
                //此时叔结点为空
                //或者 叔结点是黑色的,这种情况是下面的结点调整之后,祖父结点变成红色,会造成这种情况
                      一般是循环判断的时候出现
                else {
                    //情况五:如果结点是父结点的左结点(父结点是祖父结点的右结点),右旋,
                    //再重新进入循环进入情况六
                    /*
                    右旋:主要是为了转换为这样的情况:父结点是右结点,当前节点也是右节点
                         当前节点-->父结点(祖父节点的右节点)
                         父结点-->父结点的右节点
                         祖父节点-->不变
                    */
                    if (x == xp.left) {
                        root = rotateRight(root, x = xp);
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    //情况六:父结点是祖父节点的右节点,当前节点也是父节点的右节点
                    //将父结点变成黑色,把祖父结点左旋
                    if (xp != null) {
                        xp.red = false;
                        if (xpp != null) {
                            xpp.red = true;
                            root = rotateLeft(root, xpp);
                        }
                    }
                }
            }
        }
    }
    
    展开全文
  • 提到红黑树,你是不是头皮发麻,难搞哦????,别害怕,我来教你分分钟学会他 我们先来看一下红黑树的定义: ...(因为所有叶子节点都会回到 nil 哨兵结点,故本文忽略哨兵结点) 根据上述定义,我们可以设置红黑树...
  • 目录 一、红黑树的规则 二、红黑树节点删除整体分析 三、红黑树节点删除具体情形分析 ...综合各博客大神对该问题的分析,以TreeMap中红黑树节点删除相关代码例,记录下自己对该问题的分析和理解,欢迎指正。 ...
  • 红黑树

    2020-04-20 20:32:49
    所有叶子节点都是黑色(叶子是NULL节点) 每个红色节点的两个子节点都是黑色 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 红黑树插入情景(插入节点红色) 红黑树为空树 插入节点已存在 ...
  • 教你初步了解红黑树

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

    千次阅读 多人点赞 2019-10-11 11:38:24
    红黑树常用的操作是插入、删除和查找,并且它对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保,对于红黑树的概念、性质、插入、查找和旋转等这里不再多讲,不了解的请点击wikipedia rb-tree,这里重点...
  • 红黑树基础

    2018-08-07 20:26:09
    什么是红黑树 红黑树是一种自平衡的二叉查找树。红黑树是一种很重要的数据结构,Java中TreeMap,TreeSet和...3. 叶子节点为null并且黑色 4. 红色节点的子节点都是黑色 5. 从任意一个节点到其每个叶子节点经过的...
  •  第一,特性(3)中的叶子节点,是只空(NIL或null)的节点。  第二,特性(5)确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。 二、红黑树的搜索   由于每一棵红黑树
  • 本篇主要谈谈对红黑树的理解,大家都晓得JDK8中的hashmap底层是数组+链表+红黑树实现的,当面试官问你:啥要加上红黑树实现呢?? 那我们首先从概念来了解一下: 一、什么是红黑树红黑树是一个接近平衡的二叉...
  • 1.红黑树的概念:红黑树是一棵二叉搜索树,它在每个节点上增加一个存储位来表示节点的颜色,可以是red或black,通过对任何一条从根节点到叶子节点上的间单路径来约束,红黑树保证最长路径不超过最短路径的两倍,因而...
  • 红黑树原理

    2021-09-04 15:48:35
    特征 红黑树是 “平衡” &...③“叶子结点”一定是黑色的(红黑树叶子为null) ④红黑树中,任意路径(根到节点)中,红色和红色不能相邻 ⑤红黑树中,任意路径(根到节点)中,黑色节点的数量...
  • 3、 每个叶子节点都是(NIL)都是黑色的(都是null,虚拟出来的); 4、 每个红色节点的两个子节点一定是黑色的; 5、任意一节点到每个叶子节点的路径都包含数量相同的黑节点(黑色完美平衡)。 红黑树的添加: 1、 ...
  • 红黑树之插入节点 红黑树的性质 红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何...为了和以前的叶子节点做区分,原来的叶子节点还叫叶子节点,这个节点...
  • 红黑树之删除节点

    2017-08-12 21:35:00
    红黑树之删除节点 上一篇文章中讲了如何向红黑树中添加节点,也顺便创建了一棵红黑树。今天写写怎样从红黑树中删除节点。 相比于添加节点,删除节点要复杂的多。不过我们慢慢梳理,还是能够弄明白的。 回顾一下...
  • 红黑树系列2——红黑树的删除(码字中,待发表) 红黑树系列3——红黑树的应用(码字中,待发表) 红黑树系列4——红黑树的代码实现(码代码中,待发表) 红黑树动态建立,删除网站(强强强强烈推荐,根据网页上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,141
精华内容 5,656
关键字:

红黑树的叶子节点为null