[树]红黑树

 

第12章介绍了一棵高度为h的二叉搜索树,它可以支持任何一种基本动态集合操作,如SEARCH、PREDECESSOR、SUCCESSOR、MINIMUM、MAXIMUM、INSERT和DELETE等,其时间复杂度均为O(h)。因此,如果搜索树的高度较低时,这些集合操作会执行得较快。然而,如果树的高度较高时,这些集合操作可能并不比在链表上执行得快。红黑树(red-black
tree)是许多“平衡”搜索树中的一种,可以保证在最坏情况下基本动态集合操作的时间复杂度为O(lgn)。
13.1 红黑树的性质
红黑树是一棵二叉搜索树,它在每个结点上增加了一个存储位来表示结点的颜色,可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出2倍,因而是近似于平衡的
树中每个结点包含5个属性:color、key、left、right和p。如果一个结点没有子结点或父结点,则该结点相应指针属性的值为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点(外部结点)的指针,而把带关键字的结点视为树的内部结点。
一棵红黑树是满足下面红黑性质的二叉搜索树:

很早以前写过一个c版本的红黑树,现在以c++重写之,并引入面向对象,有时间的话再实现线程安全版本.

红黑树系列

一、定义

红黑树(Red Black
Tree)是一种特殊的二叉查找树(有时也称为2-3-4树),相比二叉查找树,特点是完全平衡,满足以下条件:

  1. 红链接均为左链接
  2. 没有任何一个结点同时和两条红链接相连;
  3. 该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同

注:满足上述定义的红黑树也称 左倾红黑树

红黑树的数据结构定义:

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED   = true;
    private static final boolean BLACK = false;
    private Node root;     // root of the BST
    private class Node {
        private Key key;           // key
        private Value val;         // associated data
        private Node left, right;  // links to left and right subtrees
        private boolean color;     // 结点颜色,表示其父节点到该结点的链接颜色(根节点为黑色,空结点为黑色)
        private int size;          // subtree count

        public Node(Key key, Value val, boolean color, int size) {
            this.key = key;
            this.val = val;
            this.color = color;
            this.size = size;
        }
    }
    public RedBlackBST() {
    }
}

注意main函数中的数据顺序。

  1. 每个结点或是红色的,或是黑色的。
  2. 根结点是黑色的。
  3. 每个叶结点(NIL)是黑色的。
  4. 如果一个结点是红色的,则它的两个子结点都是黑色的。
  5. 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。

原理

  • rb-tree是自平衡搜索树,整个结构是位于内存中的,中心思想是每次插入或者删除key时,维护好下面的5条性质,其中令其保持平衡的是第5条性质.

  • 由于是二分搜索树,树的深度会较大.(相较于B-树、B+树)

  • 五条性质:

 1. root节点为黑色
 2. 每个节点为黑色或红色
 3. 叶子节点为黑色
 4. 红节点的2个儿子为黑色
 5. 任意一个节点到其所能到达的任意叶子节点的简单路径上的黑高度一致

注意啊,有人把空节点算为黑色节点,也有人直接忽略空节点.

主要是两个互逆的操作插入和删除.

  1. 插入

  1. 删除

二、红黑树与2-3-4树的关系

理解红黑树的关键不在红黑树本身,而在2-3-4树。红黑树的真正本质是要将2-3-4树“表达”成二叉搜索树。

那么什么是2-3-4树?

 

图13-1(a)显示了一个红黑树的例子。

2.1 2-3-4树的定义

2-3-4树的名字是根据子结点数目来确定的,它含有三类结点:2-node、3-node、4-node,其中4-node只会出现在最底层

图片 1

2-3-4树 示意图

 

图片 2

2.2 红黑树与2-3-4树的映射

2-3-4树有三类不同的结点,而二叉搜索树只有一类结点(2-node)。
因此主要的问题就是:如何把3-node和4-node“表达”成2-node,而“红边”的引入,使这个问题的解决成为可能。
事实上,在一棵红黑树中,结点是无所谓红色还是黑色的,被染色的不是结点,而是连接结点的边

由于在我们的定义中,红黑树的红色链接都是左链接,故映射如下:

图片 3

图片 4

图片 5

注意:上述4-结点出现了两条相连的红色链接,违反了左倾红黑树的定义,故需要进行旋转/调整。

 

