Here is the following code mentioned in the instructions: class AVL { Node root;
ID: 3940416 • Letter: H
Question
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
Explanation / Answer
#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