一种无递归、无栈、无parent指针的红黑树实现

XGN • 2024年10月12日 am11:36 • 技术, 教程

前言

红黑树是一种复杂的平衡树，在大部分情况下都会使用父指针或者递归实现。假如我们一定要三无实现呢？

本文必须配合OI-Wiki食用！！

基础结构

#define BLK_COLOR 0
#define RED_COLOR 1
#define LEFT 0
#define RIGHT 1
#define Color(node) (node==NULL?BLK_COLOR:node->color)
#define Dir(par,node) (par->left==node?LEFT:RIGHT)

struct RBTNode
{
    int data;
    RBTNode *left;
    RBTNode *right;
    int color;

    RBTNode(int data):data(data),left(NULL),right(NULL),color(RED_COLOR){}
};

RBTNode* tree;

//directly insert son under father
void directInsert(RBTNode* fa, RBTNode* son){
    if(fa->data<son->data){
        fa->right=son;
    }else{
        fa->left=son;
    }
}

RBTNode* rotateLeft(RBTNode* root){
    auto r=root->right;
    auto rl=r==NULL?NULL:root->right->left;
    root->right=rl;
    r->left=root;
    return r;
}

RBTNode* rotateRight(RBTNode* root){
    auto l=root->left;
    auto lr=l==NULL?NULL:root->left->right;
    root->left=lr;
    l->right=root;
    return l;
}

插入

插入共有6种情况，其中只有Case 4会将祖父设为红色，从而导致需要递归向上继续维护，其他情况的祖父都是黑色，不需要向上传递。

所以，我们不妨直接从上往下考虑，沿着插入新节点的路径一路向下，如果遇到了黑色节点下面两个儿子都是红色的，我们无论怎样都下放黑色。这个时候如果当前节点的父亲也是红色的，我们不妨视作“插入”了当前节点，进行局部维护即可。我们不难发现，这样维护不再需要上传，因为我们已经下放了上方的所有Case 4的父节点的颜色，我们已经不会出现Case 4.

伪代码:

void insert(int x){
    for(x路径上从上往下的每个节点){
        if(我黑色，两个儿子红色){
            儿子=黑色
            我=红色
            if(爸爸是红色){
                rebalance(我)
            }
        }
    }

    directInsert(x)
    rebalance(新节点)

    if(根节点是红色){
        根节点=黑色
    }
}

真代码：

