Scribd
Upload
7 views11 pages

C Program for AVL Tree Implementation

The document describes a C program to implement an AVL tree. It includes functions to insert nodes, rotate the tree for balance, calculate height, and print the tree in preorder and inorder traversal. Node insertion causes rebalancing using single, double left and right rotations. Balance factor is calculated as height of left subtree - height of right subtree.

Uploaded by

Gitika Suma Attaluri
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7 views11 pages

C Program for AVL Tree Implementation

The document describes a C program to implement an AVL tree. It includes functions to insert nodes, rotate the tree for balance, calculate height, and print the tree in preorder and inorder traversal. Node insertion causes rebalancing using single, double left and right rotations. Balance factor is calculated as height of left subtree - height of right subtree.

Uploaded by

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

DEPARTMENT OF CSE

Name of the Student [Link] VIVEK


Roll Number 18R21A05D4
Name of the Lab DATA STRUCTURES LAB
Week No WEEK - 13

PROBLEM STATEMENT:
Write a C program of AVL tree
PROGRAM:
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *left,*right;
int ht;
}node;
node *insert(node *,int);
void preorder(node *);
void inorder(node *);
int height( node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
int main()
{
node *root=NULL;
int x,n,i,op;
do
{
printf("1)Create:\n");
printf("2)Insert:\n");
printf("3)Print:\n");
printf("4)Quit:\n");
printf("Enter Your Choice:\n");
scanf("%d",&op);

switch(op)
DEPARTMENT OF CSE
{
case 1: printf("Enter no. of elements:\n");
scanf("%d",&n);
printf("Enter tree data:\n");
root=NULL;
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
break;

case 2: printf("Enter a data:\n");


scanf("%d",&x);
root=insert(root,x);
break;

case 3: printf("Preorder sequence:\n");


preorder(root);
printf("\n");
printf("Inorder sequence:\n");
inorder(root);
printf("\n");
break;
}
}while(op!=4);

return 0;
}
node * insert(node *T,int x)
{
if(T==NULL)
{
T=(node*)malloc(sizeof(node));
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
if(x > T->data)
{
T->right=insert(T->right,x);
if(BF(T)==-2)
if(x>T->right->data)
T=RR(T);
DEPARTMENT OF CSE
else
T=RL(T);
}
else
if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
if(x < T->left->data)
T=LL(T);
else
T=LR(T);
}

T->ht=height(T);

return(T);
}
int height(node *T)
{
int lh,rh;
if(T==NULL)
return(0);

if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;

if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;

if(lh>rh)
return(lh);

return(rh);
}

node * rotateright(node *x)


{
node *y;
y=x->left;
x->left=y->right;
DEPARTMENT OF CSE
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}

node * rotateleft(node *x)


{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);

return(y);
}

node * RR(node *T)


{
T=rotateleft(T);
return(T);
}

node * LL(node *T)


{
T=rotateright(T);
return(T);
}

node * LR(node *T)


{
T->left=rotateleft(T->left);
T=rotateright(T);

return(T);
}

node * RL(node *T)


{
T->right=rotateright(T->right);
T=rotateleft(T);
return(T);
}
DEPARTMENT OF CSE
int BF(node *T)
{
int lh,rh;
if(T==NULL)
return(0);

if(T->left==NULL)
lh=0;
else
lh=1+T->left->ht;

if(T->right==NULL)
rh=0;
else
rh=1+T->right->ht;

return(lh-rh);
}

void preorder(node *T)


{
if(T!=NULL)
{
printf("%d(Bf=%d)",T->data,BF(T));
preorder(T->left);
preorder(T->right);
}
}

void inorder(node *T)


{
if(T!=NULL)
{
inorder(T->left);
printf("%d(Bf=%d)",T->data,BF(T));
inorder(T->right);
}
}
DEPARTMENT OF CSE
TEST CASE 1

TEST CASE 2
DEPARTMENT OF CSE
2 BINARY SEARCH TREE

PROGRAM:

#include <stdio.h>

#include<string.h>

#include <stdlib.h>

struct BST

char data;

struct BST *left,*right;

}node;

struct BST* root=NULL,*temp,*cur;

void create()

char c[10];

temp=root;

cur=(struct BST*)malloc(sizeof(struct BST));

printf("\n enter character:\n");

fflush(stdin);

scanf("%s",c);

cur->data=c[0];

cur->left=NULL;

cur->right=NULL;

if(temp==NULL)
DEPARTMENT OF CSE
root=cur;

else

while(temp!=NULL)

if((cur->data)<(temp->data))

if(temp->left==NULL)

temp->left=cur;

return;

else

temp=temp->left;

else

if(temp->right==NULL)

temp->right=cur;

return;

else
DEPARTMENT OF CSE
temp=temp->right;

}//else

}//while

}//else

}//create

void postorder(struct BST *temp)

if(temp!=NULL)

