Now, Fig. 11.26 shows a simple example of insertion into an AVL tree using rotation. Multimedia
player receives stream with various objects from server, and renders the scene graph. Fig. 11.26
receives various multimedia objects text, image, video, animation, audio, graphic, geometric
and h.263 in turn.
Fig. 11.26. The insertion of multimedia object into an AVL tree using rotation
11.3.3. Deletion from an AVL tree
If we try to delete a node from an AVL tree, since the height is changed, the balance must be
kept. While deleting a node from an AVL tree, we can use the same concept for the rotation to
balance the tree as inserting a node.
No rotation
We consider an example to delete a node from simple AVL tree of Fig. 11.27. Since this example
is too simple and keeps the balance of an AVL tree during the deletion, it does not have any
rotations.
1)
If a node is the leaf as the node 2, it is deleted simply.
2)
If a node has at most one subtree as the node 8, it is deleted, and then the single node 9 is
linked to the node 7.
3)
If the node to be deleted has two subtrees as the node 3, its deletion is more complicated.
In this case, we find the immediate predecessor node 2 of the node 3 under the inorder
traverse, and then link parent node 7 of node 3 to the immediate predecessor node 2. We
delete node 3.
Fig. 11.27. An example to delete a node from simple AVL tree
From above examples, we can make the general description to delete a node from an AVL tree.
Although the left or right subtree is shortened by deleting, if the height of a tree is unchanged or
| H
L
–
HR | =
1, the tree is not rebuilt. For any node x in an AVL tree, its deletion is performed
as follows.
1) If the node x is the leaf, we delete it simply.
2) If the node x has at most one subtree, we delete x by linking the parent of x to the single
subtree of x.
3) If the node x has two subtrees, we find the immediate predecessor y of x under inorder
traversal. In order to find y, we traverse the left subtree of node x to the right final node
continuously. If y has no more right subtree, we replace the position of the node x by the
node y. Then we delete former y in the tree. Fig. 11.28 shows this.
Fig. 11.28. Finding the immediate predecessor y of x
Fig. 11.29 shows that the tree is not rebuilt. Fig. 11.29 (a) shows that both balance factor and the
height of node t are unchanged by deleting node x. The balance factor of node t is EH = 0 and
the height of tree T1 is unchanged. Thus, the balance factor of node t must be EH = 0. Fig. 11.29
(b) shows that the balance factor of node t is changed, but its height is unchanged by deleting
node x. The balance factor of node t is EH = 0 and the height of tree T1 is unchanged. However,
since the right subtree of node t is reduced by 1, the balance factor of node t must be changed to
LH = 1. Fig. 11.29 (c) shows that the balance factor of node t is changed, also its height is
changed by deleting node x. Since balance factor of node t is RH = 1 and the height of tree T2 is
reduced by 1, the balance factor of node t must be changed to EH = 0.
Fig. 11.29. The deletion of node x without rotation
We consider another example to delete a node from the larger AVL tree. Its deletion is very
complicated, since this example may not keep the balance of an AVL tree during the deletion.
This has some rotations.
Rotation
By the deletion of the node x, since the height of the subtree rooted at x may be reduced by 1 or
not, we must trace the balance factor for the change of height for each node t on the path from
the parent of x to the root in the tree. The node t includes node of position that has just been
replaced by deletion. Thus, the balance factor of the current node t can be changed according to
its height of the left or right subtree.
For each node t on the path from the parent of x to the root (the node t includes node of position
that has just been replaced by deletion), if the balance factor of node t is RH or LH and the
subtree rooted at t has | H
L
–
HR | =
2 by deleting, this tree is no longer an AVL tree. We must
rebuild the tree to maintain its balance with rotation. The direction of rotation depends on
which height of subtree was reduced.
In the deletion with rotation, we have single and double rotations according to the balance
factor of each t and s, where s is the root of the taller subtree of t. While the tree has | H
L
–
HR |
=
2 at node t and s, the direction of rotation is determined according to following cases.
1) The balance factor of t is LH (or RH) and that of s is EH:
Since the node t has HR – H
L
=
2 by the deletion, the single left rotation is performed
to restore balance. The height of tree is unchanged. Fig. 11.30 shows this case.
Fig. 11.30. The left rotation when t is RH and s is EH
2) The balance factor of t is LH and that of s is LH (or if the balance factor of t is RH and
that of s is RH):
The case means that the direction of both balance factors is same. Since the node t has
HR –
H
L
=
2 by the deletion, the single left rotation is performed to restore balance.
The height of tree is reduced. Fig. 11.31 shows this case.
Fig. 11.31. The left rotation when t is RH and s is RH
3) The balance factor of t is RH and that of s is LH (or if the balance factor of t is LH and
that of s is RH):
The case means that the direction of both balance factors is opposite. Since the node t
has HR
–
H
L
=
2 by the deletion, double rotations is performed in order s and t to
restore balance. The height of tree is reduced. The balance factor of new root is EH. Fig.
11.32 shows this case.
If there is no further change of the balance factor and the tree satisfies the condition of an AVL
tree, the deletion processing is finished.
Example: Given the AVL tree as Fig. 11.33. In Fig. 11.33 (a), if we try to delete node 11, we place
the immediate predecessor node 10 into the position of node 11 as Fig 11.33 (b). Since the node
10 of Fig 11.33 (b) has the right higher subtree, we rotate node 10 to the left as shown in Fig.
11.33 (c). The height of Fig. 11.33 (c) is 4 and left higher at the node 9. We rotate the node 7 to
the left, and then to the right as shown in (d) and (e) of Fig. 11.33.?
Fig. 11.32. The double rotations when t is RH and s is LH
Fig. 11.33. An example to delete a node from complicated AVL tree
11.3.4. Implementation of an AVL tree
From actions and cases of an AVL tree, we can implement functions for the left and right
rotations to balance it. For the practical implementation using, we need the abstract data type,
and also use an AVL tree with nodes already in order, tree insertion and comparison algorithm.
There are functions in C programming language syntax for the left and right rotation while
insertion into and deletion from an AVL tree.
#include <stdio.h>
#include < stdio.h >
// Declaration of integer entry
typedef int Enter;
typedef
struct avltreenode AVLTreeNode;
typedef struct avltreenode{
AVLTreeNode *LeftSubTree;
Enter Entry;
AVLTreeNode *RightSubTree;
int Balance;
} AVLTreeNode;
AVLTreeNode *root = NULL;
// Output of tree entry using traversing in preorder
void preorder(AVLTreeNode *CurrentNode)
{
if (CurrentNode)
{
printf ("%d,%d\n",CurrentNode->Entry,CurrentNode->Balance);
preorder(CurrentNode->LeftSubTree);
preorder(CurrentNode->RightSubTree);
}
}
void Insert(Enter key)
{
//Current node and its parent node in searching
AVLTreeNode *CurrentNode, *ParentNode;
//New creating node for insertion
AVLTreeNode *NewNode;
//Unbalanced node and its parent
AVLTreeNode *UnbalanceNode, *UnbalanceParentNode;
//Temporary node pointer for rotation
AVLTreeNode *tmp, *tmp2;
// If direction = +1: insertion into a left subtree
// If direction = -1: insertion into a right subtree
// direction is added to balance value to check tree is balance or
unbalance. //
// If root is NULL, function finishes.
int direction;
if (root == NULL)
{
root = (AVLTreeNode*)malloc(sizeof (avltreenode));
root->Entry = key;
root->LeftSubTree = NULL;
root->RightSubTree = NULL;
root->Balance = 0;
return;
}
// Initialize.
UnbalanceNode = root;
UnbalanceParentNode = NULL;
CurrentNode = root;
ParentNode = NULL;
// Searching tree.
while (CurrentNode)
{
// If the balance factor of current node is +1 or -1, save that node. //
// The node has possibility to be unbalanced node. //
if (CurrentNode->Balance)
{
UnbalanceNode = CurrentNode;
UnbalanceParentNode = ParentNode;
}
ParentNode = CurrentNode;
// Checking if the current node is equal to inserting node.
// If equal, finishes.
if (key == CurrentNode->Entry) return;
// Move to the left when key is less than.
else if (key < CurrentNode->Entry)
CurrentNode = CurrentNode->LeftSubTree;
// Move to the right when key is greater than.
else
CurrentNode = CurrentNode->RightSubTree;
}
// Create new node and put the value.
NewNode = (AVLTreeNode*) malloc(sizeof (avltreenode));
NewNode->Entry = key;
NewNode->LeftSubTree = NULL;
NewNode->RightSubTree = NULL;
NewNode->Balance = 0;
// Compare it with parent node, and then decides left subtree or right subtree.
if (key < ParentNode->Entry )
ParentNode->LeftSubTree = NewNode;
else
ParentNode->RightSubTree = NewNode;
// According to the unbalanced node, decide to move to the left or right.
if (key < UnbalanceNode->Entry)
{
CurrentNode = UnbalanceNode->LeftSubTree;
tmp = CurrentNode;
direction = 1;
}
else
{
CurrentNode = UnbalanceNode->RightSubTree;
tmp = CurrentNode;
direction = -1;
}
// Set balance factors of nodes on the path from the current node to the new
// creating node.
while (CurrentNode != NewNode)
{
if (key < CurrentNode->Entry)
{
CurrentNode->Balance = 1;
CurrentNode = CurrentNode->LeftSubTree;
}
else
{
CurrentNode->Balance = -1;
CurrentNode = CurrentNode->RightSubTree;
}
}
// Checking if balance factor of unbalance node is 0 (or when adding direction to it). If it is
balanced, function finishes. //
if (UnbalanceNode->Balance == 0 || UnbalanceNode->Balance +
direction == 0)
{
UnbalanceNode->Balance += direction;
return;
}
// Move to the left.
if (direction == 1)
{
// Move the node pointer and set balance factor newly.
if (tmp->Balance == 1) //Single Right Rotation
{
UnbalanceNode->LeftSubTree= tmp->RightSubTree;
tmp->RightSubTree = UnbalanceNode;
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
else // Double Rotation
{
tmp2 = tmp->RightSubTree;
tmp->RightSubTree = tmp2->LeftSubTree;
UnbalanceNode->LeftSubTree=tmp2-RightSubTree;
tmp2->LeftSubTree = tmp;
tmp2->RightSubTree = UnbalanceNode;
if (tmp2->Balance == 1)
{
UnbalanceNode->Balance = -1;
tmp->Balance = 0;
}
else if (tmp2->Balance == -1)
{
UnbalanceNode->Balance = 0;
tmp->Balance = 1;
}
else
{
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
tmp2->Balance = 0;
tmp = tmp2;
}
}
// Move to the right.
else
{
// Move the node pointer and set balance factor newly.
if(tmp->Balance == -1) // Single Left Rotation
{
UnbalanceNode->RightSubTree= tmp->LeftSubTree;
tmp->LeftSubTree = UnbalanceNode;
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
else // Double Rotation
{
tmp2 = tmp->LeftSubTree;
tmp->LeftSubTree = tmp2->RightSubTree;
UnbalanceNode->RightSubTree=tmp2-LeftSubTree;
tmp2->RightSubTree = tmp;
tmp2->LeftSubTree = UnbalanceNode;
if (tmp2->Balance == 1)
{
UnbalanceNode->Balance = 1;
tmp->Balance = 0;
}
else if (tmp2->Balance == -1)
{
UnbalanceNode->Balance = 0;
tmp->Balance = -1;
}
else
{
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
tmp2->Balance = 0;
tmp = tmp2;
}
}
// If parent of unbalanced node is NULL, the subtree of unbalanced node becomes root. It
means that tmp is root. //
if (UnbalanceParentNode == NULL)
root = tmp;
// The subtree of unbalanced node becomes the subtree of parent of the unbalanced
node. It
means that tmp becomes the subtree of parent of the unbalanced node. //
else if(UnbalanceNode==UnbalanceParentNode->LeftSubTree)
UnbalanceParentNode->LeftSubTree = tmp;
else
UnbalanceParentNode->RightSubTree = tmp;
}
/*Search Func.
input : Entry value of Node to be search.
output : Node pointer
*/
AVLTreeNode* Search(Enter key)
{
if (root != NULL){
AVLTreeNode *node = root;
// While node is not NULL.
while (node)
{
// If Entry = key, return node pointer.
if (node->Entry == key)
return node;
//If Entry < key, move to the right.
else if (node->Entry < key)
node = node->RightSubTree;
// If Entry > key, move to the left.
else
node = node->LeftSubTree;
}
}
return NULL;
}
/*
Delete Func.
input : Entry of Node to be deleted
output : Deleted tree.
*/
void Delete(Enter key)
{
// Selected current node and its parent node
AVLTreeNode *CurrentNode, *ParentNode;
// Unbalanced node and its parent
AVLTreeNode *UnbalanceNode, *UnbalanceParentNode;
// Temporary node pointer
AVLTreeNode *tmp, *tmp2;
// Save nodes on the path from the root to the node to be deleted
AVLTreeNode *SaveNode[100];
// Save direction of each node on the path from the root to the node to be deleted ( -1 or +1) //
int Path[100];
int NodeCount = 0; // Save the number of SaveNode
int PathCount = 0; // Save the number of Path
int i; // Loop iterations
// Initialize.
CurrentNode = root;
ParentNode = NULL;
// Finding the key.
while (CurrentNode != NULL && CurrentNode->Entry != key)
{
ParentNode = CurrentNode;
// Save the node on the path while searching.
SaveNode[NodeCount++] = CurrentNode;
if (CurrentNode->Entry < key){
CurrentNode = CurrentNode->RightSubTree;
Path[PathCount++]=-1; // Save the direction.
}
else {
CurrentNode = CurrentNode->LeftSubTree;
Path[PathCount++] = 1;// Save the direction.
}
}
SaveNode[NodeCount++] = CurrentNode;
// If the key exists.
if (CurrentNode != NULL)
{
// Case of the leaf node
if (CurrentNode->LeftSubTree == NULL &&
CurrentNode->RightSubTree == NULL)
{
//Root only exists in the tree.
if (PathCount == 0)
{
root = NULL;
}
// Disconnect from the parent of node.
else if (Path[PathCount-1] == -1)
ParentNode->RightSubTree = NULL;
else if (Path[PathCount-1] == 1)
ParentNode->LeftSubTree = NULL;
}
// If it exists in left of current node, copy the maximum value in left subtree into current node.//
else if (CurrentNode->LeftSubTree != NULL)
{
// to save the maximum value in the LeftSubTree.//
tmp = CurrentNode->LeftSubTree;
tmp2 = CurrentNode;// parent of tmp
Path[PathCount++] = 1;
SaveNode[NodeCount++] = tmp;
// Finding the maximum value
while (tmp->RightSubTree != NULL)
{
SaveNode[NodeCount++] = tmp;
tmp2 = tmp;
tmp = tmp->RightSubTree;
Path[PathCount++] = -1;
}
// The maximum value is Entry value to have been deleted.//
CurrentNode->Entry = tmp->Entry;
tmp->Balance = 0;
// If the node with maximum value is not leaf, it has one subtree only. If it has not subtree,
disconnect it. //
if (Path[PathCount-1] == -1)
{
if (tmp->LeftSubTree != NULL)
tmp2->RightSubTree = tmp->LeftSubTree;
else
tmp2->RightSubTree = NULL;
}
else
{
if (tmp->RightSubTree != NULL)
tmp2->LeftSubTree = tmp->RightSubTree;
else
tmp2->LeftSubTree = NULL;
}
}
else if (CurrentNode->RightSubTree != NULL)
{
// Save minimum value in the RightSubTree
tmp = CurrentNode->RightSubTree;
tmp2 = CurrentNode;//tmp? parent
Path[PathCount++] = -1;
// The minimum value is the Entry of deleted node.//
SaveNode[NodeCount++] = tmp;
// Search the minimum value.//
while (tmp->LeftSubTree != NULL)
{
SaveNode[NodeCount++] = tmp;
tmp2 = tmp;
tmp = tmp->LeftSubTree;
Path[PathCount++] = 1;
}
CurrentNode->Entry = tmp->Entry;
tmp->Balance = 0;
// If the node with maximum value is not leaf, it has one
subtree only. If it has not subtree,
disconnect it. //
if (Path[PathCount-1] == -1)
{
if (tmp->LeftSubTree != NULL)
tmp2->RightSubTree = tmp->LeftSubTree;
else
tmp2->RightSubTree = NULL;
}
else
{
if (tmp->RightSubTree != NULL)
tmp2->LeftSubTree = tmp->RightSubTree;
else
tmp2->LeftSubTree = NULL;
}
}
// There are two more nodes to have been searched.//
if (NodeCount > 1){
preorder(root);
printf ("\n");
// Search the already searched nodes from end reversly.//
for (i = NodeCount - 2; i >= 0; i--)
{
// Change the balance factor of previous node. //
if (SaveNode[i+1]->Balance == 0)
{
// Set the balance factor
SaveNode[i]->Balance += -Path[i];
// Unbalanced with +2 or -2
if (SaveNode[i]->Balance == 2 ||
SaveNode[i]->Balance == -2)
{
// Save parent of unbalance node. //
if(I !=0 && SaveNode[i-1] != NULL)
UnbalanceParentNode=SaveNode[i-1];
else
UnbalanceParentNode = NULL;
// Save the unbalanced node.
UnbalanceNode = SaveNode[i];
// Balance is +2. Left is unbalance.
if (SaveNode[i]->Balance == 2) {
// Save to rotate. //
tmp = UnbalanceNode->LeftSubTree;
// Single Right Rotation
if (tmp->Balance >= 0) {
// Set the balance factor. //
if (tmp->RightSubTree) {
UnbalanceNode->Balance =1-tmp->RightSubTree->Balance;
tmp->Balance = -1 + tmp->RightSubTree->Balance;
}
else
{
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
// rotate
UnbalanceNode->LeftSubTree = tmp->RightSubTree;
tmp->RightSubTree = UnbalanceNode;
}
else // Double Rotation
{
// rotate
tmp2 = tmp->RightSubTree;
tmp->RightSubTree = tmp2->LeftSubTree;
UnbalanceNode->LeftSubTree = tmp2->RightSubTree;
tmp2->LeftSubTree = tmp;
tmp2->RightSubTree = UnbalanceNode;
//Set the balance factor.
if (tmp2->Balance == 1)
{
UnbalanceNode->Balance = -1;
tmp->Balance = 0;
}
else if (tmp2->Balance == -1)
{
UnbalanceNode->Balance = 0;
tmp->Balance = 1;
}
else
{
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
tmp2->Balance = 0;
tmp = tmp2;
}
}
// Balance is -2. Right is unbalance.
else if (SaveNode[i]->Balance == -2)
{
// Save to rotate.
tmp = UnbalanceNode->RightSubTree;
if (tmp->Balance<= 0) // Single Left Rotation
{
// Set the balance facotr.
if (tmp->LeftSubTree)
{
UnbalanceNode->Balance = -1 - tmp->LeftSubTree->Balance;
tmp->Balance = 1 + tmp->LeftSubTree->Balance;
}
else
{
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
// Rotate.
UnbalanceNode->RightSubTree = tmp->LeftSubTree;
tmp->LeftSubTree = UnbalanceNode;
}
else // Double Rotation
{
tmp2 = tmp->LeftSubTree;
tmp->LeftSubTree = tmp2->RightSubTree;
UnbalanceNode->RightSubTree = tmp2->LeftSubTree;
tmp2->RightSubTree = tmp;
tmp2->LeftSubTree = UnbalanceNode;
// Set the balance factor.
if (tmp2->Balance == 1)
{
UnbalanceNode->Balance = 1;
tmp->Balance = 0;
}
else if (tmp2->Balance == -1)
{
UnbalanceNode->Balance = 0;
tmp->Balance = -1;
}
else
{
UnbalanceNode->Balance = 0;
tmp->Balance = 0;
}
tmp2->Balance = 0;
tmp = tmp2;
}
}
// If parent of unbalanced node is NULL, its subtree is root. tmp becomes the root. //
if (UnbalanceParentNode == NULL)
root = tmp;
else if (UnbalanceNode == UnbalanceParentNode->LeftSubTree)
UnbalanceParentNode->LeftSubTree = tmp;
else
UnbalanceParentNode->RightSubTree = tmp;
}
}
}
}
free (SaveNode[NodeCount-1]);
}
}
void main( )
{
int choice;
Enter key;
while (1){
printf ("Select(1) Insert(2)Delete(3)Search(4)View (5)Exit : ");
scanf ("%d", &choice);
switch(choice)
{
case 1:
printf ("Key : ");
scanf("%d", &key);
Insert(key);
break;
case 2:
printf ("Key : ");
scanf ("%d", &key);
Delete(key);
break;
case 3:
printf ("Key : ");
scanf ("%d", &key);
Search(key);
break;
case 4:
preorder(root);
printf ("\n");
break;
default :
break;
}
if (choice == 5)
break;
}
}