徒手(加上Wikipedia)实现一颗红黑树


纸上得来终觉浅，觉知此事要躬行。

红黑树是一种什么树，三言两语是说不清楚的，在此推荐Wikipedia页面,为了实现一棵树，我盯着这个页面好些天才算看明白了一点点，我在此主要记录一下代码实现细节过程。

首先定义节点的形式：

/*RBT*/
#include <iostream>
#include<iomanip>
#include <stdlib.h>
#include <vector>
#define RED 0
#define BLACK 1
#define LEFT -1
#define RIGHT 1
using namespace std;
struct RBT_Node {
    int key;
    int color;//颜色
    RBT_Node * left;
    RBT_Node * right;
    RBT_Node * parent;
};
struct RBTree {
    RBT_Node * root;
};

树最重要的是增删查改操作，其中增删是主要的，所以我只实现增加和删除两个操作。

下面来实现节点的插入，根据原理，我们根据给出的key构造一个红节点，插入到树中，插入完毕必须要调整以满足红黑树性质，用RBT_adjust（）来实现，这个函数在后面再写出具体实现。

int RBT_insert(RBT_Node*  p, RBTree&  T, int n) {
    int RBT_adjust(RBT_Node *p, RBTree& t);
    RBT_Node*  node;
    if (T.root == NULL)
    {
        T.root = new RBT_Node;
        node = T.root;
        node->color = RED;//0是红色
        node->key = n;
        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
        RBT_adjust(node, T);
        return 0;
    }

    if (n<p->key) {
        if (p->left == NULL)
        {
            p->left = new RBT_Node;
            node = p->left;
            node->color = RED;//0是红色
            node->key = n;
            node->left = NULL;
            node->right = NULL;
            node->parent = p;
            RBT_adjust(node, T);

        }
        else RBT_insert((p->left), T, n);
        return 0;
    }
    else if (n>p->key) {
        if (p->right == NULL)
        {
            p->right = new RBT_Node;
            node = p->right;
            node->color = RED;//0是红色
            node->key = n;
            node->left = NULL;
            node->right = NULL;
            node->parent = p;
            RBT_adjust(node, T);
        }
        else RBT_insert((p->right), T, n);
        return 0;
    }
    else return -1;
}

接下来定义几个工具函数，分别实现几种旋转，找到叔叔节点，判断孩子和父亲的左右关系等等。


int RBT_adjust_LL(RBT_Node* p, RBTree& t) {
    RBT_Node** temp = NULL;
    if (p->parent == NULL) {
        t.root = p->right;
        p->right->parent = NULL;
        p->right = p->right->left;
        if (p->right != NULL) p->right->parent = p;
        t.root->left = p;
        p->parent = t.root;
        return 0;
    }
    else {
        if (p->parent->right == p)temp = &(p->parent->right);
        else temp = &(p->parent->left);
        *temp = p->right;
        p->right->parent = p->parent;
        p->right = p->right->left;
        if (p->right != NULL) p->right->parent = p;
        (*temp)->left = p;
        p->parent = (*temp);
        return 0;
    }

}