void insert(int x){
    auto node=new RBTNode(x);

    if(tree==NULL){
        tree=node;
        tree->color=BLK_COLOR;
        return;
    }

    RBTNode* now=tree;
    RBTNode* par=NULL;
    RBTNode* gpar=NULL;
    RBTNode* ggpar=NULL;

    while(true){

        //if can be push down then just push down
        if(now->color==BLK_COLOR && Color(now->left)==RED_COLOR && Color(now->right)==RED_COLOR){
            now->color=RED_COLOR;
            now->left->color=BLK_COLOR;
            now->right->color=BLK_COLOR;

            if(par==NULL){ //tree root
                now->color=BLK_COLOR;
            }else{ //rebalance
                if(par->color==RED_COLOR){
                    rebalance(ggpar,gpar,par,now);
                }
            }
        }

        if(now->data==x){
            //already in tree
            delete node;
            return;
        }
        if(now->data<x){
            //move to the right
            if(now->right==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->right;
        }else{
            //move to the left
            if(now->left==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    directInsert(now,node);

    if(now->color==RED_COLOR){
        rebalance(gpar,par,now,node);
    }

    //ensure root node is black
    if(tree->color==RED_COLOR){
        tree->color=BLK_COLOR;
    }
}

rebalance的情况请看OI-Wiki，下面只给出实现（注意细节！）：

//Assume me is red, par is red
void rebalance(RBTNode* ggpar, RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(gpar==NULL){
        //par is root
        par->color=BLK_COLOR;
        return;
    }

    if(Dir(gpar,par)==LEFT){
        if(Dir(par,me)==RIGHT){
            gpar->left=rotateLeft(par);
            swap(par,me); //after rotation switched place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateRight(gpar);
            }else{
                ggpar->right=rotateRight(gpar);
            }
        }else{
            tree=rotateRight(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }else{
        if(Dir(par,me)==LEFT){
            gpar->right=rotateRight(par);
            swap(par,me); //after rotation swapped place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateLeft(gpar);
            }else{
                ggpar->right=rotateLeft(gpar);
            }
        }else{
            tree=rotateLeft(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }
}

删除

根据OI-Wiki，删除有3（+1）种情况，其中只有一种情况会导致rebalance：那就是删除的点是 黑色叶子 。其根本原因是： 黑高度的改变。只有黑高度改变了，才会上传。

所以删除的核心是判断一棵子树什么时候黑高度会改变！注意到，rebalance的5种情况中，只有Case3黑高度会改变。所以，如果 $h(rt)$ 表示以rt为根的子树黑高度会不会改变，假设我们要删除的节点在左子树种，那么根据Case 3，我们有：

h(rt)= h(L) && (rt.color==Black) && (R.color==Black) && (RL.color==Black) && (RR.color==Black)

其中R为右节点、RL为右节点的左儿子、RR为右节点的右儿子。

所以我们只需要维护最后一个不满足(rt.color==Black) && (R.color==Black) && (RL.color==Black) && (RR.color==Black)的节点，这个节点下面的每个节点黑高度都会改变，都需要rebalance。我们自上而下的rebalance:

伪代码：

void remove(int x){
    先找到结构上要删除的节点toDelete

    for(toDelete路径上每一个节点){
        if(toDelete在左子树中){
            if(我是黑色、右儿子是黑色、右儿子的儿子都是黑色){
                //啥也不做
            }else{
                firstNoShorter=我
            }
        }else{
            //x在右子树中
            对称大法
        }
    }

    if(toDelete是红叶子){
        直接删除;
        return;
    }
    if(toDelete有儿子){
        把儿子挂到toDelete父亲上;
        儿子=黑色;
        return;
    }
    if(toDelete是树中唯一节点){
        tree=NULL;
        return;
    }
    for(firstNoShorter到toDelete路径上的点，但是不含firstNoShorter){
        reblanceRemoval(我)
    }
}

真代码：

void remove(int x){
    RBTNode* now=tree;
    RBTNode* par=NULL;

    RBTNode* nodeX=NULL; //the node containing X
    RBTNode* toDelete=NULL; //really gonna delete this
    RBTNode* toDelPar=NULL;

    RBTNode* parFirstNoShorter=NULL; //parent of first of no shorter
    RBTNode* firstNoShorter=NULL;

    //find node of value x
    while(now!=NULL){
        if(now->data==x){
            //found!
            nodeX=now;
            break;
        }
        if(now->data<x){
            //move to the right
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }else{
            //move to the left

            if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->left;
        }
    }

    if(nodeX==NULL){
        //did not find node
        return;
    }

    //find scapegoat
    if(nodeX->left==NULL){
        toDelPar=par;
        toDelete=nodeX;
    }else{
        if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
            parFirstNoShorter=par;
            firstNoShorter=now;
        }
        par=nodeX;
        now=nodeX->left;
        while(now->right!=NULL){
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }
        toDelPar=par;
        toDelete=now;
    }

    //case 1 it's a leaf red
    if(toDelete->left==NULL && toDelete->right==NULL && toDelete->color==RED_COLOR){
        if(toDelete==par->left){
            par->left=NULL;
        }else{
            par->right=NULL;
        }
        nodeX->data=toDelete->data;
        delete toDelete;
        return;
    }

    //case 2 it has a child (must be red)
    if(toDelete->left!=NULL){
        toDelete->left->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->left;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->left;
            }else{
                par->right=toDelete->left;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }
    if(toDelete->right!=NULL){
        toDelete->right->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->right;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->right;
            }else{
                par->right=toDelete->right;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }

    //tree gone
    if(toDelPar==NULL){
        tree=NULL;
        delete toDelete;
        return;
    }

    //balance
    RBTNode* gpar=parFirstNoShorter;
    par=firstNoShorter;
    if(firstNoShorter==NULL){
        now=tree;
    }else{
        if(firstNoShorter->data<toDelete->data){
            now=firstNoShorter->right;
        }else{
            now=firstNoShorter->left;
        }
    }

    while(now!=NULL){
        rebalanceRemoval(gpar,par,now);
        if(now->data<toDelete->data){
            gpar=par;
            par=now;
            now=now->right;
        }else{
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    nodeX->data=toDelete->data;
    if(toDelete==toDelPar->left){
        toDelPar->left=NULL;
    }else{
        toDelPar->right=NULL;
    }
    delete toDelete;
}

我们按照OI-wiki上的5种情况做balance（注意大量细节）：

void rebalanceRemoval(RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(par==NULL){
        return;
    }
    if(me==par->left){
        auto sib=par->right;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateLeft(par);
                }else{
                    gpar->right=rotateLeft(par);
                }
            }else{
                tree=rotateLeft(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->right;
            //resolve now, par in the next case:
        }

        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->right)==BLK_COLOR){
            //need to fucking rotate
            par->right=rotateRight(sib);
            par->right->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->right;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateLeft(par);
            }else{
                gpar->right=rotateLeft(par);
            }
        }else{
            tree=rotateLeft(par);
        }

        swap(sib->color,par->color);
        sib->right->color=BLK_COLOR;
    }else{ //i am the right side child
        auto sib=par->left;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateRight(par);
                }else{
                    gpar->right=rotateRight(par);
                }
            }else{
                tree=rotateRight(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->left;

            //resolve now, par in the next case:
        }

        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->left)==BLK_COLOR){
            //need to fucking rotate
            par->left=rotateLeft(sib);
            par->left->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->left;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateRight(par);
            }else{
                gpar->right=rotateRight(par);
            }
        }else{
            tree=rotateRight(par);
        }

        swap(sib->color,par->color);
        sib->left->color=BLK_COLOR;
    }
}