图13-1
一棵红黑树,其中黑结点涂黑,红结点以浅阴影表示。在一棵红黑树内,每个结点或红或黑,红结点的两个子结点都是黑色,且从每个结点到其后代叶结点的每条简单路径上,都包含相同数目的黑结点。(a)每个标为NIL的叶结点都是黑的。每个非NIL结点都标上它的黑高;NIL的黑高为0。(b)同样的这棵红黑树,不是用一个个的NIL表示,而用一个总是黑色的哨兵T.nil来代替,它的黑高也被省略。根结点的父结点也是这个哨兵。(c)同样的这棵红黑树,其叶结点与根结点的父结点全部被省略。本章的其余部分也采用这种画图方式

三、红黑树的操作

#include  <stdio.h>

为了便于处理红黑树代码中的边界条件,使用一个哨兵来代表NIL(参见10.2节)。对于一棵红黑树T,哨兵T.nil是一个与树中普通结点有相同属性的对象。它的color属性为BLACK,而其他属性p、left、right和key可以设为任意值。如图13-1(b)所示,所有指向NIL的指针都用指向哨兵T.nil的指针替换。
使用哨兵后,就可以将结点x的NIL孩子视为一个普通结点,其父结点为x。尽管可以为树内的每一个NIL新增一个不同的哨兵结点,使得每个NIL的父结点都有这样的良定义,但这种做法会浪费空间。取而代之的是,使用一个哨兵T.nil来代表所有的NIL:所有的叶结点和根结点的父结点。哨兵的属性p、left、right和key的取值并不重要,尽管为了方便起见可以在程序中设定它们。
我们通常将注意力放在红黑树的内部结点上,因为它们存储了关键字的值。在本章的后面部分,所画的红黑树都忽略了叶结点,如图13-1(c)所示。
从某个结点x出发(不含该结点)到达一个叶结点的任意一条简单路径上的黑色结点个数成为该结点的黑高(black-height),记为bh(x)。根据性质5,黑高的概念是明确定义的,因为从该结点出发的所有下降到其叶结点的简单路径的黑结点个数都相同。于是定义红黑树的黑高为其根结点的黑高。
下面的引理说明了为什么红黑树是一种好的搜索树。
引理 13.1 一棵有n个内部结点的红黑树的高度至多为2lg(n+1)。
证明

3.1 旋转

在红黑树的某些操作过程中,可能会出现红色右链接或者两条连续的红链接的情况,但在操作最终完成前,这些情况都会通过旋转来修复。旋转操作会改变红链接的指向。
旋转操作有以下几种类型(注意所谓左右旋转是针对红色链接来说的):

#include  <stdlib.h>

先证明以任一结点x为根的子树中至少包含2bh(x)-1个内部结点。要证明这点,对x的高度进行归纳。如果x的高度为0,则x必为叶结点(T.nil),且以x为根结点的子树至少包含2bh(x)-1

20-1个内部结点。对于归纳步骤,考虑一个高度为正值且有两个子结点的内部结点x。每个子结点有黑高bh(x)或bh(x)-1,其分别取决于自身的颜色是红还是黑。由于x子结点的高度比x本身的高度要低,可以利用归纳假设得出每个子结点至少有2bh(x)-1-1个内部结点的结论。于是,以x为根的子树至少包含(2bh(x)-1-1)+(2bh(x)-1-1)+1=2bh(x)-1个内部结点,因此得证。
为完成引理的证明,设h为树的高度。根据性质4,从根到叶结点(不包括根结点)的任何一条简单路径上都至少有一半的结点为黑色。因此,根的黑高至少为h/2;于是有

图片 6

把1移到不等式的左边,再对两边取对数,得到lg(n+1)>=h/2,或者h<=2lg(n+1)。