int RBT_adjust_RR(RBT_Node* p, RBTree& t) {
    RBT_Node** temp = NULL;
    if (p->parent == NULL) {
        t.root = p->left;
        p->left->parent = NULL;
        p->left = p->left->right;
        if (p->left != NULL) p->left->parent = p;
        t.root->right = p;
        p->parent = t.root;
        return 0;
    }
    else {
        if (p->parent->right == p)temp = &(p->parent->right);
        else temp = &(p->parent->left);
        *temp = p->left;
        p->left->parent = p->parent;
        p->left = p->left->right;
        if (p->left != NULL) p->left->parent = p;
        (*temp)->right = p;
        p->parent = *temp;
        return 0;
    }
}
int RBT_adjust_RL(RBT_Node* p, RBTree& t) {
    RBT_Node* temp1 = p;
    RBT_Node* temp2 = p->right;
    RBT_adjust_RR(temp2, t);
    RBT_adjust_LL(temp1, t);
    return 0;

}
int RBT_adjust_LR(RBT_Node* p, RBTree& t) {
    RBT_Node* temp1 = p;
    RBT_Node* temp2 = p->left;
    RBT_adjust_LL(temp2, t);
    RBT_adjust_RR(temp1, t);
    return 0;
}
bool isRchild(RBT_Node* node) {
    if (node->parent == NULL || node == NULL)return -1;
    if (node->parent->right == node)return true;
    else return false;
}
bool isLchild(RBT_Node* node) {
    if (node->parent == NULL||node==NULL)return -1;
    if (node->parent->left == node)return true;
    else return false;
}
struct RBT_Node* getUncle(RBT_Node* node) {
    //前提是爷爷存在
    if (isLchild(node->parent)) {
        return node->parent->parent->right;
    }
    else if (isRchild(node->parent)) {
        return node->parent->parent->left;
    }
}

这便是最核心的部分，也就是插入完成后的调整了，代码中，关键部位，我加了一些注释。

int RBT_adjust_case3(RBT_Node *p, RBTree& t) {
    //爸爸红，叔叔黑或者是null
    if (isLchild(p) && isRchild(p->parent)) {
        RBT_adjust_LR(p->parent->parent,t);
        p->color = BLACK;
        if(p->left)p->left->color = RED;
        if(p->right)p->right->color = RED;
        return 0;
    }
    else if (isRchild(p) && isLchild(p->parent)) {
        RBT_adjust_RL(p->parent->parent,t);
        p->color = BLACK;
         if(p->left)p->left->color = RED;
        if(p->right)p->right->color = RED;
        return 0;
    }
    else if (isLchild(p) && isLchild(p->parent)) {
        RBT_adjust_RR(p->parent->parent,t);
        p->parent->color = BLACK;
        if(p->parent->right)p->parent->right->color = RED;
        if(p->parent->left)p->parent->left->color = RED;
        return 0;
    }
    else {
        RBT_adjust_LL(p->parent->parent,t);
        p->parent->color = BLACK;
        if(p->parent->right)p->parent->right->color = RED;
        if(p->parent->left)p->parent->left->color = RED;
        return 0;
    }

}
int RBT_adjust_case2(RBT_Node *p, RBTree& t) {
    //父亲RED,所以爷爷是黑色,此处父亲红色，所以肯定不是根，爷爷 必定存在
    if ((NULL!= getUncle(p))&&(getUncle(p)->color==RED))
    {
        //若叔叔是红色，可以把爸爸 和叔叔公用的爷爷这个黑色节点，下放到父辈，也就是把爷爷染红，爸爸和叔叔染黑
        //如此一来，就相当于在爷爷处插入了一个新的红节点，需要递归调用调整操作
        p->parent->parent->color = RED;
        getUncle(p)->color = BLACK;
        p->parent->color = BLACK;
        int RBT_adjust(RBT_Node *p, RBTree& t);
        RBT_adjust(p->parent->parent, t);
        return 0;
    }
    else 
    {
        RBT_adjust_case3(p,  t);
        return 0;
    }
}
int RBT_adjust(RBT_Node *p, RBTree& t) {
    if (p->parent == NULL) { p->color = BLACK; return 0; }//插入之后是树根
    if ((p->parent->color) ==BLACK) return 0;
    else RBT_adjust_case2(p,t);
    return 0;
}

这是这段代码中最臭最长的一部分，实现了删除操作，我要说的内容，都在注释内。。。。。。。。。。

