Scribd
Upload
1 views25 pages

DS Lab(Week-7)

The document contains C programs for implementing AVL and Red-Black trees, including functionalities for insertion, deletion, and searching. The AVL tree implementation features balancing through rotations, while the Red-Black tree ensures properties like color balancing during insertions and deletions. Both implementations include a main function for user interaction to manipulate the trees.

Uploaded by

Sujith Reddy Diguvapati
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views25 pages

DS Lab(Week-7)

The document contains C programs for implementing AVL and Red-Black trees, including functionalities for insertion, deletion, and searching. The AVL tree implementation features balancing through rotations, while the Red-Black tree ensures properties like color balancing during insertions and deletions. Both implementations include a main function for user interaction to manipulate the trees.

Uploaded by

Sujith Reddy Diguvapati
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Write a C program to implement AVL tree (Insertion,

Deletion, Search).
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *left;
struct node *right;
int height;
};
int height(struct node *n)
{
if(n==NULL)
return 0;
return n->height;
}
int max(int a,int b)
{
return (a>b)?a:b;
}
struct node* create(int key)
{
struct node *newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=key;
newnode->left=NULL;
newnode->right=NULL;
newnode->height=1;
return newnode;
}
struct node* rightRotate(struct node *y)
{
struct node *x=y->left;
struct node *T2=x->right;
x->right=y;
y->left=T2;
y->height=max(height(y->left),height(y->right))+1;
x->height=max(height(x->left),height(x->right))+1;
return x;
}
struct node* leftRotate(struct node *x)
{
struct node *y=x->right;
struct node *T2=y->left;
y->left=x;
x->right=T2;
x->height=max(height(x->left),height(x->right))+1;
y->height=max(height(y->left),height(y->right))+1;
return y;
}
int getBalance(struct node *n)
{
if(n==NULL)
return 0;
return height(n->left)-height(n->right);
}
struct node* insert(struct node *node,int key)
{
if(node==NULL)
return create(key);
if(key < node->data)
node->left=insert(node->left,key);
else if(key > node->data)
node->right=insert(node->right,key);
else
return node;
node->height=1+max(height(node->left),height(node->right));
int balance=getBalance(node);
// LL
if(balance>1 && key < node->left->data)
return rightRotate(node);
// RR
if(balance<-1 && key > node->right->data)
return leftRotate(node);
// LR
if(balance>1 && key > node->left->data)
{
node->left=leftRotate(node->left);
return rightRotate(node);
}
// RL
if(balance<-1 && key < node->right->data)
{
node->right=rightRotate(node->right);
return leftRotate(node);
}
return node;
}
struct node* minValue(struct node *node)
{
struct node *current=node;
while(current->left!=NULL)
current=current->left;
return current;
}
struct node* deleteNode(struct node *root,int key)
{
if(root==NULL)
return root;
if(key < root->data)
root->left=deleteNode(root->left,key);
else if(key > root->data)
root->right=deleteNode(root->right,key);
else
{
if((root->left==NULL)||(root->right==NULL))
{
struct node *temp=root->left?root->left:root->right;
if(temp==NULL)
{
temp=root;
root=NULL;
}
else
*root=*temp;
free(temp);
}
else
{
struct node *temp=minValue(root->right);
root->data=temp->data;
root->right=deleteNode(root->right,temp->data);
}
}
if(root==NULL)
return root;
root->height=1+max(height(root->left),height(root->right));
int balance=getBalance(root);
// LL
if(balance>1 && getBalance(root->left)>=0)
return rightRotate(root);
// LR
if(balance>1 && getBalance(root->left)<0)
{
root->left=leftRotate(root->left);
return rightRotate(root);
}
// RR
if(balance<-1 && getBalance(root->right)<=0)
return leftRotate(root);
// RL
if(balance<-1 && getBalance(root->right)>0)
{
root->right=rightRotate(root->right);
return leftRotate(root);
}
return root;
}
void search(struct node *root,int key)
{
if(root==NULL)
{
printf("Element not found\n");
return;
}
if(key==root->data)
printf("Element found\n");
else if(key < root->data)
search(root->left,key);
else
search(root->right,key);
}
void inorder(struct node *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);
}
}
int main()
{
struct node *root=NULL;
int choice,val;
while(1)
{
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\[Link](Inorder)");
printf("\[Link]");
printf("\nEnter choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter value: ");
scanf("%d",&val);
root=insert(root,val);
break;
case 2:
printf("Enter value to delete: ");
scanf("%d",&val);
root=deleteNode(root,val);
break;
case 3:
printf("Enter value to search: ");
scanf("%d",&val);
search(root,val);
break;
case 4:
printf("Inorder Traversal: ");
inorder(root);
break;
case 5:
exit(0);
}
}
}
Write a C program to implement Red - Black tree (Insertion,
Deletion, Search).
#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
int color; // 1 = Red, 0 = Black
struct node *left,*right,*parent;
};

struct node *root;


struct node *TNULL;

/* Create Node */
struct node* createNode(int key)
{
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=key;
temp->color=1;
temp->left=TNULL;
temp->right=TNULL;
temp->parent=NULL;
return temp;
}
/* Left Rotation */
void leftRotate(struct node *x)
{
struct node *y=x->right;
x->right=y->left;

if(y->left!=TNULL)
y->left->parent=x;

y->parent=x->parent;

if(x->parent==NULL)
root=y;
else if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;

y->left=x;
x->parent=y;
}