总结

其实RB-tree的实现更多的是细节和分析case（细节卡了半天啊啊啊啊啊），非递归化本身难度并不高，特别是已经弄清楚AVL的分析情况下。

完整代码

#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std;
#define ll long long
#define pii pair<int, int>
#define qi ios::sync_with_stdio(0)

bool debug = true;

/*    *************************************
      * Written in Acer computer          *
      * The following code belongs to     *
      *    XGN from HellHoleStudios       *
      *************************************

    Current Problem Is:
*/
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> ptt)
{
    os << ptt.first << "," << ptt.second;
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> vt)
{
    os << "{";
    for (int i = 0; i < vt.size(); i++)
    {
        os << vt[i] << " ";
    }
    os << "}";
    return os;
}

#define BLK_COLOR 0
#define RED_COLOR 1
#define LEFT 0
#define RIGHT 1
#define Color(node) (node==NULL?BLK_COLOR:node->color)
#define Dir(par,node) (par->left==node?LEFT:RIGHT)

struct RBTNode
{
    int data;
    RBTNode *left;
    RBTNode *right;
    int color;

    RBTNode(int data):data(data),left(NULL),right(NULL),color(RED_COLOR){}
};

RBTNode* tree;

void directInsert(RBTNode* fa, RBTNode* son){
    if(fa->data<son->data){
        fa->right=son;
    }else{
        fa->left=son;
    }
}

RBTNode* rotateLeft(RBTNode* root){
    auto r=root->right;
    auto rl=r==NULL?NULL:root->right->left;
    root->right=rl;
    r->left=root;
    return r;
}

RBTNode* rotateRight(RBTNode* root){
    auto l=root->left;
    auto lr=l==NULL?NULL:root->left->right;
    root->left=lr;
    l->right=root;
    return l;
}