//delete
RBT_Node*  getBrother(RBT_Node*p) {
    if (NULL == p || NULL == p->parent)return NULL;
    if (p->parent->left == p)return p->parent->right;
    else return p->parent->left;
    
}
int delete_case6(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node)
{/*所以综合为：父亲红黑均可，兄弟黑，兄弟两个孩子不全黑,且new节点是父亲左孩子时兄弟左孩子是黑的，
    new节点是父亲右孩子时兄弟右孩子是黑的
    如此只剩下：
    当new节点是父亲左孩子时，父亲红，兄弟右孩子红，或父亲黑，兄弟右孩子黑
    当new节点是父亲右孩子时，对称。
    */
    RBT_Node*l, *r;
    if (father_of_new_node->left == new_node)
    {
        l = father_of_new_node->right->left;
        r = father_of_new_node->right->right;
    }
    else
    {
        l = father_of_new_node->left->left;
        r = father_of_new_node->left->right;
    }
    if (new_node->parent->left == new_node)
    {
        RBT_adjust_RR(father_of_new_node,t);
        r->color = BLACK;
    }
    else
    {
        RBT_adjust_LL(father_of_new_node, t);
        l->color = BLACK;
    }

    return 0;
}
int delete_case5(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node)
{//此时前提是，兄弟为黑色,（父亲，兄弟的两个孩子不全为黑色)且有（父亲为红时，兄弟两个孩子不同时为黑）
    //所以综合为：父亲红黑均可，兄弟黑，兄弟两个孩子不全黑
    RBT_Node*l, *r;
    if (father_of_new_node->left == new_node)
    {
        l = father_of_new_node->right->left;
        r = father_of_new_node->right->right;
    }
    else
    {
        l = father_of_new_node->left->left;
        r = father_of_new_node->left->right;
    }

    if (new_node->parent->left==new_node) 
    {
        if (l&&l->color == RED)
        {
            RBT_adjust_RR(l->parent, t);
            l->color = BLACK;
            l->right->color = RED;
        }
    }
    else
    {
        if (r&&r->color == RED)
        {
            RBT_adjust_LL(l->parent, t);
            l->color = BLACK;
            l->left->color = RED;
        }
    }
    delete_case6(t, new_node, father_of_new_node);

    return 0;
}
int delete_case4(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node)
{//此时前提是，兄弟为黑色,（父亲，兄弟的两个孩子不全为黑色)
    RBT_Node*l, *r;
    if (father_of_new_node->left == new_node)
    {
        l = father_of_new_node->right->left;
        r = father_of_new_node->right->right;
    }
    else
    {
        l = father_of_new_node->left->left;
        r = father_of_new_node->left->right;
    }
    if ((NULL == l || l->color == BLACK) && (NULL == r || r->color == BLACK) && father_of_new_node->color == RED)
    {
        father_of_new_node->color = BLACK;
        getBrother(new_node)->color = RED;
        return 0;
    }
    else  delete_case5(t, new_node, father_of_new_node);

}
int delete_case3(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node)
{//此时前提是，兄弟为黑色
    RBT_Node*l, *r;

        if (father_of_new_node->left == new_node)
        {
            l = father_of_new_node->right->left;
            r = father_of_new_node->right->right;
        }
        else
        {
            l = father_of_new_node->left->left;
            r = father_of_new_node->left->right;
        }
    
    
        if ((NULL==l||l->color==BLACK)&&(NULL==r||r->color==BLACK)&&father_of_new_node->color == BLACK)
        {//父亲和兄弟以及兄弟的孩子都是黑的，将兄弟染红，递归调用
            
            if (father_of_new_node->left == new_node)
            {
                father_of_new_node->right->color = RED;
            }
            else
            {
                father_of_new_node->left->color = RED;
            }
            int delete_adjust(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node, int deletedColor);
            delete_adjust(t, father_of_new_node, father_of_new_node->parent, BLACK);//递归
        }
        else delete_case4(t, new_node, father_of_new_node);

        return 0;
}
int delete_case2(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node)
{
    //case2
        
            if (getBrother(new_node))//实际上brother不可能为空
            {
                if (getBrother(new_node)->color == RED)
                {//新节点兄弟是红的，也就决定了父亲是黑的，且兄弟的二个儿子是黑的
                    if (father_of_new_node->left = new_node) 
                    {
                        RBT_adjust_LL(father_of_new_node, t);
                    }
                    else
                    {
                        RBT_adjust_RR(father_of_new_node, t);
                    }
                    father_of_new_node->parent->color = BLACK;
                    father_of_new_node->color = RED;
                }
                 
            }
            delete_case3(t, new_node, father_of_new_node);
            return 0;
        
    
}
int delete_adjust(RBTree& t, RBT_Node*new_node, RBT_Node*father_of_new_node, int deletedColor) {
    //parent_of_deleted至多含有一个非空节点
    //传来的参数给出了被删除节点的颜色,被删除节点的父亲
    if (deletedColor == RED)return 0;
    if (new_node&&new_node->color == RED) {
        //被删掉的是黑色，新顶替上来的是红色
        new_node->color = BLACK; return 0;
    }
    else 
    {//被删掉的是黑色，新顶替上来的是黑色or空，这样这条路径就少了一个黑色
            //case1
        if (NULL == father_of_new_node)return 0;
        else  delete_case2(t,new_node,father_of_new_node);
        
    }

}
int RBT_delete(RBTree& t, RBT_Node*p, int n) {
    if (p == NULL) {
        return 0;
    }
    RBT_Node* temp = NULL;
    if (n == p->key) {
        if ((!(p->left)) && (!(p->right))) {//leaf node
            temp = p;
            if (!p->parent) {//是树内唯一根节点
                t.root = NULL;
                delete p;
                return 0;
            }

            if (p->parent->right == p) { 
                p->parent->right = NULL; 
                delete_adjust(t,temp->parent->right ,temp->parent,0);
            }
            else
            {
                p->parent->left = NULL;
                delete_adjust(t, temp->parent->left,temp->parent, 0);
            }
            delete p;
            return 0;
        }
        else if (p->left) {//若左子树存在则找出左最大的
            temp = p->left;
            while (temp->right != NULL) {
                temp = temp->right;
            }
            p->key = temp->key;//复制key
             
                //if (temp->parent->right == p) p->parent->right = NULL;
                //else temp->parent->left = NULL;
                if (temp->parent->left == temp)
                {
                    temp->parent->left = temp->left;
                    if (temp->left != NULL)temp->left->parent = temp->parent;
                    delete_adjust(t, temp->parent->left,temp->parent,temp->color);
                }
                else
                {
                    temp->parent->right = temp->left;
                    if (temp->left != NULL)temp->left->parent = temp->parent;
                    delete_adjust(t, temp->parent->right, temp->parent, temp->color);
                }
                delete temp;
                return 0;//调整
            
        }
        else if (p->right) {//找右边最小的
            temp = p->right;
            while (temp->left != NULL) {
                temp = temp->left;
            }
            p->key = temp->key;//复制key
            if (temp->parent->left == temp)
            {
                temp->parent->left = temp->right;
                if (temp->right != NULL)temp->right->parent = temp->parent;
                delete_adjust(t, temp->parent->left, temp->parent, temp->color);
            }
            else
            {
                temp->parent->right = temp->right;
                if (temp->right != NULL)temp->right->parent = temp->parent;
                delete_adjust(t, temp->parent->right, temp->parent, temp->color);
            }
            delete temp;
            return 0;//调整

        }
        
    }//p->key==n
    else {
        if (n > p->key) {
            RBT_delete(t, p->right, n);
        }

        else {
            RBT_delete(t, p->left, n);
        }
    }
    return 0;
}

