红黑树的各种操作

客官°小女子只卖身不卖艺 2022-06-18 10:58 149阅读 0赞

红黑树各种操作

// 红黑树各种操作.cpp : Defines the entry point for the console application.  
//

\#include "stdafx.h"  
\#include<iostream>  
using namespace std;  
enum MyColor\{red,black\};  
typedef int DType;

struct RBTree  
\{  
DType data;  
MyColor col;  
RBTree \*parent;  
RBTree \*left;  
RBTree \*right;  
\};  
//查询节点信息  
RBTree \* search(RBTree \* r,DType val)  
\{  
RBTree \*x = r;  
while(x!=NULL&&x->data!=val)  
\{  
if(x->data>val)  
x = x->left;  
else  
x = x->right;  
\}  
return x;  
\}  
//左旋转  
RBTree \* left\_rotate(RBTree \* r,RBTree \*x)  
\{  
RBTree \*y = x->right;  
x->right = y->left;  
if(y->left!=NULL)  
y->left->parent = x;  
y->parent = x->parent;  
if(x->parent==NULL)  
r=y;  
else if(x==x->parent->left)  
x->parent->left = y;  
else  
x->parent->right = y;  
y->left=x;  
x->parent = y;  
return r;  
\}  
//右旋转  
RBTree \* right\_rotate(RBTree\* r,RBTree \*x)  
\{  
RBTree \*y = x->left;  
x->left = y->right;  
if(y->right!=NULL)  
y->right->parent = x;  
y->parent = x->parent;  
if(x->parent==NULL)  
r=y;  
else if(x==x->parent->left)  
x->parent->left = y;  
else  
x->parent->right = y;  
y->right = x;  
x->parent = y;  
return r;  
\}  
//插入元素后，保持红黑性  
RBTree\* keep\_insert\_RBTree(RBTree \*r,RBTree \*s)  
\{  
while(s->parent->col==red)  
\{  
if(s->parent==s->parent->parent->left)  
\{  
RBTree \*y = s->parent->parent->right;  
if(y->col==red)  
\{  
y->col = black;  
s->parent->col = black;  
s->parent->parent->col=red;  
s = s->parent->parent;  
\}  
else  
\{  
if(s==s->parent->right)  
\{  
s = s->parent;  
r = left\_rotate(r,s);  
\}  
s->parent->col = black;  
s->parent->parent = red;  
r = right\_rotate(r,s->parent->parent);  
\}  
\}  
else  
\{  
RBTree \*y = s->parent->parent->left;  
if(y->col==red)  
\{  
y->col = black;  
s->parent->col = black;  
s->parent->parent->col = red;  
s = s->parent->parent;  
\}  
else  
\{  
if(s==s->parent->left)  
\{  
s = s->parent;  
r = right\_rotate(r,s);  
\}  
s->parent->col = black;  
s->parent->parent = red;  
r = left\_rotate(r,s->parent->parent);  
\}  
\}  
\}  
r->col = black;  
return r;  
\}  
//插入元素  
RBTree \*insert(RBTree \*r,RBTree \*s)  
\{  
RBTree \*p = search(r,s->data);  
if(P==NULL)  
\{  
RBTree \*y=NULL;  
RBTree \*x=r;  
while(x!=NULL)  
\{  
y = x;  
if(s->data<x->data)  
x = x->left;  
else  
x = x->right;  
\}  
s->parent = y;  
if(y==NULL)  
r = s;  
else if(s->data<y->data)  
y-left = s;  
else  
y->right = s;  
s->left = NULL;  
s->right = NULL;  
s->col = red;  
r = keep\_insert\_RBTree();  
\}  
return r;  
\}  
//取得最小值节点  
RBTree \* get\_min(RBTree \*r)  
\{  
RBTree \* s = r;  
while(s->left!=NULL)  
s = s->left;  
return s;  
\}  
//取得最大值节点  
RBTree \* get\_max(RBTree \*r)  
\{  
RBTree \*s = r;  
while(s->right!=NULL)  
s = s->right;  
return s;  
\}  
//取得中序前驱节点  
RBTree \* get\_processor(RBTree \*r,DType val)  
\{  
RBTree \*p = search(r,val);  
if(p==NULL)  
return NULL;  
else  
\{  
if(p->left != NULL)  
return get\_max(r);  
else  
\{  
RBTree \*q = p->parent;  
while(q!=NULL&&p==q->parent->left)  
\{  
p = q;  
q = p->parent;  
\}  
return q;  
\}  
\}  
\}  
//取得中序后继节点  
RBTree \* get\_successor(RBTree \*r,DType val)  
\{  
RBTree \*p = search(r,val);  
if(p==NULL)  
return NULL;  
else  
\{  
if(p->right != NULL)  
return get\_min(r);  
else  
\{  
RBTree \*q = p->parent;  
while(q != NULL&&p==q->right)  
\{  
p = q;  
q = p->parent;  
\}  
return q;  
\}  
\}  
\}  
//删除节点操作  
RBTree \*delete\_node(RBTree \*r,int val)  
\{  
RBTree \*p = search(r,val);  
RBTree \*y,\*x;  
if(p != NULL)  
\{  
if(p->left==NULL||p->right==NULL)  
y = p;  
else  
y = get\_successor(r,val);  
if(y->left != NULL)  
x = y->left;  
else  
x = y->right;  
if(x != NULL)  
x->parent = y->parent;  
if(y->parent == NULL)  
r = x;  
else if(y == x->parent->left)  
x->parent->left = x;  
else  
x->parent->right = x;  
if(y != p)  
\{  
p->data = y->data;  
\}  
if(y->col==black)  
r = keep\_delete\_RBTree(r,x);  
\}  
return r;  
\}  
//保持删除节点后，树的红黑性  
RBTree \*keep\_delete\_RBTree(RBTree \*r,RBTree \*s)  
\{  
while(s != r&&s->col==black)  
\{  
if(s==s->parent->left)  
\{  
RBTree \*w = s->parent->right;  
if(w->col==red)  
\{  
w->col = black;  
s->parent->col = red;  
lr = eft\_rotate(r,s->parent);  
w = s->parent->right;  
\}  
if(w->left->col==black&&w->right->col==black)  
\{  
w->col=red;  
s = s->parent;  
\}  
else if(w->right->col==black)  
\{  
w->left->col = black;  
w->col = red;  
r = right\_rotate(r,w);  
w = s->parent->right;  
\}  
else  
\{  
w->col = s->parent->col;  
s->parent->col = black;  
w->right->col = black;  
r = left\_rotate(r,s->parent);  
s = r;  
\}  
\}  
else  
\{  
same as the case of "left";  
\}  
\}

s->col = black;

return r;  
\}  
int \_tmain(int argc, \_TCHAR\* argv\[\])  
\{

......code.......  
return 0;  
\}