//Assume me is red, par is red
void rebalance(RBTNode* ggpar, RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(gpar==NULL){
        //par is root
        par->color=BLK_COLOR;
        return;
    }

    if(Dir(gpar,par)==LEFT){
        if(Dir(par,me)==RIGHT){
            gpar->left=rotateLeft(par);
            swap(par,me); //after rotation switched place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateRight(gpar);
            }else{
                ggpar->right=rotateRight(gpar);
            }
        }else{
            tree=rotateRight(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }else{
        if(Dir(par,me)==LEFT){
            gpar->right=rotateRight(par);
            swap(par,me); //after rotation swapped place
        }
        if(ggpar!=NULL){
            if(ggpar->left==gpar){
                ggpar->left=rotateLeft(gpar);
            }else{
                ggpar->right=rotateLeft(gpar);
            }
        }else{
            tree=rotateLeft(gpar);
        }
        par->color=BLK_COLOR;
        gpar->color=RED_COLOR;
    }
}

void insert(int x){
    auto node=new RBTNode(x);

    if(tree==NULL){
        tree=node;
        tree->color=BLK_COLOR;
        return;
    }

    RBTNode* now=tree;
    RBTNode* par=NULL;
    RBTNode* gpar=NULL;
    RBTNode* ggpar=NULL;

    while(true){

        //if can be push down then just push down
        if(now->color==BLK_COLOR && Color(now->left)==RED_COLOR && Color(now->right)==RED_COLOR){
            now->color=RED_COLOR;
            now->left->color=BLK_COLOR;
            now->right->color=BLK_COLOR;

            if(par==NULL){ //tree root
                now->color=BLK_COLOR;
            }else{ //rebalance
                if(par->color==RED_COLOR){
                    rebalance(ggpar,gpar,par,now);
                }
            }
        }

        if(now->data==x){
            //already in tree
            delete node;
            return;
        }
        if(now->data<x){
            //move to the right
            if(now->right==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->right;
        }else{
            //move to the left
            if(now->left==NULL){
                break;
            }
            ggpar=gpar;
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    directInsert(now,node);

    if(now->color==RED_COLOR){
        rebalance(gpar,par,now,node);
    }

    //ensure root node is black
    if(tree->color==RED_COLOR){
        tree->color=BLK_COLOR;
    }
}

//assume me is black
void rebalanceRemoval(RBTNode* gpar, RBTNode* par, RBTNode* me){
    if(par==NULL){
        return;
    }
    if(me==par->left){
        auto sib=par->right;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateLeft(par);
                }else{
                    gpar->right=rotateLeft(par);
                }
            }else{
                tree=rotateLeft(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->right;
            //resolve now, par in the next case:
        }

        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->right)==BLK_COLOR){
            //need to fucking rotate
            par->right=rotateRight(sib);
            par->right->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->right;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateLeft(par);
            }else{
                gpar->right=rotateLeft(par);
            }
        }else{
            tree=rotateLeft(par);
        }

        swap(sib->color,par->color);
        sib->right->color=BLK_COLOR;
    }else{
        auto sib=par->left;
        //case 1
        if(sib->color==RED_COLOR){
            if(gpar!=NULL){
                if(gpar->left==par){
                    gpar->left=rotateRight(par);
                }else{
                    gpar->right=rotateRight(par);
                }
            }else{
                tree=rotateRight(par);
            }

            sib->color=BLK_COLOR;
            par->color=RED_COLOR;
            gpar=sib;
            sib=par->left;

            //resolve now, par in the next case:
        }

        //case 2
        if(par->color==RED_COLOR && Color(sib->left)==BLK_COLOR && Color(sib->right)==BLK_COLOR){
            sib->color=RED_COLOR;
            par->color=BLK_COLOR;
            //no need to resolve
            return;
        }

        //three black situation --> case 3
        if(sib->color==BLK_COLOR && Color(sib->right)==BLK_COLOR && Color(sib->left)==BLK_COLOR){
            sib->color=RED_COLOR;
            return;
        }

        //case 4
        if(Color(sib->left)==BLK_COLOR){
            //need to fucking rotate
            par->left=rotateLeft(sib);
            par->left->color=BLK_COLOR;
            sib->color=RED_COLOR;
            sib=par->left;
        }

        //case 5
        if(gpar!=NULL){
            if(par==gpar->left){
                gpar->left=rotateRight(par);
            }else{
                gpar->right=rotateRight(par);
            }
        }else{
            tree=rotateRight(par);
        }

        swap(sib->color,par->color);
        sib->left->color=BLK_COLOR;
    }
}