由该引理知,动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR可在红黑树上在O(lgn)时间内执行,因为这些操作在一棵高度为h的二叉搜索树上的运行时间为O(h)(参见第12章),而任何包含n个结点的红黑树又都是高度为O(lgn)的二叉搜索树。(当然,在第12章的算法中,NIL的引用必须用T.nil来代替。)虽然当给定一棵红黑树作为输入时,第12章的算法TREE-INSERT和TREE-DELETE的运行时间为O(lgn),但是这两个算法并不直接支持动态集合操作INSERT和DELETE,因为它们并不能保证被这些操作修改过的二叉搜索树仍是红黑树。那么如何在时间O(lgn)内支持这两个操作呢,我们将在13.3节和13.4节中介绍。
练习
13.1-1 按照图13-1(a)的方式,画出在关键字集合{1, 2, …,
15}上高度为3的完全二叉搜索树。以三种不同方式向图中加入NIL叶结点并对各结点着色,使所得的红黑树的黑高分别为2、3和4。
13.1-2
对图13-1中的红黑树,画出对其调用TREE-INSERT操作插入关键字36后的结果。如果插入的结点被标为红色,所得的树是否还是一棵红黑树?如果该结点被标为黑色呢?
13.1-3 定义一棵松弛红黑树(relaxed red-black
tree)为满足红黑性质1、3、4和5的二叉搜索树。换句话说,根结点可以是红色或是黑色。考虑一棵根结点为红色的松弛红黑树T。如果将T的根结点标为黑色而其他都不变,那么所得到的是否还是一棵红黑树?
是。
13.1-4
假设将一棵红黑树的每一个红结点“吸收”到它的黑色父结点中,使得红结点的子结点变成黑色父结点的子结点(忽略关键字的变化)。当一个黑结点的所有红色子结点都被吸收后,它可能的度为多少?所得的树的叶结点深度如何?
2、3、4。
13.1-5
证明:在一棵红黑树中,从某结点x到其后代叶结点的所有简单路径中,最长的一条至多是最短一条的2倍。
13.1-6
在一棵黑高为k的红黑树中,内部结点最多可能有多少个?最少可能有多少个?
22k-1, 2k-1
13.1-7
试描述一棵含有n个关键字的红黑树,使其红色内部结点个数与黑色内部结点个数的比值最大。这个比值是多少?该比值最小的树又是怎样呢?比值是多少?
每个黑色结点的子结点都是红色结点,每个叶结点的父结点都是红色结点,2:1。
没有红色结点,0。

3.1.1 左旋转

左旋转是指将一条红色右链接转换成红色左链接,如下图:

图片 7

3-1-1 左旋

代码实现:

/**
 * 将树h进行左旋转(假设h的右链接为红色)
 * 
 * @return 返回旋转后新树的根结点,该树根结点的左链接为红色
 */
private Node rotateLeft(Node h) {
    // assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;

    x.color = x.left.color;
    x.left.color = RED;

    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
}

 

3.1.2 右旋转

右旋转是指将一条红色左链接转换成红色右链接,如下图:

图片 8

3-1-2 右旋

代码实现:

/**
 * 将树h进行右旋转(假设h的左链接为红色)
 * 
 * @return 返回旋转后新树的根结点,该树根结点的右链接为红色
 */
private Node rotateRight(Node h) {
    // assert (h != null) && isRed(h.left);
    Node x = h.left;
    h.left = x.right;
    x.right = h;

    x.color = x.right.color;
    x.right.color = RED;

    x.size = h.size;
    h.size = size(h.left) + size(h.right) + 1;
    return x;
}

typedef   enum  _color

3.2 颜色翻转

当一个结点的左右链接都是红色时,需要将其转换为黑色:

图片 9

3-2 颜色翻转

代码实现:

/**
 * 将以h为根的树的左右链接反转
 * 基于以下假设:
 * ①h结点的左右结点均存在
 * ②当h为黑色时,其左右结点必须都是红色;当h是红色时,其左右结点必须是黑色
 */