定义两种遍历，用于输出树的形态，方便调试。
前序遍历不必多讲，这个层序遍历我做了换行，一层输出一行，并且红色节点用[]，黑色节点用（），空的位置用+占位，使得二叉树能够可视化表示出来。

//遍历输出
int pre_Treverse(RBT_Node* t) {
    if (t == NULL)
    {
        return 0;
    }
    pre_Treverse(t->left);
    cout << t->key << " ";

    pre_Treverse(t->right);
}
//层序遍历
int levelOrder_traverse(RBTree t) {
    /*
    此函数用于层序使出二叉树，红色节点用[]，黑色节点用（），空的位置用+占位
    */
    if (t.root == NULL)return -1;
    vector<RBT_Node*> vec;
    vec.push_back(t.root);
    int cur = 0;
    int num_of_nextlevel = 1;
    int num_of_nextlevel_notnull = 0;
    int step_of_thislecel = 100;
    while (cur<vec.size())
    {
        for (int i = 0; i < num_of_nextlevel; i++) {

            if (vec.at(cur) == NULL) {
                vec.push_back(NULL); vec.push_back(NULL);
                cout << "+";
            }
            else {
                if (vec.at(cur)->color == BLACK)
                {
                    cout <<"["<< vec.at(cur)->key<<"]";
                }
                else
                {
                    cout << "(" << vec.at(cur)->key << ")";
                }
                if (vec.at(cur)->left != NULL) { vec.push_back(vec.at(cur)->left); num_of_nextlevel_notnull++; }
                else { vec.push_back(NULL); }
                if (vec.at(cur)->right != NULL) { vec.push_back(vec.at(cur)->right); num_of_nextlevel_notnull++; }
                else { vec.push_back(NULL); }
            }

            cur++;
        }
        cout << endl;
        step_of_thislecel /= 2;
        num_of_nextlevel *= 2;
        if (num_of_nextlevel_notnull == 0) break;
        num_of_nextlevel_notnull = 0;

    }//while end
}

