红黑树-插入删除

操作

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂，但操作时间仍可以保持为 O(log n) 次。

插入

我们首先以二叉查找树的方法增加节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换（color flips）和树旋转来调整。） 下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样，我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意:

  • 性质1[1]和性质3[2]总是保持着。
  • 性质4[3]只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁。
  • 性质5[4]只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁。

在下面的示意图中，将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。在图中展示的任何颜色要么是由它所处情形所作的假定，要么是这些假定所暗含 (imply) 的。

对于每一种情况，我们将使用 C 示例代码来展示。通过下列函数，可以找到一个节点的叔父和祖父节点:

 node grandparent(node n) {
     return n->parent->parent;
 }
 
 node uncle(node n) {
     if (n->parent == grandparent(n)->left)
         return grandparent(n)->right;
     else
         return grandparent(n)->left;
 }

情形1: 新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2[5]。因为它在每个路径上对黑节点数目增加一，性质5[4]符合。

 void insert_case1(node n) {
     if (n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2(n);
 }

情形2: 新节点的父节点P是黑色，所以性质4[3]没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质5[4]受到威胁，因为新节点N有两个黑色叶子儿子；但是由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以这个性质依然满足。

 void insert_case2(node n) {
     if (n->parent->color == BLACK)
         return; /* 树仍旧有效 */
     else
         insert_case3(n);
 }

注意: 在下列情形下我们假定新节点有祖父节点，因为父节点是红色；并且如果它是根，它就应当是黑色。所以新节点总有一个叔父节点，尽管在情形4和5下它可能是叶子。

 

 

情形3: 如果父节点P和叔父节点U二者都是红色，(此时新插入节点N做为P的左子节点或右子节点都属于情形3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质5[4])。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G的父节点也有可能是红色的，这就违反了性质4[3]。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程。（把G当成是新加入的节点进行各种情况的检查）

 
 void insert_case3(node n) {
     if (uncle(n) != NULL && uncle(n)->color == RED) {
         n->parent->color = BLACK;
         uncle(n)->color = BLACK;
         grandparent(n)->color = RED;
         insert_case1(grandparent(n));
     }
     else
         insert_case4(n);
 }

注意: 在余下的情形下，我们假定父节点P 是其父亲G 的左子节点。如果它是右子节点，情形4和情形5中的左和右应当对调。

 

 

情形4: 父节点P是红色而叔父节点U是黑色或缺少; 还有，新节点N是其父节点P的右子节点，而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色; 接着，我们按情形5处理以前的父节点P。这导致某些路径通过它们以前不通过的新节点N或父节点P中的一个，但是这两个节点都是红色的，所以性质5[4]没有失效。

 
 void insert_case4(node n) {
     if (n == n->parent->right && n->parent == grandparent(n)->left) {
         rotate_left(n->parent);
         n = n->left;
     } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
         rotate_right(n->parent);
         n = n->right;
     }
     insert_case5(n);
 }

情形5: 父节点P是红色而叔父节点U 是黑色或缺少，新节点N 是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G 的一次右旋转; 在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G 的父节点。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色 (如果 P 和 G 都是紅色就違反了性質4，所以 G 必須是黑色)。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4[3]。性质5[4]也仍然保持满足，因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G ，现在它们都通过以前的父节点P。在各自的情形下，这都是三个节点中唯一的黑色节点。

 
 void insert_case5(node n) {
     n->parent->color = BLACK;
     grandparent(n)->color = RED;
     if (n == n->parent->left && n->parent == grandparent(n)->left) {
         rotate_right(grandparent(n));
     } else {
         /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
         rotate_left(grandparent(n));
     }
 }

注意插入实际上是原地算法，因为上述所有调用都使用了尾部递归。

删除

如果需要删除的节点有两个儿子，那么问题可以被转化成删除另一个只有一个儿子的节点的问题（为了表述方便，这里所指的儿子，为非叶子节点的儿子）。对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中(如在这里所展示的那样)。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值而不违反任何属性，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。