private void flipColors(Node h) {
    // h must have opposite color of its two children
    // assert (h != null) && (h.left != null) && (h.right != null);
    // assert (!isRed(h) && isRed(h.left) && isRed(h.right))
    // || (isRed(h) && !isRed(h.left) && !isRed(h.right));
    h.color = !h.color;
    h.left.color = !h.left.color;
    h.right.color = !h.right.color;
}

  {

3.3 插入

红黑树的插入位置肯定在最底层(null位置),根据之前2-3-4树的定义,最底层可能是2-结点、3-结点、4-结点。
由于2-3-4树映射成红黑树后,4-结点需要处理掉,故我们只需要考虑在2-结点和3-结点插入的情况。另外,为保证树的平衡性,我们假设新插入的结点颜色初始时始终为红色

    RED,

3.3.1 向2-结点中插入新键

如果我们向2-结点插入的话,有两种情况:

  1. 插入左孩子,那么直接插入就可以;
  2. 插入右孩子,为了保持左倾,插入之后,我们需要进行一个左旋操作;

图片 10

3-3-1 插入示意图(最终得到一个3-结点)

    BLACK

3.3.2 向3-结点中插入新键

如果我们向3-结点插入的话,有三种情况:

  1. 新键大于3-结点中的两个键(右)

图片 11

  1. 新键小于3-结点中的两个键(左)

图片 12

  1. 新键在3-结点中的两个键之间(中)

图片 13

上述所有情况归结起来,具体步骤如下:

  1. 找到待插入的位置(肯定是个NULL)
  2. 沿着插入点到根结点的路径向上移动,途径的每个结点(不含当前插入的结点)顺序完成以下操作:
    ①如果右子结点是红色,左子结点是黑色,则对该结点进行左旋转;
    ②如果左子结点是红色,且左子结点的左子结点也是红色,则对该结点进行右旋转;
    ③如果左右子结点都是红色的,则对该结点进行颜色转换;

图片 14

3-3-2 插入示意图(最终得到一个4-结点,需要通过颜色转换处理掉)

代码实现:

public void put(Key key, Value val) {
    if (key == null)
        throw new IllegalArgumentException("first argument to put() is null");
    root = put(root, key, val);
    //根节点的颜色始终置为黑色
    root.color = BLACK;     
}
/**
 * 在以h为根的树中插入新结点,并进行红黑链接调整
 * @return 返回调整后的新树的根节点
 */
private Node put(Node h, Key key, Value val) {
    //h==null说明当前指向插入位置
    if (h == null)
        return new Node(key, val, RED, 1);

    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结点即查找到的键的位置,仅更新
        h.val = val;

    // 针对h结点进行链接调整(可抽象成通过的调整方法):
    if (isRed(h.right) && !isRed(h.left))       //1.如果右子结点是红色,左子结点是黑色,则对该结点进行左旋转;
        h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left))    //2.如果左子结点是红色,且左子结点的左子结点也是红色,则对该结点进行右旋转;
        h = rotateRight(h);
    if (isRed(h.left) && isRed(h.right))        //3.如果左右子结点都是红色的,则对该结点进行颜色转换;
        flipColors(h);
    h.size = size(h.left) + size(h.right) + 1;  
    return h;
}

图片 15

3-3-3 红黑树的完整插入示例

  }color;

3.4 删除

删除的基本原则:

  1. 删除路径上,当前结点不能是2-结点;
  2. 必要情况下,允许各层出现4-结点;
  3. 待删除的结点,经调整后总处于最底层;
  4. 删除结点后,向上修正(fixUp)以消除之前产生的4-结点和红色右链接;

fixUp源码如下:

/**
 * 对以h为根的树进行调整,使其重新满足左倾红黑树的特点
 * @return 返回新树的根结点
 */
private Node fixUp(Node h) {
    if (isRed(h.right))     //左旋
        h = rotateLeft(h);      

    if (isRed(h.left) && isRed(h.left.left))    //右旋
        h = rotateRight(h);

    if (isRed(h.left) && isRed(h.right))        //颜色转换
        colorFlip(h);
    return h;
}

 

3.4.1 删除最大结点

显然,最大结点一定在最右边。
而最右边的结点可能有3种情况:2-结点、3-结点、4-结点。分别进行分析:

3-结点、4-结点:
直接删除即可。

图片 16

2-结点:
如果直接删除2-结点会破坏红黑树的平衡,所以在沿搜索路径向下遇到2-结点时需要进行变换,变成3-结点或者4-结点。
变换方式就从兄弟结点借一个或者两个结点过来,根据兄弟结点的类型,分为两大类:
1、兄弟结点为2-结点
这种情况,要从父结点拿一个结点,然后与兄弟结点合并(2-结点变成4-结点):

图片 17

3-4-1 兄弟结点为2-结点的两种情况

注意:由于我们沿着删除路径向右下搜索的时候会对2-结点进行变换,所以当前指向的2-结点的父结点只可能是3-结点或4-结点

2、兄弟结点非2-结点
这种情况直接从兄弟结点借取一个结点:

图片 18

3-4-2 兄弟结点为非2-结点的四种情况


那么问题来了,上面的两类删除情况是针对2-3-4树的,如何转换成红黑树的相应操作呢?

做法如下:
当我们在沿右子树不断递归向下的过程中:
①遇到左倾红边,就把它右旋;
②遇到右子结点是2-结点时,就按照上面所说的合并/借取策略将2-结点转化成3-结点或4-结点(这样最终能保证最后被删除的结点是红结点,并位于整棵树的底端);
递归终结的条件是当目标结点h的右子树为null,此时h就是最大结点。

