`
kmplayer
  • 浏览: 508980 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

红黑树

 
阅读更多
二叉排序树
1,二叉排序树(Binary Sort Tree)又称二叉查找树。
2,它或者是一棵空树;或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;

平衡二叉树
1,平衡二叉树,又称AVL树。
2,它或者是一棵空树,或者是具有下列性质的二叉树:
(1)它的左子树和右子树都是平衡二叉树;
(2)左子树和右子树的高度之差之差的绝对值不超过1.

红黑树

1,红黑树是一种自平衡二叉查找树.
典型的用途是实现关联数组。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。
2,红黑树是一种很有意思的平衡检索树。
它的统计性能要好于平衡二叉树(AVL-树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持)。
3,红黑树的每个节点上的属性除了有一个key、3个指针:parent、lchild、rchild以外,还多了一个属性:color。它只能是两种颜色:红或黑。而红黑树除了具有二叉搜索树的所有性质之外,还具有以下4点性质:
(1). 根节点是黑色的。
(2). 空节点是黑色的(红黑树中,根节点的parent以及所有叶节点lchild、rchild都不指向NULL,而是指向一个定义好的空节点)。
(3). 红色节点的父、左子、右子节点都是黑色。
(4). 在任何一棵子树中,每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。

4,在插入、删除节点后,就有可能破坏了红黑树的性质。所以我们要做一些操作来把整棵树修补好。下面我就来介绍一下。

首先有一个预备知识,那就是节点的Left-Rotate和Right-Rotate操作。所谓Left-Rotate(x)就是把节点x向左下方向移动一格,然后让x原来的右子节点代替它的位置。而Right-Rotate当然就是把Left-Rotate左、右互反一下。如下图:



一、 插入

插入首先是按部就班二叉搜索树的插入步骤,把新节点z插入到某一个叶节点的位置上。
接下来把z的颜色设成红色。为什么?还记得红黑树的性质吗,从根节点向下到空节点的每一条路径上的黑色节点数要相同。如果新插入的是黑色节点,那么它所在的路径上就多出了一个黑色的节点了。所以新插入的节点一定要设成红色。但是这样可能又有一个矛盾,如果z的父节点也是红色,怎么办,前面说过红色节点的子节点必须是黑色。因此我们要执行下面一个迭代的过程,称为Insert-Fixup,来修补这棵红黑树。

在Insert-Fixup中,每一次迭代的开始,指针z一定都指向一个红色的节点。如果z->parent是黑色,那我们就大功告成了;如果z->parent是红色,显然这就违返了红黑的树性质,那么我们要想办法把z或者z->parent变成黑色,但这要建立在不破坏红黑树的其他性质的基础上。

这里再引入两个指针:grandfather,指向z->parent->parent,也就是z的爷爷(显然由于 z->parent为红色,grandfather一定是黑色);uncle,指向grandfather除了z->parent之外的另一个子节点,也就是z的父亲的兄弟,所以叫uncle。

(为了说话方便,我们这里都假设z->parent是grandfather的左子节点,而uncle是grandfather的右子节点。如果遇到的实际情况不是这样,那也只要把所有操作中的左、右互反就可以了。)

在每一次迭代中,我们可能遇到以下三种情况。
Case 1. uncle也是红色。这时只要把z->parent和uncle都设成黑色,并把grandfather设成红色。这样仍然确保了每一条路径上的黑色节点数不变。然后把z指向grandfather,并开始新一轮的迭代。
如下图:



Case 2. uncle是黑色,并且z是z->parent的右子节点。这时我们只要把z指向z->parent,然后做一次Left- Rotate(z)。就可以把情况转化成Case 3。

Case 3. uncle是黑色,并且z是z->parent的左子节点。到了这一步,我们就剩最后一步了。只要把z->parent设成黑色,把 grandfather设成红色,再做一次Right-Rotate(grandfather),整棵树就修补完毕了。可以思考一下,这样一次操作之后,确实满足了所有红黑树的性质。
Case 2和Case 3如下图:


反复进行迭代,直到某一次迭代开始时z->parent为黑色而告终,也就是当遇到Case 3后,做完它而告终。

二、删除

让我们来回顾一下二叉搜索树的删除节点z的过程:如果z没有子节点,那么直接删除即可;如果z只有一个子节点,那么让这个子节点来代替z的位置,然后把z删除即可;如果z有两个子节点,那么找到z在中序遍历中的后继节点s(也就是从z->rchild开始向左下方一直走到底的那一个节点),把 s的key赋值给z的key,然后删除s。

在红黑树中,删除一个节点z的方法也是首先按部就班以上的过程(当然,前面说的“如果 z 没有子节点”等类似的判别条件,在红黑树中,要加上“除了空节点之外”这个前提)。
如果删除的节点是黑色的,那么显然它所在的路径上就少一个黑色节点,那么红黑树的性质就被破坏了。这时我们就要执行一个称为Delete-Fixup的过程,来修补这棵树。下面我就来讲解一下。

一个节点被删除之后,一定有一个它的子节点代替了它的位置(即使是叶节点被删除后,也会有一个空节点来代替它的位置。前面说过,在红黑树中,空节点是一个实际存在的节点。)。我们就设指针x指向这个代替位置的节点。
显然,如果x是红色的,那么我们只要把它设成黑色,它所在的路径上就重新多出了一个黑色节点,那么红黑树的性质就满足了。
然而,如果x是黑色的,那我们就要假想x上背负了2个单位的黑色。那么红黑树的性质也同样不破坏,但是我们要找到某一个红色的节点,把x上“超载”的这1 个单位的黑色丢给它,这样才算完成。Delete-Fixup做的就是这个工作。

Delete-Fixup同样是一个循环迭代的过程。每一次迭代开始时,如果指针x指向一个红色节点,那么大功告成,把它设成黑色即告终。相反如果 x黑色,那么我们就会面对以下4种情况。

这里引入另一个指针w,指向x的兄弟。这里我们都默认x是x->parent的左子节点,则w是x->parent的右子节点。(如果实际遇到相反的情况,只要把所有操作中的左、右互反一下就可以了。)

Case 1. w是红色。这时我们根据红黑树的性质可以肯定x->parent是黑色、w->lchild是黑色。我们把x->parent与w的颜色互换,然后做一次Left-Rotate(x->parent)。做完之后x就有了一个新的兄弟:原w->lchild,前面说过它一定是黑色的。那么我们就在不破坏红黑树性质的前提下,把Case 1转换成了Case2、3、4中的一个,也就是w是黑色的情况。思考一下,这样做不会改变每条路径上黑色节点的个数,如下图:

4,实现代码:
#include <iostream>
using namespace std;



//Key中的内容可能更复杂,比如字符串等。
struct Key
{
    int value;
};

struct RBTNode
{
    Key key;
    int lcount;
    int rcount;
    RBTNode* lchild;
    RBTNode* rchild;
    RBTNode* parent;
    bool color;
};

class RBT
{
private:
    const static bool RED = true;
    const static bool BLACK = false;
    RBTNode* m_null;
    RBTNode* m_root;

    void clear();
    void delFixup(RBTNode* delNode);
    void insertFixup(RBTNode* insertNode);
    //比较两个Key的大小。这里可能有更复杂的比较,如字符串比较等。
    inline int keyCmp(const Key& key1, const Key& key2)
    {
        return key1.value - key2.value;
    }

    //把一个节点向左下方移一格,并让他原来的右子节点代替它的位置。
    inline void leftRotate(RBTNode* node)
    {
        RBTNode* right = node->rchild;
        node->rchild = right->lchild;
        node->rcount = right->lcount;
        node->rchild->parent = node;
        right->parent = node->parent;
        if (right->parent == m_null)
        {
            m_root = right;
        }
        else if (node == node->parent->lchild)
        {
            node->parent->lchild = right;
        }
        else
        {
            node->parent->rchild = right;
        }
        right->lchild = node;
        right->lcount += node->lcount + 1;
        node->parent = right;
    }

    //把一个节点向右下方移一格,并让他原来的左子节点代替它的位置。
    inline void rightRotate(RBTNode* node)
    {
        RBTNode* left = node->lchild;
        node->lchild = left->rchild;
        node->lcount = left->rcount;
        node->lchild->parent = node;
        left->parent = node->parent;
        if (left->parent == m_null) {
            m_root = left;
        }
        else if (node == node->parent->lchild) {
            node->parent->lchild = left;
        }
        else {
            node->parent->rchild = left;
        }
        left->rchild = node;
        left->rcount += node->rcount + 1;
        node->parent = left;
    }

    //找到子树中最大的一个节点
    RBTNode* treeMax(RBTNode* root);
    //找到子树中最小的一个节点
    RBTNode* treeMin(RBTNode* root);

public:
    RBT();
    ~RBT();
    //找到从小到大排序后下标为i的节点。i从0开始。
    RBTNode* atIndex(int i);
    //删除一个节点
    void del(RBTNode* node);
    void init();
    //插入一个节点
    void insert(const Key& key);
    //返回节点的总个数
    int nodeCount();
    //按照key查找一个节点。
    RBTNode* search(const Key& key);
    //把树中节点的值放进一个数组。
    void toArray(int* array);
    //一个节点在中序遍列中的下一个节点。
    RBTNode* treeNext(RBTNode* node);
    //一个节点在中序遍列中的前一个节点。
    RBTNode* treePre(RBTNode* node);
};

void RBT::clear()
{
    RBTNode* p = m_root;
    while (p != m_null)
    {
        if (p->lchild != m_null) {
            p = p->lchild;
        }
        else if (p->rchild != m_null) {
            p = p->rchild;
        }
        else {
            RBTNode* temp = p;
            p = p->parent;
            if (temp == p->lchild)
            {
                p->lchild = m_null; //null取代当前要被删除的节点
            }
            else {
                p->rchild = m_null;
            }
            delete temp;
        }
    }
}

//待看...
void RBT::delFixup(RBTNode* delNode)
{
    RBTNode* p = delNode;
    while (p != m_root && p->color == BLACK) {
        if (p == p->parent->lchild) {
            RBTNode* sibling = p->parent->rchild;
            if (sibling->color == RED) {
                sibling->color = BLACK;
                p->parent->color = RED;
                leftRotate(p->parent);
                sibling = p->parent->rchild;
            }
            if (sibling->lchild->color == BLACK
                && sibling->rchild->color == BLACK
               ) {
                sibling->color = RED;
                p = p->parent;
            }
            else {
                if (sibling->rchild->color == BLACK) {
                    sibling->lchild->color = BLACK;
                    sibling->color = RED;
                    rightRotate(sibling);
                    sibling  = sibling->parent;
                }
                sibling->color = sibling->parent->color;
                sibling->parent->color = BLACK;
                sibling->rchild->color = BLACK;
                leftRotate(sibling->parent);
                p = m_root;
            }
        }
        else {
            RBTNode* sibling = p->parent->lchild;
            if (sibling->color == RED) {
                sibling->color = BLACK;
                p->parent->color = RED;
                rightRotate(p->parent);
                sibling = p->parent->lchild;
            }
            if (sibling->lchild->color == BLACK
                && sibling->rchild->color == BLACK
               ) {
                sibling->color = RED;
                p = p->parent;
            }
            else {
                if (sibling->lchild->color == BLACK) {
                    sibling->rchild->color = BLACK;
                    sibling->color = RED;
                    leftRotate(sibling);
                    sibling = sibling->parent;
                }
                sibling->color = sibling->parent->color;
                sibling->parent->color = BLACK;
                sibling->lchild->color = BLACK;
                rightRotate(sibling->parent);
                p = m_root;
            }
        }
    }
    p->color = BLACK;
}

void RBT::insertFixup(RBTNode* insertNode)
{
    RBTNode* p = insertNode;
    while (p->parent->color == RED)
    {
        if (p->parent == p->parent->parent->lchild)
        {
            RBTNode* parentRight = p->parent->parent->rchild;
            if (parentRight->color == RED)
            {
                p->parent->color = BLACK;
                parentRight->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;
            }
            else
            {
                if (p == p->parent->rchild)
                {
                    p = p->parent;
                    leftRotate(p);
                }
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                rightRotate(p->parent->parent);
            }
        }
        else
        {
            RBTNode* parentLeft = p->parent->parent->lchild;
            if (parentLeft->color == RED)
            {
                p->parent->color = BLACK;
                parentLeft->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;
            }
            else
            {
                if (p == p->parent->lchild)
                {
                    p = p->parent;
                    rightRotate(p);
                }
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                leftRotate(p->parent->parent);
            }
        }
    }
    m_root->color = BLACK;
}

RBTNode* RBT::treeMax(RBTNode* root)
{
    RBTNode* result = root;
    while (result->rchild != m_null)
    {
        result = result->rchild;
    }
    return result;
}

//找到子树中最小的一个节点
RBTNode* RBT::treeMin(RBTNode* root)
{
    RBTNode* result = root;
    while (result->lchild != m_null)
    {
        result = result->lchild;
    }
    return result;
}

RBT::RBT() : m_null(new RBTNode)
{
    m_null->color = BLACK;
    m_root = m_null;
}

RBT::~RBT()
{
    clear();
    delete m_null;
}

//找到从小到大排序后下标为i的节点。i从0开始。
RBTNode* RBT::atIndex(int i)
{
    RBTNode* result = m_root;
    if (i > result->lcount + result->rcount)
    {
        result = NULL;
    }
    else
    {
        while (i != result->lcount)
        {
            if (i < result->lcount) //懂
            {
                result = result->lchild;
            }
            else
            {
                i -= result->lcount + 1;
                result = result->rchild;
            }
        }
    }
    return result;
}

//删除一个节点
void RBT::del(RBTNode* node) //?????????????
{
    RBTNode* toDel = node;
    if (node->lchild != m_null && node->rchild != m_null)
    {
        toDel = treeNext(node); //?????????
    }

    RBTNode* temp = toDel;
    while (temp->parent != m_null)
    {
        if (temp == temp->parent->lchild)
        {
            temp->parent->lcount--;
        }
        else
        {
            temp->parent->rcount--;
        }
        temp = temp->parent;
    }

    RBTNode* replace = toDel->lchild != m_null? toDel->lchild: toDel->rchild;
    replace->parent = toDel->parent;
    if (replace->parent == m_null)
    {
        m_root = replace;
    }
    else if (toDel == toDel->parent->lchild)
    {
        replace->parent->lchild = replace;
    }
    else
    {
        replace->parent->rchild = replace;
    }
    if (toDel != node)
    {
        node->key = toDel->key;
    }
    if (toDel->color == BLACK)
    {
        //修改树,以保持平衡。
        delFixup(replace);
    }
    delete toDel;
}

void RBT::init()
{
    clear();
    m_root = m_null;
}

    //插入一个节点
void RBT::insert(const Key& key) //懂
{
    RBTNode* node = new RBTNode;
    node->key = key;
    node->lcount = 0;
    node->rcount = 0;
    node->lchild = m_null;
    node->rchild = m_null;
    node->color = RED;

    RBTNode* p = m_root;
    RBTNode* leaf = m_null;
    while (p != m_null)
    {
        leaf = p;
        if (keyCmp(node->key, p->key) < 0)
        {
            p->lcount++;
            p = p->lchild;
        }
        else
        {
            p->rcount++;
            p = p->rchild;
        }
    }
    node->parent = leaf;
    if (leaf == m_null)//如果是空树。
    {
        m_root = node;
    }
    else if (keyCmp(node->key, leaf->key) < 0)
    {
        leaf->lchild = node;
    }
    else {
        leaf->rchild = node;
    }
    //修改树,以保持平衡。
    insertFixup(node);
}

int RBT::nodeCount()
{
    return m_root != m_null? m_root->lcount + m_root->rcount + 1: 0;
}

//按照key查找一个节点。
RBTNode* RBT::search(const Key& key)
{
    RBTNode* result = m_root;
    while (result != m_null && keyCmp(key, result->key) != 0)
    {
        result = keyCmp(key, result->key) < 0 ? result->lchild: result->rchild;
    }
    return result == m_null? NULL: result;
}

//把树中节点的值放进一个数组。
void RBT::toArray(int* array)
{
    RBTNode* p = treeMin(m_root);
    int i = 0;
    while (p != m_null)
    {
        array[i] = p->key.value;
        i++;
        p = treeNext(p);//按照中序遍历的顺序放入
    }
}

//一个节点在中序遍列中的下一个节点。
RBTNode* RBT::treeNext(RBTNode* node)
{
    RBTNode* result;
    if (node->rchild != m_null)
    {
        result = treeMin(node->rchild);
    }
    else
    {
        result = node->parent;
        RBTNode* temp = node;
        while (result != m_null && temp == result->rchild)
        {
            temp = result;
            result = result->parent;
        }
    }
    return result;
}

//一个节点在中序遍列中的前一个节点。
RBTNode* RBT::treePre(RBTNode* node)
{
    RBTNode* result;
    if (node->lchild != m_null)
    {
        result = treeMax(node->lchild); //有修改
    }
    else
    {
        result = node->parent;
        RBTNode* temp = node;
        while (result != m_null && temp == result->lchild)
        {
            temp = result;
            result = result->parent;
        }
    }
    return result;
}

int main()
{
    return 0;
}


  • 大小: 35.6 KB
  • 大小: 8.4 KB
  • 大小: 7.6 KB
  • 大小: 9.4 KB
分享到:
评论

相关推荐

    红黑树-动态演示生成红黑树

    红黑树(Red-Black Tree)是一种自平衡二叉查找树,由计算机科学家鲁道夫·贝尔在1978年提出。它在保持二叉查找树特性的同时,通过引入颜色属性来确保树的平衡,从而提高了数据操作的效率。红黑树的主要目标是保证在...

    红黑树的源码与测试函数

    红黑树(Red-Black Tree)是一种自平衡二叉查找树,它的每个节点都带有颜色属性,可以是红色或黑色。这种数据结构被广泛应用于计算机科学的许多领域,特别是操作系统、数据库系统以及编译器中,用于高效地执行插入、...

    红黑树原理详解

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年发明。它的名称来源于其节点颜色属性,即红色和黑色。红黑树的主要特性保证了其在插入、删除和查找操作中的高效性能,通常时间复杂度为O(log n),其中n是树中...

    红黑树-使用C++实现-简单练习

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer于1972年提出。它的设计目标是在保持二叉查找树基本属性的同时,通过引入颜色(红色或黑色)来保证树的平衡,从而在插入和删除操作后能够快速恢复平衡状态,减少查找、...

    红黑树的插入与删除_详细整理资料

    ### 红黑树的插入与删除:详细解析 红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年发明,最初被称为“对称二叉B树”。它在1978年Leo J. Guibas和Robert Sedgewick的论文中获得了现代名称“红黑树”。红黑树...

    红黑树和AVL树的实现

    红黑树和AVL树是两种自平衡二叉查找树,它们在计算机科学中的数据结构领域扮演着重要的角色,主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡,从而确保搜索、插入和删除...

    红黑树java操作代码 红黑树是java里面遍历性能最好数据结构

    红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在实现高效的数据结构和算法时。在Java中,虽然标准库并未直接提供红黑树的类,但我们可以自定义实现,如提供的`Red...

    红黑树完整实现文件

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本属性的同时,通过引入颜色(红色或黑色)来保证树的平衡,从而提高查找、插入和删除操作的效率。在红黑树中,每个...

    红黑树代码

    红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...

    gcc 红黑树(二叉搜索树 红黑树 动态排序树 精确计时)

    红黑树是一种自平衡二叉查找树,它的设计目的是为了在保持查找效率的同时,尽可能地减少插入和删除操作带来的性能损失。在计算机科学中,它是一种广泛应用的数据结构,特别是在动态排序和高效查找方面。 二叉搜索树...

    Linux内核红黑树封装的通用红黑树

    通用红黑树 说明: 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树: 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者:rcyh 日期:2011年7月21日 ---------------------------------...

    红黑树的C实现,算法导论的红黑树C实现

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本性质的同时,通过引入颜色属性来保证树的平衡,从而达到高效的插入、删除和查找操作。红黑树的关键特性是: 1. 每...

    红黑树的例子

    ### 红黑树知识点详解 #### 一、红黑树定义与性质 红黑树是一种自平衡二叉查找树,其每个节点除了保存键值、左子节点、右子节点和父节点的信息外,还额外保存了一个表示颜色的属性(红色或黑色)。红黑树在进行...

    红黑树、区间树

    红黑树和区间树是两种在计算机科学中广泛使用的数据结构,主要应用于高效的数据存储和检索。它们在算法和数据结构领域具有重要地位,尤其在处理动态集合或需要快速查找和更新操作的问题时。 首先,我们来详细了解...

    红黑树-数据结构

    红黑树是一种自平衡二叉查找树(self-balancing binary search tree),由计算机科学家Rudolf Bayer在1972年提出。它在保持二叉查找树特性的同时,通过引入颜色属性来确保树的平衡,从而提高数据操作的效率。在红黑...

    红黑树实现源码

    红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性:红色或黑色。这种颜色属性被用来确保树的某些关键性质,...

    红黑树的插入详细图解,直接拿下红黑树

    红黑树是一种自平衡二叉查找树,它的主要特点是在保持二叉查找树特性的同时,通过特定的颜色规则来确保树的平衡,以达到快速查找、插入和删除的目的。红黑树的每个节点都有一个颜色属性,可以是红色或黑色。在插入新...

    用c实现的红黑树,经典的红黑树,

    红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持查询效率高的同时,尽可能地减少由于插入和删除操作引起的树的不平衡。红黑树的主要特点包括: 1. **颜色属性**:每个节点都有...

    红黑树Java实现

    红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性:红色或黑色。这种颜色属性用于确保树的平衡,使得在树中的...

    delphi红黑树源码

    红黑树(Red-Black Tree)是一种自平衡二叉查找树,由计算机科学家Rudolf Bayer在1972年提出。它在数据结构和算法领域具有重要地位,被广泛应用于各种系统和软件中,包括数据库索引、编译器、虚拟机等。在Delphi编程...

Global site tag (gtag.js) - Google Analytics