在本文余下的部分中，我们只需要讨论删除只有一个儿子的节点(如果它两个儿子都为空，即均为叶子，我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点，它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏属性3和4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证属性5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏属性5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持属性5。

需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N，称呼它的兄弟(它父亲的另一个儿子)为S。在下面的示意图中，我们还是使用P称呼N的父亲，SL称呼S的左儿子，SR称呼S的右儿子。我们将使用下述函数找到兄弟节点:

struct node *
sibling(struct node *n)
{
        if (n == n->parent->left)
                return n->parent->right;
        else
                return n->parent->left;
}

我们可以使用下列代码进行上述的概要步骤，这里的函数 replace_node 替换 child 到 n 在树中的位置。出于方便，在本章节中的代码将假定空叶子被用不是 NULL 的实际节点对象来表示(在插入章节中的代码可以同任何一种表示一起工作)。

void
delete_one_child(struct node *n)
{
        /*
         * Precondition: n has at most one non-null child.
         */
        struct node *child = is_leaf(n->right) ? n->left : n->right;
 
        replace_node(n, child);
        if (n->color == BLACK) {
                if (child->color == RED)
                        child->color = BLACK;
                else
                        delete_case1(child);
        }
        free(n);
}

如果 N 和它初始的父亲是黑色，则删除它的父亲导致通过 N 的路径都比不通过它的路径少了一个黑色节点。因为这违反了属性 4，树需要被重新平衡。有几种情况需要考虑:

情况 1: N 是新的根。在这种情况下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以属性都保持着。

void
delete_case1(struct node *n)
{
        if (n->parent != NULL)
                delete_case2(n);
}

注意: 在情况2、5和6下，我们假定 N 是它父亲的左儿子。如果它是右儿子，则在这些情况下的左和右应当对调。

情况 2: S 是红色。在这种情况下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父。我们接着对调 N 的父亲和祖父的颜色。尽管所有的路径仍然有相同数目的黑色节点，现在 N 有了一个黑色的兄弟和一个红色的父亲，所以我们可以接下去按 4、5或6情况来处理。(它的新兄弟是黑色因为它是红色S的一个儿子。)

 
void
delete_case2(struct node *n)
{
        struct node *s = sibling(n);
 
        if (s->color == RED) {
                n->parent->color = RED;
                s->color = BLACK;
                if (n == n->parent->left)
                        rotate_left(n->parent);
                else
                        rotate_right(n->parent);
        } 
        delete_case3(n);
}

情况 3: N 的父亲、S 和 S 的儿子都是黑色的。在这种情况下，我们简单的重绘 S 为红色。结果是通过S的所有路径，它们就是以前不通过 N 的那些路径，都少了一个黑色节点。因为删除 N 的初始的父亲使通过 N 的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过 P 的所有路径现在比不通过 P 的路径少了一个黑色节点，所以仍然违反属性4。要修正这个问题，我们要从情况 1 开始，在 P 上做重新平衡处理。

 
void
delete_case3(struct node *n)
{
        struct node *s = sibling(n);
 
        if ((n->parent->color == BLACK) &&
            (s->color == BLACK) &&
            (s->left->color == BLACK) &&
            (s->right->color == BLACK)) {
                s->color = RED;
                delete_case1(n->parent);
        } else
                delete_case4(n);
}

情况 4: S 和 S 的儿子都是黑色，但是 N 的父亲是红色。在这种情况下，我们简单的交换 N 的兄弟和父亲的颜色。这不影响不通过N 的路径的黑色节点的数目，但是它在通过 N 的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。

 
void
delete_case4(struct node *n)
{
        struct node *s = sibling(n);
 
        if ((n->parent->color == RED) &&
            (s->color == BLACK) &&
            (s->left->color == BLACK) &&
            (s->right->color == BLACK)) {
                s->color = RED;
                n->parent->color = BLACK;
        } else
                delete_case5(n);
}

情况 5: S 是黑色，S 的左儿子是红色，S 的右儿子是黑色，而 N 是它父亲的左儿子。在这种情况下我们在 S 上做右旋转，这样 S的左儿子成为 S 的父亲和 N 的新兄弟。我们接着交换 S 和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在 N 有了一个右儿子是红色的黑色兄弟，所以我们进入了情况 6。N 和它的父亲都不受这个变换的影响。

 
void
delete_case5(struct node *n)
{
        struct node *s = sibling(n);
 
        if  (s->color == BLACK) /* this if statement is trivial, 
due to Case 2 (even though Case two changed the sibling to a sibling's child, 
the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent, 
// or right of the right, so case six will rotate correctly.
                if ((n == n->parent->left) &&
                    (s->right->color == BLACK) &&
                    (s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
                        s->color = RED;
                        s->left->color = BLACK;
                        rotate_right(s);
                } else if ((n == n->parent->right) &&
                           (s->left->color == BLACK) &&
                           (s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
                        s->color = RED;
                        s->right->color = BLACK;
                        rotate_left(s);
                }
        }
        delete_case6(n);
}

情况 6: S 是黑色，S 的右儿子是红色，而 N 是它父亲的左儿子。在这种情况下我们在 N 的父亲上做左旋转，这样 S 成为 N 的父亲和 S 的右儿子的父亲。我们接着交换 N 的父亲和 S 的颜色，并使 S 的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以属性 3 没有被违反。但是，N 现在增加了一个黑色祖先: 要么 N 的父亲变成黑色，要么它是黑色而 S 被增加为一个黑色祖父。所以，通过 N 的路径都增加了一个黑色节点。

此时，如果一个路径不通过 N，则有两种可能性:

  • 它通过 N 的新兄弟。那么它以前和现在都必定通过 S 和 N 的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
  • 它通过 N 的新叔父，S 的右儿子。那么它以前通过 S、S 的父亲和 S 的右儿子，但是现在只通过 S，它被假定为它以前的父亲的颜色，和 S 的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。

在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了属性 4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。

 
void
delete_case6(struct node *n)
{
        struct node *s = sibling(n);
 
        s->color = n->parent->color;
        n->parent->color = BLACK;
 
        if (n == n->parent->left) {
                s->right->color = BLACK;
                rotate_left(n->parent);
        } else {
                s->left->color = BLACK;
                rotate_right(n->parent);
        }
}

同样的，函数调用都使用了尾部递归，所以算法是就地的。此外，在旋转之后不再做递归调用，所以进行了恒定数目(最多 3 次)的旋转。

渐进边界的证明

包含n个内部节点的红黑树的高度是 O(log(n))。

定义:

  • h(v) = 以节点v为根的子树的高度。
  • bh(v) = 从v到子树中任何叶子的黑色节点的数目(如果v是黑色则不计数它)(也叫做黑色高度)。

引理: 以节点v为根的子树有至少2bh(v) − 1个内部节点。

引理的证明(通过归纳高度):

基础: h(v) = 0

如果v的高度是零则它必定是 nil，因此 bh(v) = 0。所以:

2bh(v) − 1 = 20 − 1 = 1 − 1 = 0

归纳假设: h(v) = k 的v有 2bh(v) − 1 − 1 个内部节点暗示了 h(v') = k+1 的 v'有2bh(v') − 1 个内部节点。

因为 v' 有 h(v') > 0 所以它是个内部节点。同样的它有黑色高度要么是 bh(v') 要么是 bh(v')-1 (依据v'是红色还是黑色)的两个儿子。通过归纳假设每个儿子都有至少 2bh(v') − 1 − 1 个内部接点，所以 v' 有:

2bh(v') − 1 − 1 + 2bh(v') − 1 − 1 + 1 = 2bh(v') − 1

个内部节点。

使用这个引理我们现在可以展示出树的高度是对数性的。因为在从根到叶子的任何路径上至少有一半的节点是黑色(根据红黑树属性4)，根的黑色高度至少是h(root)/2。通过引理我们得到:

 

因此根的高度是O(log(n))。

时间： 2024-10-21 22:46:58

红黑树-插入删除的相关文章

红黑树的插入

一.红黑树的介绍 先来看下算法导论对R-B Tree的介绍: 红黑树,一种二叉查找树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black. 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其 他路径长出俩倍,因而是接近平衡的. 前面说了,红黑树,是一种二叉查找树,既然是二叉查找树,那么它必满足二叉查找树的一般性质. 下面,在具体介绍红黑树之前,咱们先来了解下 二叉查找树的一般性质: 1.在一棵二叉查找树上,执行查找.插入.删除等操作,的时间复杂

数据结构和算法05 之红-黑树（看完包懂~）

(友情提示,红-黑树是基于二叉搜索树的,如果对二叉搜索树不了解,可以先看看:二叉搜索树 )                从第4节的分析中可以看出,二叉搜索树是个很好的数据结构,可以快速地找到一个给定关键字的数据项,并且可以快速地插入和删除数据项.但是二叉搜索树有个很麻烦的问题,如果树中插入的是随机数据,则执行效果很好,但如果插入的是有序或者逆序的数据,那么二叉搜索树的执行速度就变得很慢.因为当插入数值有序时,二叉树就是非平衡的了,排在一条线上,其实就变成了一个链表--它的快速查找.插入和删除指

java集合类TreeMap和TreeSet及红黑树

看这篇博客前,我觉得很有必要先看下我之前的几篇博客 Red-Black Trees(红黑树)                                         (TreeMap底层的实现就是用的红黑树数据结构) 探索equals()和hashCode()方法                                 (TreeMap/TreeSet实现使用到的核心方法) java中的HashTable,HashMap和HashSet      (同为java集合类,对比下他们

红黑树深入剖析及Java实现

红黑树是平衡二叉查找树的一种.为了深入理解红黑树,我们需要从二叉查找树开始讲起. BST 二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大.它的高度决定了它的查找效率. 在理想的情况下,二叉查找树增删查改的时间复杂度为O(logN)(其中N为节点数),最坏的情况下为O(N).当它的高度为logN+1时,我们就说二叉查找树是平衡的. BST的查找操作 T  key = a search key  Node ro

数据结构之红黑树

概述 红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组.它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees).红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能. 二叉查找树(BST) 二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右

【算法导论】红黑树

红黑树          在了解红黑树之前,我们必须先了解二叉搜索树(又称二叉排序树,我在上一篇文章中有介绍),因为红黑树是一种特殊的二叉排序树:在每个节点上增加一个存储位来表示节点的颜色,因此红黑树共有五个域:color,key,lchild,rchild,p.          红黑树的提出:一个高度为h的二叉排序树可以实现任何一种基本的动态集合操作:插入.删除.查找等操作,但是当树才高度比较高时,二叉树就会退化成链表.而红黑树能确保在最坏的情况下,基本的动态集合操作的时间为O(logn).

红黑树的使用详解_C 语言

(学习的参考资料主要是<算法导论>) 首先是红黑树的性质.一棵二叉查找树满足以下的红黑性质,则为一棵红黑树. 1)每个结点或是红的,或是黑的. 2)根结点是黑的. 3)每个叶结点(NIL)是黑的. 4)红结点的两个孩子都是黑的. 5)对任意结点,从它到其子孙结点所有路径上包含相同数目的黑结点. 初学时并不在意,但是仔细研究相关算法就会知道,算法都是围绕保持这些性质来进行的.性质5)保证了红黑树使用时的高效.定理证明了n个内结点的红黑树高度至多为2lg(n+1).   不同于一般二叉查找树,红黑

一步一图一代码，一定要让你真正彻底明白红黑树【转】

转自:http://blog.csdn.net/chenhuajie123/article/details/11951777 一步一图一代码,一定要让你真正彻底明白红黑树   作者:July   二零一一年一月九日 ----------------------------- 本文参考:I.  The Art of Computer Programming Volume III. Introduction to Algorithms, Second EditionIII.The Annotated

第十三章 红黑树

R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为"红黑树",它一种特殊的二叉查找树.红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black). 红黑树的特性:(1)每个节点或者是黑色,或者是红色.(2)根节点是黑色.(3)每个叶子节点(NIL)是黑色. [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!](4)如果一个节点是红色的,则它的子节点必须是黑色的.(5)从一个节点到该节点的子孙节点的所有路径上包含相