具体来说,步骤如下:

  1. 遇到左倾红边,就将其右旋(保证较大元素被“推”到右子树去),如下图:

图片 19

2.
遇到当前结点h的右子结点是2-结点时(即h.right==BLACK&&h.right.left==BLACK):
①若h的左子结点是2-结点(即h.left.left==BLACK),采取合并策略,如下图:

图片 20

②若h的左子结点不是2-结点(即h.left.left==RED),采取借取策略,如下图:

图片 21

上述①②归结起来就是:

/**
 * 将以h为根的树进行调整,使其右子结点变成非2-结点
 * (假设h是红结点,且h的右子结点为2-结点)
 * 
 * @return 返回新树的根结点
 */
private Node moveRedRight(Node h) {
    // assert (h != null);
    // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
    flipColors(h);
    if (isRed(h.left.left)) {
        h = rotateRight(h);
        flipColors(h);
    }
    return h;
}

删除最大结点-完整代码:

public void deleteMax() {
    if (isEmpty())
        throw new NoSuchElementException("BST underflow");

    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;

    root = deleteMax(root);
    if (!isEmpty())
        root.color = BLACK;
}
/**
 * 删除以h为根的树的最大结点
 * 
 * @return 返回删除并修复后新树的根节点
 */
private Node deleteMax(Node h) {
    if (isRed(h.left))         //遇到左倾红边,就将其右旋
        h = rotateRight(h);
    if (h.right == null)       //h即为最大结点
        return null;

    if (!isRed(h.right) && !isRed(h.right.left))  //h的右子结点为2-结点
        h = moveRedRight(h);

    h.right = deleteMax(h.right);

    return fixUp(h);           //向上修复红黑树
}

删除最大结点示例1(左子结点都是2-结点):

图片 22

3-4-3 删除示例(左子结点都是2-结点)

删除最大结点示例2:

图片 23

typedef   struct  _data

3.4.2 删除最小结点

显然,最小结点一定在最左边,最左边的结点可能有3种情况:2-结点、3-结点、4-结点。
对于每种情况如何删除,参考3.4.1删除最大结点的方式。

那么,如何转换成红黑树的相应操作呢?

做法如下:
当我们在沿左子树不断递归向下的过程中:
①遇到左倾红边则忽略,因为左倾红黑树的红边本来就是左倾的;
②遇到左子结点是2-结点时,就按照上面所说的合并/借取策略将2-结点转化成3-结点或4-结点(这样最终能保证最后被删除的结点是红结点,并位于整棵树的底端);
递归终结的条件是当目标结点h的左子树为null,此时h就是最小结点。

具体来说,步骤如下:
1.
遇到当前结点h的左子结点是2-结点时(即h.left==BLACK&&h.left.left==BLACK):
①若h的右子结点是2-结点(即h.right.left==BLACK),采取合并策略,如下图:

图片 24

②若h的右子结点不是2-结点(即h.right.left==RED),采取借取策略,如下图:

图片 25

上述①②归结起来就是:

/**
 * 将以h为根的树进行调整,使其左子结点变成非2-结点
 * (假设h是红结点,且h的左子结点为2-结点)
 * 
 * @return 返回新树的根结点
 */
private Node moveRedLeft(Node h) {
    // assert (h != null);
    // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);
    flipColors(h);
    if (isRed(h.right.left)) {
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
        flipColors(h);
    }
    return h;
}

删除最小结点-完整代码:

public void deleteMin() {
    if (isEmpty())
        throw new NoSuchElementException("BST underflow");

    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;

    root = deleteMin(root);
    if (!isEmpty())
        root.color = BLACK;
}

/**
 * 删除以h为根的树的最小结点
 * 
 * @return 返回删除并修复后新树的根节点
 */
private Node deleteMin(Node h) {
    if (h.left == null)     //h即为最小结点
        return null;

    if (!isRed(h.left) && !isRed(h.left.left))    //h的左子结点为2-结点
        h = moveRedLeft(h);

    h.left = deleteMin(h.left);
    return fixUp(h);        //向上修复红黑树
}

删除最小结点示例(右子结点都是2-结点):

图片 26

3-4-2 删除最小结点示例(右子结点都是2-结点)

