Here is the following code mentioned in the instructions:
class AVL {
Node root;
private class Node {
int data;
Node left, right;
int height;
private Node(int D, Node L, Node R, int H) {
data=D;
left=L;
right=R;
height=H; // user has to set height
} // of constructor Node
} //of Node
static private void UpdateHeight(Node T) {
if (T ==null) return;
else T.height = Math.max(HEIGHT(T.left),HEIGHT(T.right)) + 1;
} // UPdate Height
static private int HEIGHT(Node T) {
if (T== null ) return(-1);
else return (T.height);
}
// we need to more our right child up
static private Node LeftRotate(Node T) {
System.out.println(\"left rotate with data \" + T.data);
Node Tr;
Tr=T.right; // right child
T.right=Tr.left; // our right child IS NOW hhh
Tr.left=T; // move T down to the left
UpdateHeight(Tr.left); // update the height of T
UpdateHeight(Tr); // update hte height of the new root
return Tr;
} // of LeftRotate
// we move our immediate left node up.
// in doing so, we are now immediat right of our left child
static private Node RightRotate(Node T) {
Node Tl;
System.out.println(\"left rotate with data \" + T.data);
Tl=T.left; // left child
T.left=Tl.right; // our left child is now what our left was pointing to
Tl.right=T; // move T down to the right
UpdateHeight(Tl.right); // update the height of T
UpdateHeight(Tl); // update hte height of the new root
return Tl;
} // of RightRotate
public AVL() {
root=null;
} // of constructor AVL
// method to allow external entity to insert an element into the tree
public void insert(int D)
{
root=insert_internal(D, root);
} // of insert
private Node insert_internal(int D, Node T) {
if (T==null) return( new Node (D, null, null, 0));
if (T.data == D) return T; // the data is already in there
if ( D < T. data ) // go left
{ if (T.left == null)
{
T.left = insert_internal(D,null);
UpdateHeight(T);
}
else { //interior node
T.left = insert_internal(D, T.left);
}
} // of go left
else // D goes to the right
{ if (T.right == null)
{
T.right = insert_internal(D,null);
UpdateHeight(T);
}
else { //interior node
T.right = insert_internal(D, T.right);
}
} // of go right
// now we have to figure out if things are out of
// balance
int diff= HEIGHT(T.right) - HEIGHT(T.left);
System.out.println(\"difference is \" + diff + \" data is \" + T.data);
if ( Math.abs(diff) <= 1) // we are good to go at this level
{
UpdateHeight(T);
return(T);
}
// only if diff is bigger than 1
if ( diff > 1)// right leaning
{ // look at right child and figure out how it is leaning
} // of right leaning
else // left leaning
{ // look at left child to see how it is leaning
Node child = T.left;
int cdiff;
cdiff = HEIGHT(child.right) - HEIGHT(child.left);
System.out.println(\"cdiff is \" + cdiff);
if ( cdiff < 0 ) // left left lean
{ T=RightRotate(T); }
else
{
System.out.println(\"SHAUN\");
preorder_internal(T);
T.left = LeftRotate(T.left);
System.out.println(\"SHAUN\");
preorder_internal(T);
T=RightRotate(T);
}
} // of left leaning
// at this point we have rotated, so we need to update
// the height of our current tree
UpdateHeight(T);
return(T);
} // of insert_internal
public void preorder() {
System.out.println(\"preorder\");
preorder_internal(root);
} // of preorder
private void preorder_internal(Node T) {
if (T==null) return;
else { System.out.println(T.data + \" height \" + T.height);
preorder_internal(T.left);
preorder_internal(T.right);
return;
} // of else
} // or preorder_internal
}// of AVL
class avltester {
public static void main(String args[]) {
AVL T;
T=new AVL();
T.insert(5);
T.preorder();
T.insert(3);
T.preorder();
T.insert(4);
T.preorder();
} // of main
} // of avltester
class AVL {
Node root;
private class Node {
int data;
Node left, right;
int height;
private Node(int D, Node L, Node R, int H) {
data=D;
left=L;
right=R;
height=H; // user has to set height
} // of constructor Node
} //of Node
static private void UpdateHeight(Node T) {
if (T ==null) return;
else T.height = Math.max(HEIGHT(T.left),HEIGHT(T.right)) + 1;
} // UPdate Height
static private int HEIGHT(Node T) {
if (T== null ) return(-1);
else return (T.height);
}
// we need to more our right child up
static private Node LeftRotate(Node T) {
System.out.println(\"left rotate with data \" + T.data);
Node Tr;
Tr=T.right; // right child
T.right=Tr.left; // our right child IS NOW hhh
Tr.left=T; // move T down to the left
UpdateHeight(Tr.left); // update the height of T
UpdateHeight(Tr); // update hte height of the new root
return Tr;
} // of LeftRotate
// we move our immediate left node up.
// in doing so, we are now immediat right of our left child
static private Node RightRotate(Node T) {
Node Tl;
System.out.println(\"left rotate with data \" + T.data);
Tl=T.left; // left child
T.left=Tl.right; // our left child is now what our left was pointing to
Tl.right=T; // move T down to the right
UpdateHeight(Tl.right); // update the height of T
UpdateHeight(Tl); // update hte height of the new root
return Tl;
} // of RightRotate
public AVL() {
root=null;
} // of constructor AVL
// method to allow external entity to insert an element into the tree
public void insert(int D)
{
root=insert_internal(D, root);
} // of insert
private Node insert_internal(int D, Node T) {
if (T==null) return( new Node (D, null, null, 0));
if (T.data == D) return T; // the data is already in there
if ( D < T. data ) // go left
{ if (T.left == null)
{
T.left = insert_internal(D,null);
UpdateHeight(T);
}
else { //interior node
T.left = insert_internal(D, T.left);
}
} // of go left
else // D goes to the right
{ if (T.right == null)
{
T.right = insert_internal(D,null);
UpdateHeight(T);
}
else { //interior node
T.right = insert_internal(D, T.right);
}
} // of go right
// now we have to figure out if things are out of
// balance
int diff= HEIGHT(T.right) - HEIGHT(T.left);
System.out.println(\"difference is \" + diff + \" data is \" + T.data);
if ( Math.abs(diff) <= 1) // we are good to go at this level
{
UpdateHeight(T);
return(T);
}
// only if diff is bigger than 1
if ( diff > 1)// right leaning
{ // look at right child and figure out how it is leaning
} // of right leaning
else // left leaning
{ // look at left child to see how it is leaning
Node child = T.left;
int cdiff;
cdiff = HEIGHT(child.right) - HEIGHT(child.left);
System.out.println(\"cdiff is \" + cdiff);
if ( cdiff < 0 ) // left left lean
{ T=RightRotate(T); }
else
{
System.out.println(\"SHAUN\");
preorder_internal(T);
T.left = LeftRotate(T.left);
System.out.println(\"SHAUN\");
preorder_internal(T);
T=RightRotate(T);
}
} // of left leaning
// at this point we have rotated, so we need to update
// the height of our current tree
UpdateHeight(T);
return(T);
} // of insert_internal
public void preorder() {
System.out.println(\"preorder\");
preorder_internal(root);
} // of preorder
private void preorder_internal(Node T) {
if (T==null) return;
else { System.out.println(T.data + \" height \" + T.height);
preorder_internal(T.left);
preorder_internal(T.right);
return;
} // of else
} // or preorder_internal
}// of AVL
class avltester {
public static void main(String args[]) {
AVL T;
T=new AVL();
T.insert(5);
T.preorder();
T.insert(3);
T.preorder();
T.insert(4);
T.preorder();
} // of main
} // of avltester
#include<stdio.h>
#include<malloc.h>
#define CHANGED 0
#define BALANCED 1
int height;
struct bnode
{
int data,bfactor;
struct bnode *left,*right;
};
typedef struct bnode node;
node* getnode()
{
int size;
node* newnode;
size=sizeof(node);
newnode=(node*)malloc(size);
return(newnode);
}
void copynode(node *r,int data)
{
r->data=data;
r->left=NULL;
r->right=NULL;
r->bfactor=0;
}
void releasenode(node *p)
{
free(p);
}
node* searchnode(node *root,int data)
{
if(root!=NULL)
if(data<root->data)
root=searchnode(root->left,data);
else if(data>root->data)
root=searchnode(root->right,data);
return(root);
}
void lefttoleft(node **Pptr,node **Aptr)
{
node *p=*Pptr,*A=*Aptr;
printf(\"\ Left to left AVL Rotation\ \");
p->left=A->right;
A->right=p;
if(A->bfactor==0)
{
p->bfactor=1;
A->bfactor=-1;
height=BALANCED;
}
else
{
p->bfactor=0;
A->bfactor=0;
}
p=A;
*Pptr=p;
*Aptr=A;
}
void lefttoright(node **Pptr,node **Aptr, node **Bptr)
{
node *p=*Pptr, *A=*Aptr, *B=*Bptr;
printf(\"\ Left to Right AVL Rotation \ \");
B=A->right;
A->right=B->left;
B->left=A;
p->left=B->right;
B->right=p;
if(B->bfactor==1)
p->bfactor=-1;
else
p->bfactor=0;
if(B->bfactor==-1)
A->bfactor=1;
else
A->bfactor=0;
B->bfactor=0;
p=B;
*Pptr=p;
*Aptr=A;
*Bptr=B;
}
void righttoright(node **Pptr, node **Aptr)
{
node *p=*Pptr, *A=*Aptr;
printf(\"\ Right to Right AVL Rotation \ \");
p->right=A->left;
A->left=p;
if(A->bfactor==0)
{
p->bfactor=-1;
A->bfactor=1;
height=BALANCED;
}
else
{
p->bfactor=0;
A->bfactor=0;
}
p=A;
*Pptr=p;
*Aptr=A;
}
void righttoleft(node **Pptr, node **Aptr, node **Bptr)
{
node *p=*Pptr, *A=*Aptr, *B=*Bptr;
printf(\"\ Right to Left AVL Rotation \ \");
B=A->left;
A->left=B->right;
B->right=A;
p->right=B->left;
B->left=p;
if(B->bfactor==-1)
p->bfactor=1;
else
p->bfactor=0;
if(B->bfactor==1)
A->bfactor=-1;
else
A->bfactor=0;
B->bfactor=0;
p=B;
*Pptr=p;
*Aptr=A;
*Bptr=B;
}
node* insertnode(int data,node* p)
{
node *A,*B;
if(p==NULL)
{
p=getnode();
copynode(p,data);
height=CHANGED;
return(p);
}
if(data<p->data)
{
p->left=insertnode(data,p->left);
if(height==CHANGED)
{
switch(p->bfactor)
{
case -1:
p->bfactor=0; //right heavy tree
height=BALANCED;
break;
case 0:
p->bfactor=1; //balanced tree
break;
case 1:
A=p->left;
if(A->bfactor==1)
lefttoleft(&p,&A);
else
lefttoright(&p,&A,&B);
height=BALANCED;
break;
}
}
}
if(data>p->data)
{
p->right=insertnode(data,p->right);
if(height==CHANGED)
{
switch(p->bfactor)
{
case 1:
p->bfactor=0; //left heavy trees
height=BALANCED;
break;
case 0:
p->bfactor=-1; //balanaced trees
break;
case -1:
A=p->right; //right heavy trees
if(A->bfactor==-1)
righttoright(&p,&A);
else
righttoleft(&p,&A,&B);
height=CHANGED;
break;
}
}
}
return(p);
}
void del(node **N,node **C)
{
node *T,*A,*B;
node **p;
T=(*N);
if((*N)->right!=NULL)
{
del(&((*N)->right),C);
if(height==CHANGED)
{
p=N;
switch((*p)->bfactor)
{
case -1:
(*p)->bfactor=0;
break;
case 0:
(*p)->bfactor=1;
height=BALANCED;
break;
case 1:
A=(*p)->left;
if(A->bfactor>=0)
lefttoleft(p,&A);
else
lefttoright(p,&A,&B);
break;
}
}
}
else
{
(*C)->data=(*N)->data;
(*N)=(*N)->left;
releasenode(T);
height=CHANGED;
}
}
void deletenode(int data,node **p)
{
node *A,*B,*C;
if(*p==NULL)
{
printf(\"\ AVL Tree is empty\");
return;
}
if(data<(*p)->data)
{
deletenode(data,&((*p)->left));
if(height==CHANGED)
{
switch((*p)->bfactor)
{
case 1:
(*p)->bfactor=0;
break;
case 0:
(*p)->bfactor=1;
height=BALANCED;
break;
case -1:
A=(*p)->right;
if(A->bfactor<=0)
righttoright(p,&A);
else
righttoleft(p,&A,&B);
break;
}
}
}
else if(data>(*p)->data)
{
deletenode(data,&((*p)->right));
if(height==CHANGED)
{
switch((*p)->bfactor)
{
case -1:
(*p)->bfactor=0;
break;
case 0:
(*p)->bfactor=1;
height=BALANCED;
break;
case 1:
A=(*p)->left;
if(A->bfactor>=0)
lefttoleft(p,&A);
else
lefttoright(p,&A,&B);
break;
}
}
}
else
{
C=*p;
if(C->right==NULL)
{
*p=C->left;
height=CHANGED;
releasenode(C);
}
else if(C->left==NULL)
{
*p=C->right;
height=CHANGED;
releasenode(C);
}
else
{
del(&(C->left),&C);
if(height==CHANGED)
{
switch((*p)->bfactor)
{
case 1:
(*p)->bfactor=0;
break;
case 0:
(*p)->bfactor=-1;
height=BALANCED;
break;
case -1:
A=(*p)->right;
if(A->bfactor<=0)
righttoright(p,&A);
else
righttoleft(p,&A,&B);
break;
}
}
}
}
}
void inorder(node *root)
{
if(root==NULL)
return;
inorder(root->left);
printf(\"%4d\",root->data);
inorder(root->right);
}
void main()
{
int data,ch,choice=\'y\';
node *root=NULL;
printf(\"\ Basic operations in an AVL Tree...\");
printf(\"\ 1.Insert a node in the AVL Tree\");
printf(\"\ 2.Delete a node in the AVL Tree\");
printf(\"\ 3.View the AVL Tree\");
printf(\"\ 4.Exit\");
while((choice==\'y\')||(choice==\'Y\'))
{
printf(\"\ \");
fflush(stdin);
scanf(\"%d\",&ch);
switch(ch)
{
case 1:
printf(\"\ Enter the value to be inserted:\");
scanf(\"%d\",&data);
if(searchnode(root,data)==NULL)
root=insertnode(data,root);
else
printf(\"\ Data already exists\");
break;
case 2:
printf(\"Enter the value to be deleted:\");
scanf(\"%d\",&data);
if(searchnode(root,data)!=NULL)
deletenode(data,&root);
else
printf(\"\ Element to be deleted is not found\");
break;
case 3:
if(root==NULL)
{
printf(\"\ AVL Tree is Emoty\ \");
continue;
}
printf(\"\ Inorder Traversal of the AVL Tree:\");
inorder(root);
break;
default:
printf(\"\ End of run of your program...\");
releasenode(root);
return;
}
}
}
OUTPUT:
Basic operations in an AVL Tree...
1.Insert a node in the AVL Tree
2.Delete a node in the AVL Tree
3.View the AVL Tree
4.Exit
1
Enter the value to be inserted:23
1
Enter the value to be inserted:15
3
Inorder Traversal of the AVL Tree: 15 23
Enter the value to be inserted:13
Left to left AVL Rotation
3
Inorder Traversal of the AVL Tree: 13 15 23
Enter the value to be inserted:27
1
Enter the value to be inserted:20
1
Enter the value to be inserted:18
Right to Left AVL Rotation
Enter the value to be inserted:32
Right to Right AVL Rotation
3
Inorder Traversal of the AVL Tree: 13 15 18 20 23 27 32
Enter the value to be inserted:9
1
Enter the value to be inserted:12
Left to Right AVL Rotation
3
Inorder Traversal of the AVL Tree: 9 12 13 15 18 20 23 27 32
Homework Sourse
