Difference between revisions of "Red Black Tree Insertion & Deletion"

 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
−
 
+
<metadesc>Red Black Tree Insertion & Deletion implementation in C/C++  </metadesc>
−
<syntaxhighlight lang="c">
+
<syntaxhighlight lang="c" name="redblacktree">
  
 
#include<stdio.h>
 
#include<stdio.h>
 
#include<stdlib.h>
 
#include<stdlib.h>
−
 
+
 
struct nod
 
struct nod
 
{
 
{
Line 14: Line 14:
 
};
 
};
 
typedef struct nod node;
 
typedef struct nod node;
−
void insertfix(node* z);
+
−
node* delet(node*);
+
void insertfix(node *z);
−
node* treesucc(node*);
+
node* delet(node *);
−
void deletefix(node*);
+
node* treesucc(node *);
 +
void deletefix(node *);
 
node* find(node *t,int);
 
node* find(node *t,int);
 
node *root,*nil;
 
node *root,*nil;
 
int preorder(node *t);
 
int preorder(node *t);
 +
int inorder(node *t);
 +
int x;
 +
 +
 
node* make()
 
node* make()
 
{
 
{
−
     node*a;
+
     node *a;
−
     a=(node*)malloc(sizeof(node));
+
     a = (node *)malloc(sizeof(node));
−
     a->left=nil;
+
     a->left = nil;
−
     a->right=nil;
+
     a->right = nil;
 
     return a;
 
     return a;
 
};
 
};
−
int inorder(node *t);
+
−
int x;
+
 +
 
int main()
 
int main()
 