void remove(int x){
    RBTNode* now=tree;
    RBTNode* par=NULL;

    RBTNode* nodeX=NULL; //the node containing X
    RBTNode* toDelete=NULL; //really gonna delete this
    RBTNode* toDelPar=NULL;

    RBTNode* parFirstNoShorter=NULL; //parent of first of no shorter
    RBTNode* firstNoShorter=NULL;

    //find node of value x
    while(now!=NULL){
        if(now->data==x){
            //found!
            nodeX=now;
            break;
        }
        if(now->data<x){
            //move to the right
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }else{
            //move to the left

            if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->left;
        }
    }

    if(nodeX==NULL){
        //did not find node
        return;
    }

    //find scapegoat
    if(nodeX->left==NULL){
        toDelPar=par;
        toDelete=nodeX;
    }else{
        if(Color(now->right)!=BLK_COLOR || (now->right!=NULL && (Color(now->right->left)!=BLK_COLOR || Color(now->right->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
            parFirstNoShorter=par;
            firstNoShorter=now;
        }
        par=nodeX;
        now=nodeX->left;
        while(now->right!=NULL){
            if(Color(now->left)!=BLK_COLOR || (now->left!=NULL && (Color(now->left->left)!=BLK_COLOR || Color(now->left->right)!=BLK_COLOR)) || Color(now)!=BLK_COLOR){
                parFirstNoShorter=par;
                firstNoShorter=now;
            }
            par=now;
            now=now->right;
        }
        toDelPar=par;
        toDelete=now;
    }

    //case 1 it's a leaf red
    if(toDelete->left==NULL && toDelete->right==NULL && toDelete->color==RED_COLOR){
        if(toDelete==par->left){
            par->left=NULL;
        }else{
            par->right=NULL;
        }
        nodeX->data=toDelete->data;
        delete toDelete;
        return;
    }

    //case 2 it has a child (must be red)
    if(toDelete->left!=NULL){
        toDelete->left->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->left;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->left;
            }else{
                par->right=toDelete->left;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }
    if(toDelete->right!=NULL){
        toDelete->right->color=BLK_COLOR;
        if(par==NULL){
            tree=toDelete->right;
        }else{
            if(toDelete==par->left){
                par->left=toDelete->right;
            }else{
                par->right=toDelete->right;
            }
        }

        nodeX->data=toDelete->data;
        return;
    }

    //tree gone
    if(toDelPar==NULL){
        tree=NULL;
        delete toDelete;
        return;
    }

    //balance
    RBTNode* gpar=parFirstNoShorter;
    par=firstNoShorter;
    if(firstNoShorter==NULL){
        now=tree;
    }else{
        if(firstNoShorter->data<toDelete->data){
            now=firstNoShorter->right;
        }else{
            now=firstNoShorter->left;
        }
    }

    while(now!=NULL){
        rebalanceRemoval(gpar,par,now);
        if(now->data<toDelete->data){
            gpar=par;
            par=now;
            now=now->right;
        }else{
            gpar=par;
            par=now;
            now=now->left;
        }
    }

    nodeX->data=toDelete->data;
    if(toDelete==toDelPar->left){
        toDelPar->left=NULL;
    }else{
        toDelPar->right=NULL;
    }
    delete toDelete;
}

bool checkColorConstraint(RBTNode *node)
{
    if (node == nullptr)
        return true;
    bool leftOK = checkColorConstraint(node->left);
    bool rightOK = checkColorConstraint(node->right);
    if (!leftOK || !rightOK)
        return false;
    if (node->color == BLK_COLOR)
        return true;
    else if (node->color == RED_COLOR)
    {
        if (node->left != nullptr && node->left->color == RED_COLOR)
        {
            cout << "COLOR problem: " << node->data << " left " << node->left->data;
            return false;
        }
        if (node->right != nullptr && node->right->color == RED_COLOR)
        {
            cout << "COLOR problem: " << node->data << " right " << node->right->data;
            return false;
        }
        return true;
    }
    else
        assert(0); // 颜色只能是red,black

    return true;
}

// 这个函数检查黑高度约束是否满足
int checkBlackHeightConstraint(RBTNode *node)
{
    if (node == 0)
        return 1;

    int lH = checkBlackHeightConstraint(node->left);
    int rH = checkBlackHeightConstraint(node->right);
    if (lH != rH || lH < 0)
    {
        cout << "BLACK HEIGHT problem: " << node->data << " left " << lH << " right " << rH << endl;
        return -1;
    }
    return lH + (node->color == BLK_COLOR ? 1 : 0);
}

bool CheckOrder(RBTNode *node, RBTNode *prevNode)
{
    if (node == nullptr)
        return true;

    if (prevNode != nullptr && prevNode->data >= node->data)
    {
        return false;
    }
    if (!CheckOrder(node->left, prevNode))
        return false;
    return CheckOrder(node->right, node);
}

bool checkRedBlackTree(RBTNode *rt)
{
    if (!checkColorConstraint(rt))
    {
        cout << "Color Constraint violated" << endl;
        return false;
    }

    if (checkBlackHeightConstraint(rt) < 0)
    {
        cout << "Black Height Constraint violated!" << endl;
        return false;
    }
    if (!CheckOrder(rt, nullptr))
    {
        cout << "Not a binary search tree";
        return false;
    }
    if (rt != nullptr && rt->color != BLK_COLOR)
    {
        cout << "The root is not black!" << endl;
        return false;
    }
    return true;
}

// 通过中序遍历，从小到大输出树中Key集合的代码
void midOrderPrint(RBTNode *rt)
{
    if (rt == nullptr)
        return;

    midOrderPrint(rt->left);
    cout << rt->data << " ";
    midOrderPrint(rt->right);
}

int main(int argc, char *argv[])
{
    freopen("in.txt","r",stdin);

    int n;
    // n=1000;
    cin>>n;
    for(int i=0;i<n;i++){
        int op,data;
        // op=rand()%2+1;
        // data=rand();
        // cout<<op<<" "<<data<<endl;
        cin>>op>>data;
        if(op==1){
            insert(data);
        }else{
            remove(data);
        }

        midOrderPrint(tree);
        cout<<endl;

        bool ok=checkRedBlackTree(tree);
        assert(ok);
        cout<<"OK"<<endl;
    }
    return 0;
}

版权声明：
作者：XGN
链接：https://blog.hellholestudios.top/archives/1589
来源：Hell Hole Studios Blog
文章版权归作者所有，未经允许请勿转载。

THE END

chinese oi xgn

二维码

一种基于维护高度的无递归、无栈、无parent指针的AVL树实现方式

< <上一篇

crimboi[22] 你什么拓扑?

下一篇>>

文章目录

关闭

发表评论

取消回复

共有 10 条评论

rumrumgib

Ggg太强啦！

2024-10-12 11:44 回复
1. The :P@rumrumgib
  
  rumrumgib太强啦！：P
  
  2024-10-12 17:15 回复
The :P

赞！

2024-10-12 17:07 回复
1. rumrumgib@The :P
  
  sorry太强啊
  
  2024-10-12 17:19 回复
rumrumgib

我是bigmurmur

2024-10-12 17:15 回复
1. rumrumgib@rumrumgib
  
  我也是bigmurmur
  
  2024-10-12 17:20 回复
  1. rumrumgib@rumrumgib
    
    我才是bigmurmur
    
    2024-10-12 17:24 回复
rumrumgib

I am bigmurmur.

2024-10-12 17:19 回复
bigmurmur

为什么我不能是bigmurmur

2024-10-12 17:26 回复
bigmurmur

正宗bigmurmur

2024-10-12 17:31 回复

搜索内容

一种无递归、无栈、无parent指针的红黑树实现

前言

基础结构

插入

删除

总结

完整代码

取消回复

共有 10 条评论

分类

其他操作