{

3.4.3 删除任意结点

有了上述的铺垫,删除任意结点就相对简单很多了,其实思路是一样的,如果所要删除的结点在3-结点或者4-结点中,根据2-3-4树的性质直接删除就可以了。
最复杂的情况是如果是2-结点,那么删除就会引起不平衡。
所以就得从兄弟结点中借一个结点,但由于是任意结点,不像删除最大最小的情况,确定是左边或者右边,而是有很多种情况。根据理论研究,有9
* 6 + 27 * 9 + 81 * 12 = 1269多种情况,所以单纯的这种思路是不行的。

正确的思路:
像堆那样,如果要删除一个结点,把待删除结点和最底部的结点交换,然后就变成删除最底部的结点,就可以转换成删除最大结点或者最小结点了。
这样也把问题简化了,因为删除最大和最小结点的方法我们已经分析出来了。

具体步骤:

  1. 查找待删除结点的右子树中的最小结点(即后继结点);
  2. 将待删除结点置为后继结点;
  3. 删除待删除结点的后继结点。

归结起来就是:

Node x = min(h.right);
h.key = x.key;
h.val = x.val;
h.right = deleteMin(h.right);

例如,要删除下面这棵红黑树的D结点,步骤如下:
1.
选用D结点左子树的最大结点或者右子树的最小结点来替换D的值(本质就是用离D最近的结点替换掉D,然后将替换的结点删除,那么树仍然是有序的);

  1. 然后删除D结点左子树的最大结点右子树的最小结点

图片 27

3-4-3 选用D的右子树的最小结点作替换

删除任意结点-完整源码:

public void delete(Key key) {
    if (key == null)
        throw new IllegalArgumentException("argument to delete() is null");
    if (!contains(key))
        return;

    // if both children of root are black, set root to red
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;

    root = delete(root, key);
    if (!isEmpty())
        root.color = BLACK;
}
/**
 * 删除以h为根的树中的指定结点
 * 
 * @return 返回删除后新树的根结点
 */
private Node delete(Node h, Key key) {
    // assert get(h, key) != null;
    int cmp = key.compareTo(h.key);
    if (cmp < 0) {    //待删除结点<当前结点,则在左子树中递归(采用5.2删除最小结点的变换方式)
        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
        h.left = delete(h.left, key);
    } else {          //待删除结点≥当前结点,则在右子树中递归(采用5.1删除最大结点的变换方式)
        if (isRed(h.left))
            h = rotateRight(h);

        if (cmp == 0 && (h.right == null))
            return null;

        if (!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h);

        if (cmp == 0) {   //找到待删除结点等于当前结点
            Node x = min(h.right);
            h.key = x.key;
            h.val = x.val;
            h.right = deleteMin(h.right);
        } else            //待删除结点>当前结点
            h.right = delete(h.right, key);
    }
    return fixUp(h);
}

  int  value;

四、性能分析

无论键的插入顺序如何,红黑树都几乎是完美平衡的。

一棵大小为N的红黑树,最大高度为2lgN(交替出现红黑结点),最小高度为lgN(所有结点都是黑色)。

  • 时间复杂度
    O(lgN)

}data;

 

typedef  struct  _redblack

{

  color    m_color;

  data   *m_data;

  struct  _redblack  *parent;

  struct  _redblack  *left;

  struct  _redblack  *right;

}redblack;

 

typedef  struct  _wrapdata

{

  redblack  *root;

  int  size;

}wrapdata;

 

int  compare ( redblack  *left ,redblack  *right)

{

  if(left->m_data->value >  right->m_data->value)

    {

      return  1;

    }

  else

    {

      return  0;

    }

}

 

redblack  * newstruct ( data *newdata)

{

  redblack  *newnode;

  newnode=(redblack *)calloc (1 ,sizeof (redblack));

  newnode->m_color=RED;

  newnode->m_data=newdata;

  return  newnode;

}

 

void  rotate_right ( redblack * left ,redblack  *right )

{

 

  right->left=left->right;

  if(left->right)

    {

      left->right->parent=right;

    }

 

  left->right=right;

  left->parent=right->parent;

  if(right->parent)

    {

      if(right->parent->left==right)

 {

      right->parent->left=left;

 }

      else

 {

      right->parent->right=left;

 }

    }

  right->parent=left;

 

}

 

void  rotate_left ( redblack * left ,redblack  *right )

{

  left->right=right->left;

  if (right->left)

    {

      right->left->parent=left;

    }

 

  right->left=left;

  right->parent=left->parent;

  if(left->parent)

    {

      if(left->parent->right==left)

 {

      left->parent->right=right;

 }

      else

 {

      left->parent->left=right;

 }

    }

  left->parent=right;

}

 