{
 
{
 
     node *trav;
 
     node *trav;
−
     int n=0,*a,i;
+
     int n = 0,*a,i;
−
   
+
−
     nil=make();
+
     nil = make();
−
     nil->x=0;
+
     nil->x = 0;
−
     nil->color=1;
+
     nil->color = 1;
−
     root= make();
+
     root = make();
 
     printf("Enter the root: ");
 
     printf("Enter the root: ");
 
     scanf("%d",&root->x);
 
     scanf("%d",&root->x);
−
     root->p=nil;
+
     root->p = nil;
−
     root->color=1;
+
     root->color = 1;
 
     inorder(root);
 
     inorder(root);
 
     printf("Enter  numbers\n-1 to stop\n");
 
     printf("Enter  numbers\n-1 to stop\n");
Line 49: Line 55:
 
     {
 
     {
 
scanf("%d",&n);
 
scanf("%d",&n);
−
if(n==-1)
+
if(n == -1)
 
    break;
 
    break;
−
trav=root;
+
trav = root;
 
for(;;)
 
for(;;)
 
{
 
{
−
    if(n<trav->x&&trav->left!=nil)
+
    if(n < trav->x && trav->left != nil)
 
trav=trav->left;
 
trav=trav->left;
−
    if(n>trav->x&&trav->right!=nil)
+
    if(n > trav->x && trav->right != nil)
−
trav=trav->right;
+
trav = trav->right;
−
    if(n==trav->x)
+
    if(n == trav->x)
 
    {
 
    {
 
printf("\nThis is not insertable ");
 
printf("\nThis is not insertable ");
 
break;
 
break;
 
    }
 
    }
−
    if(trav->left==nil&&n<trav->x)
+
    if(trav->left == nil && n < trav->x)
 
    {
 
    {
−
trav->left=make();
+
trav->left = make();
−
trav->left->x=n;
+
trav->left->x = n;
−
trav->left->p=trav;
+
trav->left->p = trav;
−
trav->left->color=0;
+
trav->left->color = 0;
 
insertfix(trav->left);
 
insertfix(trav->left);
−
x=0;
+
x = 0;
 
inorder(root);
 
inorder(root);
 
break;
 
break;
 
    }
 
    }
−
    if(trav->right==nil&&n>trav->x)
+
    if(trav->right == nil && n > trav->x)
 
    {
 
    {
−
trav->right=make();
+
trav->right = make();
−
trav->right->x=n;
+
trav->right->x = n;
−
trav->right->p=trav;
+
trav->right->p = trav;
−
trav->right->color=0;
+
trav->right->color = 0;
 
insertfix(trav->right);
 
insertfix(trav->right);
−
x=0;
+
x = 0;
 
inorder(root);
 
inorder(root);
 
break;
 
break;
Line 91: Line 97:
 
     {
 
     {
 
scanf("%d",&n);
 
scanf("%d",&n);
−
if(n==0)
+
if(n == 0)
 
    break;
 
    break;
−
if((trav=find(root,n))!=nil)
+
if((trav=find(root,n)) != nil)
 
    delet(trav);
 
    delet(trav);
 
else
 
else
Line 100: Line 106:
 
    continue;
 
    continue;
 
}
 
}
−
x=0;
+
x = 0;
 
printf("Deleted!!!\n");
 
printf("Deleted!!!\n");
 
inorder(root);
 
inorder(root);
 
     }
 
     }
 
}
 
}
−
 
+
 
node* find(node *t,int x)
 
node* find(node *t,int x)
 
{
 
{
−
     int flag=1;
+
     int flag = 1;
 
     node *temp;
 
     node *temp;
−
     if(t!=nil)
+
     if(t != nil)
 
     {
 
     {
−
temp=find(t->left,x);
+
temp = find(t->left,x);
−
if(temp!=nil)
+
if(temp != nil)
 
    return temp;
 
    return temp;
−
if(t->x==x)      
+
if(t->x == x)      
 
    return t;
 
    return t;
−
temp=find(t->right,x);
+
temp = find(t->right,x);
−
if(temp!=nil)
+
if(temp != nil)
 
    return temp;
 
    return temp;
 
     }
 
     }
 
     return nil;
 
     return nil;
 
}
 
}
−
 
+
 
int inorder(node *t)
 
int inorder(node *t)
 
{
 
{
−
     if(t!=nil)
+
     if(t != nil)
 
     {
 
     {
 
inorder(t->left);
 
inorder(t->left);
Line 133: Line 139:
 
     }
 
     }
 
}
 
}
−
 
+
−
void leftrotate(node*x)
+
void leftrotate(node *x)
 
{
 
{
−
     node* y=x->right;
+
     node* y = x->right;
−
     x->right=y->left;
+
     x->right = y->left;
−
     y->left->p=x;
+
     y->left->p = x;
−
     y->p=x->p;
+
     y->p = x->p;
−
     if(x->p==nil)
+
     if(x->p == nil)
−
root=y;
+
root = y;
−
     else if(x==x->p->left)
+
     else if(x == x->p->left)
−
x->p->left=y;
+
x->p->left = y;
 
     else
 
     else
−
x->p->right=y;
+
x->p->right = y;
−
     y->left=x;
+
     y->left = x;
−
     x->p=y;
+
     x->p = y;
 
}
 
}
−
 
+
−
void rightrotate(node*x)
+
void rightrotate(node *x)
 
{
 
{
−
     node* y=x->left;
+
     node* y = x->left;
−
     x->left=y->right;
+
     x->left = y->right;
−
     y->right->p=x;
+
     y->right->p = x;
−
     y->p=x->p;
+
     y->p = x->p;
−
     if(x->p==nil)
+
     if(x->p == nil)
−
root=y;
+
root = y;
−
     else if(x==x->p->right)
+
     else if(x == x->p->right)
−
x->p->right=y;
+
x->p->right = y;
 
     else
 
     else
−
x->p->left=y;
+
x->p->left = y;
−
     y->right=x;
+
     y->right = x;
−
     x->p=y;
+
     x->p = y;
 
}
 
}
−
 
+
−
void insertfix(node* z)
+
void insertfix(node *z)
 
{
 
{
−
     node*y;
+
     node* y;
−
     while(z->p->color==0&&z!=nil)
+
     while(z->p->color == 0 && z != nil)
 
     {
 
     {
−
if(z->p==z->p->p->left)
+
if(z->p == z->p->p->left)
 
{
 
{
−
    y=z->p->p->right;
+
    y = z->p->p->right;
−
    if(y->color==0&&y!=nil)
+
    if(y->color == 0 && y != nil)
 
    {
 
    {
−
z->p->color=1;
+
z->p->color = 1;
−
y->color=1;
+
y->color = 1;
−
z->p->p->color=0;
+
z->p->p->color = 0;
−
z=z->p->p;
+
z = z->p->p;
 
    }
 
    }
 
    else
 
    else
 
    {
 
    {
−
if(z==z->p->right)
+
if(z == z->p->right)
 
{
 
{
−
    z=z->p;
+
    z = z->p;
 
    leftrotate(z);
 
    leftrotate(z);
 
}
 
}
−
if(z!=root&&z->p!=root)
+
if(z != root && z->p != root)
 
{
 
{
−
    z->p->color=1;
+
    z->p->color = 1;
−
    z->p->p->color=0;
+
    z->p->p->color = 0;
 
    rightrotate(z->p->p);
 
    rightrotate(z->p->p);
 
}
 
}
Line 198: Line 204:
 
else
 
else
 
{
 
{
−
    y=z->p->p->left;
+
    y = z->p->p->left;
−
    if(y->color==0)
+
    if(y->color == 0)
 
    {
 
    {
−
z->p->color=1;
+
z->p->color = 1;
−
y->color=1;
+
y->color = 1;
−
z->p->p->color=0;
+
z->p->p->color = 0;
−
z=z->p->p;
+
z = z->p->p;
 
    }
 
    }
 
    else
 
    else
 
    {
 
    {
−
if(z==z->p->left)
+
if(z == z->p->left)
 
{
 
{
−
    z=z->p;
+
    z = z->p;
 
    rightrotate(z);
 
    rightrotate(z);
 
}
 
}
−
if(z!=root&&z->p!=root)
+
if(z != root && z->p != root)
 
{
 
{
−
    z->p->color=1;
+
    z->p->color = 1;
−
    z->p->p->color=0;
+
    z->p->p->color = 0;
 
    leftrotate(z->p->p);
 
    leftrotate(z->p->p);
 
}
 
}
Line 222: Line 228:
 
}
 
}
 
     }
 
     }
−
     root->color=1;
+
     root->color = 1;
−
     nil->color=1;
+
     nil->color = 1;
 
}
 
}
−
 
+
−
node* delet(node*z)
+
node* delet(node *z)
 
{
 
{
−
     node*y,*x;
+
     node *y,*x;
−
       if(z->left==nil||z->right==nil)
+
       if(z->left == nil || z->right == nil)
−
y=z;
+
y = z;
 
     else
 
     else
−
y=treesucc(z);
+
y = treesucc(z);
−
     if(y->left!=nil||y->right!=nil)
+
     if(y->left != nil || y->right != nil)
 
     {
 
     {
−
if(y->left!=nil)
+
if(y->left != nil)
−
    x=y->left;
+
    x = y->left;
 
else
 
else
−
    x=y->right;
+
    x = y->right;
 
     }
 
     }
−
     else x=nil;
+
     else x = nil;
−
x->p=y->p;
+
x->p = y->p;
−
     if(y->p==nil)
+
     if(y->p == nil)
−
root=x;
+
root = x;
−
     else if(y==y->p->left)
+
     else if(y == y->p->left)
−
y->p->left=x;
+
y->p->left = x;
 
     else
 
     else
−
y->p->right=x;
+
y->p->right = x;
−
     if(y!=z)
+
     if(y != z)
−
z->x=y->x;
+
z->x = y->x;
−
     if(y->color==1&&x!=nil)
+
     if(y->color == 1 && x != nil)
 
deletefix(x);
 
deletefix(x);
 
     return y;
 
     return y;
 
}
 
}
−
 
+
 
node* treesucc(node *z)
 
node* treesucc(node *z)
 
{
 
{
−
     node *t=z->right;
+
     node *t = z->right;
−
     while(t->left!=nil)
+
     while(t->left != nil)
−
t=t->left;
+
t = t->left;
 
     return t;
 
     return t;
 
}
 
}
−
 
+
 
void deletefix(node *x)
 
void deletefix(node *x)
 
{
 
{
 
     node *w;
 
     node *w;
−
     while(x!=root&&x->color==1)
+
     while(x! = root && x->color == 1)
 
     {
 
     {
−
if(x==x->p->left)
+
if(x == x->p->left)
 
{     
 
{     
−
    w=x->p->right;
+
    w = x->p->right;
−
    if(w->color==0)
+
    if(w->color == 0)
 
    {
 
    {
−
w->color=1;
+
w->color = 1;
 
leftrotate(x->p);
 
leftrotate(x->p);
−
w=x->p->right;
+
w = x->p->right;
 
    }
 
    }
−
    if(w!=nil&&w->left->color==1&&w->right->color==1)
+
    if(w != nil && w->left->color == 1 && w->right->color == 1)
 
    {
 
    {
−
w->color=0;
+
w->color = 0;
−
x=x->p;
+
x = x->p;
 
    }
 
    }
 
    else
 
    else
 
    {
 
    {
−
if(w!=nil&&w->right->color==1)
+
if(w != nil && w->right->color == 1)
 
{
 
{
−
    w->left->color=1;
+
    w->left->color = 1;
−
    w->color=0;
+
    w->color = 0;
 
    rightrotate(w);
 
    rightrotate(w);
−
    w=x->p->right;
+
    w = x->p->right;
 
    inorder(root);
 
    inorder(root);
 
}
 
}
−
w->color=x->p->color;
+
w->color = x->p->color;
−
x->p->color=1;
+
x->p->color = 1;
−
if(w!=nil)
+
if(w != nil)
−
    w->right->color=1;
+
    w->right->color = 1;
 
leftrotate(x->p);
 
leftrotate(x->p);
−
x=root;
+
x = root;
 
    }
 
    }
 
}
 
}
 
else
 
else
 
{
 
{
−
    w=x->p->left;
+
    w = x->p->left;
−
    if(w->color==0)
+
    if(w->color == 0)
 
    {  
 
    {  
−
w->color=1;
+
w->color = 1;
 
rightrotate(x->p);
 
rightrotate(x->p);
−
w=x->p->left;
+
w = x->p->left;
 
    }
 
    }
−
    if(w!=nil&&w->right->color==1&&w->left->color==1)
+
    if(w != nil && w->right->color == 1 && w->left->color == 1)
 
    {
 
    {
−
w->color=0;
+
w->color = 0;
−
x=x->p;
+
x = x->p;
 
    }
 
    }
 
    else
 
    else
 
    {
 
    {
−
if(w!=nil&&w->left->color==1)
+
if(w != nil && w->left->color == 1)
 
{
 
{
−
    w->right->color=1;
+
    w->right->color = 1;
−
    w->color=0;
+
    w->color = 0;
 
    leftrotate(w);
 
    leftrotate(w);
−
    w=x->p->left;
+
    w = x->p->left;
 
}
 
}
−
w->color=x->p->color;
+
w->color = x->p->color;
−
x->p->color=1;
+
x->p->color = 1;
−
if(w!=nil)
+
if(w != nil)
−
    w->left->color=1;
+
    w->left->color = 1;
 
rightrotate(x->p);
 
rightrotate(x->p);
−
x=root;
+
x = root;
 
    }
 
    }
 
}
 
}
−
x->color=1;
+
x->color = 1;
 
     }
 
     }
 
}
 
}
 +
  
 
</syntaxhighlight>
 
</syntaxhighlight>
Line 339: Line 346:
  
  
−
{{Template:FB}}
+
{{Template:FBD}}
−
 
 
−
 
 
−
<disqus/>
 
  
  
  
 
[[Category:Trees]]
 
[[Category:Trees]]

Latest revision as of 16:41, 22 February 2014

<syntaxhighlight lang="c" name="redblacktree">

  1. include<stdio.h>
  2. include<stdlib.h>

struct nod { 

   int x;
   int color;
   struct nod *left;
   struct nod *p;
   struct nod *right;

}; typedef struct nod node;

void insertfix(node *z); node* delet(node *); node* treesucc(node *); void deletefix(node *); node* find(node *t,int); node *root,*nil; int preorder(node *t); int inorder(node *t); int x;


node* make() { 

   node *a;
   a = (node *)malloc(sizeof(node));
   a->left = nil;
   a->right = nil;
   return a;

};


int main() { 

   node *trav;
   int n = 0,*a,i;

   nil = make();
   nil->x = 0;
   nil->color = 1;
   root = make();
   printf("Enter the root: ");
   scanf("%d",&root->x);
   root->p = nil;
   root->color = 1;
   inorder(root);
   printf("Enter  numbers\n-1 to stop\n");
   for(;;)
   {

scanf("%d",&n); if(n == -1) break; trav = root; for(;;) { if(n < trav->x && trav->left != nil) trav=trav->left; if(n > trav->x && trav->right != nil) trav = trav->right; if(n == trav->x) { printf("\nThis is not insertable "); break; } if(trav->left == nil && n < trav->x) { trav->left = make(); trav->left->x = n; trav->left->p = trav; trav->left->color = 0; insertfix(trav->left); x = 0; inorder(root); break; } if(trav->right == nil && n > trav->x) { trav->right = make(); trav->right->x = n; trav->right->p = trav; trav->right->color = 0; insertfix(trav->right); x = 0; inorder(root); break; } } 

   }
   printf("Enter the numbers to delete: \n0 to stop: ");
   while(1)
   {

scanf("%d",&n); if(n == 0) break; if((trav=find(root,n)) != nil) delet(trav); else { printf("Entered element not in tree\n"); continue; } x = 0; printf("Deleted!!!\n"); inorder(root); 

   }

}

node* find(node *t,int x) { 

   int flag = 1;
   node *temp;
   if(t != nil)
   {

temp = find(t->left,x); if(temp != nil) return temp; if(t->x == x) return t; temp = find(t->right,x); if(temp != nil) return temp; 

   }
   return nil;

}

int inorder(node *t) { 

   if(t != nil)
   {

inorder(t->left); printf("%d \t",t->x); inorder(t->right); 

   }

}

void leftrotate(node *x) { 

   node* y = x->right;
   x->right = y->left;
   y->left->p = x;
   y->p = x->p;
   if(x->p == nil)

root = y; 

   else if(x == x->p->left)

x->p->left = y; 

   else

x->p->right = y; 

   y->left = x;
   x->p = y;

}

void rightrotate(node *x) { 

   node* y = x->left;
   x->left = y->right;
   y->right->p = x;
   y->p = x->p;
   if(x->p == nil)

root = y; 

   else if(x == x->p->right)

x->p->right = y; 

   else

x->p->left = y; 

   y->right = x;
   x->p = y;

}

void insertfix(node *z) { 

   node* y;
   while(z->p->color == 0 && z != nil)
   {

if(z->p == z->p->p->left) { y = z->p->p->right; if(y->color == 0 && y != nil) { z->p->color = 1; y->color = 1; z->p->p->color = 0; z = z->p->p; } else { if(z == z->p->right) { z = z->p; leftrotate(z); } if(z != root && z->p != root) { z->p->color = 1; z->p->p->color = 0; rightrotate(z->p->p); } } } else { y = z->p->p->left; if(y->color == 0) { z->p->color = 1; y->color = 1; z->p->p->color = 0; z = z->p->p; } else { if(z == z->p->left) { z = z->p; rightrotate(z); } if(z != root && z->p != root) { z->p->color = 1; z->p->p->color = 0; leftrotate(z->p->p); } } } 

   }
   root->color = 1;
   nil->color = 1;

}

node* delet(node *z) { 

   node *y,*x;
     if(z->left == nil || z->right == nil)

y = z; 

   else

y = treesucc(z); 

   if(y->left != nil || y->right != nil)
   {

if(y->left != nil) x = y->left; else x = y->right; 

   }
    else x = nil;

x->p = y->p; 

   if(y->p == nil)

root = x; 

   else if(y == y->p->left)

y->p->left = x; 

   else

y->p->right = x; 

   if(y != z)

z->x = y->x; 

   if(y->color == 1 && x != nil)

deletefix(x); 

   return y;

}

node* treesucc(node *z) { 

   node *t = z->right;
   while(t->left != nil)

t = t->left; 

   return t;

}

void deletefix(node *x) { 

   node *w;
   while(x! = root && x->color == 1)
   {

if(x == x->p->left) { w = x->p->right; if(w->color == 0) { w->color = 1; leftrotate(x->p); w = x->p->right; } if(w != nil && w->left->color == 1 && w->right->color == 1) { w->color = 0; x = x->p; } else { if(w != nil && w->right->color == 1) { w->left->color = 1; w->color = 0; rightrotate(w); w = x->p->right; inorder(root); } w->color = x->p->color; x->p->color = 1; if(w != nil) w->right->color = 1; leftrotate(x->p); x = root; } } else { w = x->p->left; if(w->color == 0) { w->color = 1; rightrotate(x->p); w = x->p->left; } if(w != nil && w->right->color == 1 && w->left->color == 1) { w->color = 0; x = x->p; } else { if(w != nil && w->left->color == 1) { w->right->color = 1; w->color = 0; leftrotate(w); w = x->p->left; } w->color = x->p->color; x->p->color = 1; if(w != nil) w->left->color = 1; rightrotate(x->p); x = root; } } x->color = 1; 

   }

}


</syntaxhighlight>





blog comments powered by Disqus
Retrieved from "https://gatecse.in/w/index.php?title=Red_Black_Tree_Insertion_%26_Deletion&oldid=2512"

<syntaxhighlight lang="c">

  1. include<stdio.h>
  2. include<stdlib.h>

struct nod { 

   int x;
   int color;
   struct nod *left;
   struct nod *p;
   struct nod *right;

}; typedef struct nod node; void insertfix(node* z); node* delet(node*); node* treesucc(node*); void deletefix(node*); node* find(node *t,int); node *root,*nil; int preorder(node *t); node* make() { 

   node*a;
   a=(node*)malloc(sizeof(node));
   a->left=nil;
   a->right=nil;
   return a;

}; int inorder(node *t); int x; int main() { 

   node *trav;
   int n=0,*a,i;
   
   nil=make();
   nil->x=0;
   nil->color=1;
   root= make();
   printf("Enter the root: ");
   scanf("%d",&root->x);
   root->p=nil;
   root->color=1;
   inorder(root);
   printf("Enter  numbers\n-1 to stop\n");
   for(;;)
   {

scanf("%d",&n); if(n==-1) break; trav=root; for(;;) { if(n<trav->x&&trav->left!=nil) trav=trav->left; if(n>trav->x&&trav->right!=nil) trav=trav->right; if(n==trav->x) { printf("\nThis is not insertable "); break; } if(trav->left==nil&&n<trav->x) { trav->left=make(); trav->left->x=n; trav->left->p=trav; trav->left->color=0; insertfix(trav->left); x=0; inorder(root); break; } if(trav->right==nil&&n>trav->x) { trav->right=make(); trav->right->x=n; trav->right->p=trav; trav->right->color=0; insertfix(trav->right); x=0; inorder(root); break; } } 

   }
   printf("Enter the numbers to delete: \n0 to stop: ");
   while(1)
   {

scanf("%d",&n); if(n==0) break; if((trav=find(root,n))!=nil) delet(trav); else { printf("Entered element not in tree\n"); continue; } x=0; printf("Deleted!!!\n"); inorder(root); 

   }

}

node* find(node *t,int x) { 

   int flag=1;
   node *temp;
   if(t!=nil)
   {

temp=find(t->left,x); if(temp!=nil) return temp; if(t->x==x) return t; temp=find(t->right,x); if(temp!=nil) return temp; 

   }
   return nil;

}

int inorder(node *t) { 

   if(t!=nil)
   {

inorder(t->left); printf("%d \t",t->x); inorder(t->right); 

   }

}

void leftrotate(node*x) { 

   node* y=x->right;
   x->right=y->left;
   y->left->p=x;
   y->p=x->p;
   if(x->p==nil)

root=y; 

   else if(x==x->p->left)

x->p->left=y; 

   else

x->p->right=y; 

   y->left=x;
   x->p=y;

}

void rightrotate(node*x) { 

   node* y=x->left;
   x->left=y->right;
   y->right->p=x;
   y->p=x->p;
   if(x->p==nil)

root=y; 

   else if(x==x->p->right)

x->p->right=y; 

   else

x->p->left=y; 

   y->right=x;
   x->p=y;

}

void insertfix(node* z) { 

   node*y;
   while(z->p->color==0&&z!=nil)
   {

if(z->p==z->p->p->left) { y=z->p->p->right; if(y->color==0&&y!=nil) { z->p->color=1; y->color=1; z->p->p->color=0; z=z->p->p; } else { if(z==z->p->right) { z=z->p; leftrotate(z); } if(z!=root&&z->p!=root) { z->p->color=1; z->p->p->color=0; rightrotate(z->p->p); } } } else { y=z->p->p->left; if(y->color==0) { z->p->color=1; y->color=1; z->p->p->color=0; z=z->p->p; } else { if(z==z->p->left) { z=z->p; rightrotate(z); } if(z!=root&&z->p!=root) { z->p->color=1; z->p->p->color=0; leftrotate(z->p->p); } } } 

   }
   root->color=1;
   nil->color=1;

}

node* delet(node*z) { 

   node*y,*x;
     if(z->left==nil||z->right==nil)

y=z; 

   else

y=treesucc(z); 

   if(y->left!=nil||y->right!=nil)
   {

if(y->left!=nil) x=y->left; else x=y->right; 

   }
    else x=nil;

x->p=y->p; 

   if(y->p==nil)

root=x; 

   else if(y==y->p->left)

y->p->left=x; 

   else

y->p->right=x; 

   if(y!=z)

z->x=y->x; 

   if(y->color==1&&x!=nil)

deletefix(x); 

   return y;

}

node* treesucc(node *z) { 

   node *t=z->right;
   while(t->left!=nil)

t=t->left; 

   return t;

}

void deletefix(node *x) { 

   node *w;
   while(x!=root&&x->color==1)
   {

if(x==x->p->left) { w=x->p->right; if(w->color==0) { w->color=1; leftrotate(x->p); w=x->p->right; } if(w!=nil&&w->left->color==1&&w->right->color==1) { w->color=0; x=x->p; } else { if(w!=nil&&w->right->color==1) { w->left->color=1; w->color=0; rightrotate(w); w=x->p->right; inorder(root); } w->color=x->p->color; x->p->color=1; if(w!=nil) w->right->color=1; leftrotate(x->p); x=root; } } else { w=x->p->left; if(w->color==0) { w->color=1; rightrotate(x->p); w=x->p->left; } if(w!=nil&&w->right->color==1&&w->left->color==1) { w->color=0; x=x->p; } else { if(w!=nil&&w->left->color==1) { w->right->color=1; w->color=0; leftrotate(w); w=x->p->left; } w->color=x->p->color; x->p->color=1; if(w!=nil) w->left->color=1; rightrotate(x->p); x=root; } } x->color=1; 

   }

}

</syntaxhighlight>






blog comments powered by Disqus