postorder(temp->left);

postorder(temp->right);

printf("\t%c",temp->data);

int main()

int ch;

printf("\nmenu options\n");

printf("[Link]\[Link]\[Link]\n");

while(1)

printf("enter ur choice");

scanf("%d",&ch);
DEPARTMENT OF CSE
switch(ch)

case 1:create();

break;

case 2:printf("Postorder Traversal\n");

postorder(root);

break;

case 3:exit(0);

default:printf("invalid choice\n");

}//switch

}//while

}//main

TEST CASE 1

TEST CASE 2
DEPARTMENT OF CSE

TEST CASE 3

Common questions

Powered by AI

The program's method for inputting characters into the binary search tree ensures correctness by using character comparison during insertion. Each new character is compared with existing nodes to determine its proper position in the tree, either as a left or right child. The `create` function repetitively traverses from the root towards the appropriate leaf spot where the new node should be placed, thereby maintaining the BST ordering property without regard to input variation .

In the AVL tree, rotations are a crucial element to maintaining balance and are specifically implemented as functions for right, left, left-right, and right-left rotations, each triggered when balances are detected via height checks after insertion. Conversely, the given binary search tree program lacks rotation mechanisms; it solely relies on the insertion of new nodes based on binary search properties without attempting any tree restructuring for balance maintenance. Thus, the AVL tree's rotations actively prevent skewing, while the BST may develop imbalances over time .

After each insertion or rotation in the AVL tree, the function calls the `height` function to update the height of the nodes involved. This function recalculates the height of a node based on the heights of its left and right subtrees, adding 1 to the maximum of the two heights. This ensures that all affected nodes maintain correct height values, which is critical for calculating balance factors and determining the need for further rotations .

In an AVL tree, the balance factor (BF) is used to measure the balance state of a node. It is calculated as the height difference between the left and right subtrees of that node. The BF for a node T is computed as BF(T) = height(left subtree) - height(right subtree). During insertion, after adding a new node, BFs are checked for each ancestor node and if any BF becomes greater than 1 or less than -1, rotations are performed to restore balance .

The function `BF(node *T)` is responsible for checking the balance of a given node after an insertion. It calculates the balance factor as the difference in height between the left and right subtrees. During the insertion process, this function is invoked recursively after inserting a new node to determine if any ancestor node requires rotation due to imbalance. If an imbalance is detected, appropriate rotation functions such as `LL`, `RR`, `LR`, or `RL` are called to restore balance .

The insertion process in an AVL tree maintains balance by ensuring that for any node, the height difference between the left and right subtrees does not exceed one. When a node is inserted, the balance factor (BF) of each ancestor node is calculated to check if it has become unbalanced. If a node becomes unbalanced, rotations are used to restore balance: the tree may undergo a right rotation (LL), left rotation (RR), left-right rotation (LR), or right-left rotation (RL) depending on the position of the inserted node relative to the subtree root .

AVL trees are preferred over binary search trees in applications where frequent dynamic insertions and deletions occur, and where consistent time complexity for lookup, insertion, and deletion is crucial due to their ability to maintain self-balance automatically. Specific criteria include scenarios requiring high-performance databases with real-time indexing or data structures needing guaranteed logarithmic depth for optimal search times. AVL trees minimize performance degradation over time due to their ability to keep the tree balanced through rotations, unlike standard BSTs, which can become skewed and degrade to O(n) time complexity in the worst cases .

The four types of rotations in AVL trees are: 1) Right Rotation (LL): Applied when a left subtree becomes unbalanced with an excess node on the left. It shifts the subtree root to its right child. 2) Left Rotation (RR): Similar to right rotation but applied to right-heavy subtrees, moving the root to its left child. 3) Left-Right Rotation (LR): A combination of a left rotation on a left child followed by a right rotation on the root. 4) Right-Left Rotation (RL): Involves a right rotation on a right child followed by a left rotation on the root. These rotations help restore balance by rearranging nodes to reduce height imbalance .

The AVL tree implementation includes additional functions such as calculating the balance factor and performing rotations (LL, RR, LR, RL) to maintain balance after each insert operation. This requires keeping track of each node's height. In contrast, the Binary Search Tree (BST) implementation does not require balance factors or rotations as it does not self-balance, meaning it relies solely on left-right comparisons to insert nodes. The AVL tree is more complex due to the added balancing mechanisms .

The simplicity of BSTs makes them easier to implement and understand, especially when minor imbalance issues are not impactful, such as when expected inputs are near-randomized. AVL trees, with their complex balancing mechanisms and mandatory height tracking, ensure O(log n) operations by keeping the tree height minimal. Scenarios with frequent insertions and deletions, requiring predictable time complexity, favor AVL trees. In contrast, simpler applications where balanced access patterns are typical may benefit from the computational simplicity of BSTs due to less overhead in maintaining balance .

You might also like