/* Right Rotation */
void rightRotate(struct node *x)
{
struct node *y=x->left;
x->left=y->right;

if(y->right!=TNULL)
y->right->parent=x;

y->parent=x->parent;

if(x->parent==NULL)
root=y;
else if(x==x->parent->right)
x->parent->right=y;
else
x->parent->left=y;

y->right=x;
x->parent=y;
}

/* Fix Insertion */
void fixInsert(struct node *k)
{
struct node *u;

while(k->parent->color==1)
{
if(k->parent==k->parent->parent->right)
{
u=k->parent->parent->left;

if(u->color==1)
{
u->color=0;
k->parent->color=0;
k->parent->parent->color=1;
k=k->parent->parent;
}
else
{
if(k==k->parent->left)
{
k=k->parent;
rightRotate(k);
}

k->parent->color=0;
k->parent->parent->color=1;
leftRotate(k->parent->parent);
}
}
else
{
u=k->parent->parent->right;

if(u->color==1)
{
u->color=0;
k->parent->color=0;
k->parent->parent->color=1;
k=k->parent->parent;
}
else
{
if(k==k->parent->right)
{
k=k->parent;
leftRotate(k);
}

k->parent->color=0;
k->parent->parent->color=1;
rightRotate(k->parent->parent);
}
}

if(k==root)
break;
}
root->color=0;
}

/* Insert Node */
void insert(int key)
{
struct node *node=createNode(key);
struct node *y=NULL;
struct node *x=root;

while(x!=TNULL)
{
y=x;
if(node->data<x->data)
x=x->left;
else
x=x->right;
}

node->parent=y;

if(y==NULL)
root=node;
else if(node->data<y->data)
y->left=node;
else
y->right=node;

if(node->parent==NULL)
{
node->color=0;
return;
}

if(node->parent->parent==NULL)
return;

fixInsert(node);
}

/* Search */
struct node* search(struct node *node,int key)
{
if(node==TNULL || key==node->data)
return node;

if(key<node->data)
return search(node->left,key);

return search(node->right,key);
}
/* Minimum Node */
struct node* minimum(struct node *node)
{
while(node->left!=TNULL)
node=node->left;

return node;
}

/* Replace Nodes */
void rbTransplant(struct node *u,struct node *v)
{
if(u->parent==NULL)
root=v;
else if(u==u->parent->left)
u->parent->left=v;
else
u->parent->right=v;

v->parent=u->parent;
}

/* Fix Deletion */
void fixDelete(struct node *x)
{
struct node *s;

while(x!=root && x->color==0)


{
if(x==x->parent->left)
{
s=x->parent->right;

if(s->color==1)
{
s->color=0;
x->parent->color=1;
leftRotate(x->parent);
s=x->parent->right;
}

if(s->left->color==0 && s->right->color==0)


{
s->color=1;
x=x->parent;
}
else
{
if(s->right->color==0)
{
s->left->color=0;
s->color=1;
rightRotate(s);
s=x->parent->right;
}

s->color=x->parent->color;
x->parent->color=0;
s->right->color=0;
leftRotate(x->parent);
x=root;
}
}
else
{
s=x->parent->left;

if(s->color==1)
{
s->color=0;
x->parent->color=1;
rightRotate(x->parent);
s=x->parent->left;
}

if(s->left->color==0 && s->right->color==0)


{
s->color=1;
x=x->parent;
}
else
{
if(s->left->color==0)
{
s->right->color=0;
s->color=1;
leftRotate(s);
s=x->parent->left;
}

s->color=x->parent->color;
x->parent->color=0;
s->left->color=0;
rightRotate(x->parent);
x=root;
}
}
}

x->color=0;
}

/* Delete Node */
void deleteNode(int key)
{
struct node *z=search(root,key);
struct node *x,*y=z;
int y_original_color=y->color;

if(z==TNULL)
{
printf("Element not found\n");
return;
}

if(z->left==TNULL)
{
x=z->right;
rbTransplant(z,z->right);
}
else if(z->right==TNULL)
{
x=z->left;
rbTransplant(z,z->left);
}
else
{
y=minimum(z->right);
y_original_color=y->color;
x=y->right;

if(y->parent==z)
x->parent=y;
else
{
rbTransplant(y,y->right);
y->right=z->right;
y->right->parent=y;
}

rbTransplant(z,y);
y->left=z->left;
y->left->parent=y;
y->color=z->color;
}

if(y_original_color==0)
fixDelete(x);
}

/* Display Tree */
void display(struct node *root,int space)
{
int i;
if(root==TNULL)
return;

space+=10;

display(root->right,space);

printf("\n");
for(i=10;i<space;i++)
printf(" ");

if(root->color==1)
printf("%d(R)\n",root->data);
else
printf("%d(B)\n",root->data);

display(root->left,space);
}

/* Main Function */
int main()
{
int ch,val;

TNULL=(struct node*)malloc(sizeof(struct node));


TNULL->color=0;
TNULL->left=NULL;
TNULL->right=NULL;

root=TNULL;

while(1)
{
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\nEnter choice: ");
scanf("%d",&ch);

switch(ch)
{
case 1:
printf("Enter element: ");
scanf("%d",&val);
insert(val);
break;

case 2:
printf("Enter element to delete: ");
scanf("%d",&val);
deleteNode(val);
break;

case 3:
printf("Enter element to search: ");
scanf("%d",&val);

if(search(root,val)!=TNULL)
printf("Element Found\n");
else
printf("Element Not Found\n");
break;

case 4:
printf("\nRed Black Tree Structure:\n");
display(root,0);
break;

case 5:
exit(0);
}
}
}

You might also like