main函数现身，程序终于完了。

int main() {
    RBTree T = { NULL };
    for (int i = 0; i < 20; i++) {
        RBT_insert(T.root, T, i);
    }
    pre_Treverse(T.root);
    cout << endl;
    levelOrder_traverse(T);
    cout << endl;
    RBT_delete(T, T.root, 7);
    levelOrder_traverse(T);
    cout << "hello";
    system("pause");
    return 0;

}

运行结果如下：

运行结果

我先顺序插入了20个节点，前序输出，然后层序输出。
然后删除了根节点7，再层序输出，可以看出，树的建立和节点删除没有问题，不过我对软件测试不太了解，也不保证没有bug，但是经过这个过程，对红黑树原理有了更深了解，要debug也不会素手无策了。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,530评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,403评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,120评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,770评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,758评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,649评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,021评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,675评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,931评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,751评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,410评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,004评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,969评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,042评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,493评论 2赞 343

推荐阅读更多精彩内容

  • 红黑树深入剖析及Java实现(转)
    红黑树是平衡二叉查找树的一种。为了深入理解红黑树，我们需要从二叉查找树开始讲起。 BST 二叉查找树（Binary...
    kanehe阅读 1,370评论 0赞 8
  • 疯狂java笔记之树和二叉树
    树的概述 树是一种非常常用的数据结构，树与前面介绍的线性表，栈，队列等线性结构不同，树是一种非线性结构 1.树的定...
    Jack921阅读 4,432评论 1赞 31
  • 数据结构和算法（上）
    1 序 2016年6月25日夜，帝都，天下着大雨，拖着行李箱和同学在校门口照了最后一张合照，搬离寝室打车去了提前租...
    RichardJieChen阅读 5,073评论 0赞 12
  • 数据结构（二）——树结构模型及应用
    基于树实现的数据结构，具有两个核心特征： 逻辑结构：数据元素之间具有层次关系； 数据运算：操作方法具有Log级的平...
    yhthu阅读 4,238评论 1赞 5
  • 宝贝成长记录15 2017年 6月6日
    妈妈：“儿子，今天虽然洗碗打卡结束了，你的宝贝3D打印笔也到了，但这几天我已经习惯了你每天饭后洗碗，要不今天饭后你...
    何金霖阅读 168评论 0赞 0