void   mid_print (redblack  *root)

{

  if (!root)

    {

      return;

    }

  else

    {

      mid_print (root ->left);

      printf(“%d   “,root->m_data->value);

      mid_print  (root  ->right);

    }

}

 

void   left_print (redblack  *root)

{

  if (!root)

    {

      return;

    }

  else

    {

      printf(“%d   “,root->m_data->value);

      left_print (root ->left);

      left_print  (root  ->right);

    }

}

 

 

void   right_print (redblack  *root)

{

  if (!root)

    {

      return;

    }

  else

    {

      right_print (root ->left);

      right_print  (root  ->right);

      printf(“%d   “,root->m_data->value);

    }

}

 

int  depth(redblack  *root)

{

  int  left,right;

  if (!root)

    {

      return 0;

    }

  else

    {

      left=depth(root->left);

      right=depth(root->right);

      return        left>right ? ( left+1):(right+1);

 

    }

}

void  insert_fixup (wrapdata  *node , redblack *newnode)

{

 

  redblack *curnode;

  redblack  *parent;

  redblack  *grandparent;

  redblack *tmp;

  curnode=newnode;

  parent=curnode->parent;

  while(  curnode->m_color==RED  &&   parent ->m_color==RED)

    {

      grandparent=parent->parent;

      if ( curnode == parent->left)

 {

   if (  parent == grandparent->left)

     {

       curnode->m_color=BLACK;

       rotate_right ( parent , grandparent);

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

     }

   else

     {

       //       printf(“nothing”);

       rotate_right (curnode,  parent );

       tmp=parent;

       parent=curnode;

       curnode=tmp;

 

       curnode->m_color=BLACK;

       rotate_left (grandparent ,parent );

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

 

 

     }

 }

      else

 {

   if (  parent== grandparent->right)

     {

       curnode->m_color=BLACK;

       rotate_left (grandparent,parent );

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

 

     }

   else

     {

       //       printf(“nothing”);

       rotate_left (  parent ,curnode);

       tmp=parent;

       parent=curnode;

       curnode=tmp;

 

       curnode->m_color=BLACK;

       rotate_right (parent,grandparent );

 

       curnode=parent;

              parent=curnode->parent;

              if(!parent )

  {

    node->root=curnode;

    break;

  }

     }

 }

    }

}

 

void  insert  ( wrapdata  *node , data *newdata )

{

  redblack  *newnode;

  redblack  *curnode;

 

  newnode=newstruct (newdata);

 

  node->size++;

  if ( ! node->root)

    {

      node->root= newnode;

 

    }

  else

    {

      curnode=node->root;

      while(1)

 {

   if (   compare ( newnode ,curnode))

     {

       if (!curnode->right)

  {

    curnode->right=newnode;

    newnode->parent=curnode;

 

    break;

  }

       else

  {

    curnode=curnode->right;

  }

     }

   else

     {

       if (!curnode->left)

  {

    curnode->left=newnode;

    newnode->parent=curnode;

    break;

  }

       else

  {

    curnode=curnode->left;

  }

 

     }

 

 }

      insert_fixup ( node , newnode);

 

    }

  node->root->m_color=BLACK;

 

}

 

 

int  main()

{

  int  i;

  wrapdata  *node;

  data  *newdata;

  int 
value[]={12,24,25,9,4,91,2,100,29,888,10,22,5,11,111,7,13,1,99,222,98,17,8,55,44,33,21,77,199,2345,46,49,51,53,54,52,50,48,47,45,43,42,41,40,39,38,37,78,79,80,81,82,83,84,85};

  node=(wrapdata*)calloc (1  ,sizeof (wrapdata));

  for (i=0;i<sizeof (value)/sizeof(int );i++)

    {

      newdata=(data *)calloc (1 ,sizeof (data));

      newdata->value=value[i];

      insert (node ,newdata);

    } www.2cto.com

 

  printf(“%d  \n”,depth (node->root));

 

  mid_print (node->root);

  printf(“\n”);

  left_print (node->root);

  printf(“\n”);

  right_print (node->root);

  printf(“\n”);

  return  0;

}

 

  摘自 chenbingchenbing的专栏

#include stdio.h
#include stdlib.h typedef enum _color { RED, BLACK }color; typedef
struct _data { int value; }data; typedef struct _redblack…

相关文章