![AVL Tree Deletion PDF [PDF]](https://pdfs.asia/img/200x200/avl-tree-deletion-pdf.jpg)
6 0 517 KB
AVL Tree Deletion Deletion of nodes from an AVL tree is similar to that of Insertion. But the main difference between AVL Insertion and AVL Deletion is that:
Imbalance caused in insertion can be corrected only with one rotation (single or double). In Insertion if imbalance occur then we need to find the first unbalanced node only from newly inserted node, by traversing toward Root node, and performing required rotation at that node will fix the whole AVL tree. But deletion of a node can imbalance multiple nodes in the tree (In ancestry line up-to Root node), so multiple rotations may be required and we need to traverse all the way back up-to the root node looking for imbalance nodes and performing required rotations.
AVL Tree deletion = Binary Search Tree delete (Search the node, and remove it)
+
Perform required rotations if deletion cause imbalance.
We distinguish AVL tree deletion in three cases: The node to be deleted is a leaf node (external node) The node to be deleted has exactly one child node. The node to be deleted has two children.
Attention
Don’t confuse if you found different case of AVL tree deletion (such as R0, R1, R-1, L0, L1, and L-1). All these six cases get automatically covered in above three case of AVL Tree deletion.
Case 1
The node to be deleted is a leaf node (i.e. node has no children) Deletion of even a single leaf node from an AVL tree may imbalance multiple nodes at a time. So traverse all the way back up-to Root node from parent of deleted leaf node in search of imbalance node, and perform required rotation if found any imbalanced node.
BF =0- (2) = - 2
25
25 30
22
Delete 23
30
22
Left Rotation at node 25
30
40
25 40
28
40
28
23
22 35
35
50
28
35
50
50 Delete 28
BF =-1 - (1) = - 2
30
30
30 Delete 25
25
40 35
50 Left Rotation at node 30
40 30
35
Delete 22
50
25
40 35
50
22
40 35
50
Let us see another in which deletion of single leaf node imbalance multiple node at a time, hence multiple rotation required.
30
30 BF =1 - (-1) = 2
25
25
40
40
Delete 26
22
35
26 34
20
22
50 45
34
20
60
50
35 45
60 70
70 Right Rotation at node 25
BF =1 - (3) = - 2
40
30
30
35
22
20
50
25
34
45
Left Rotation at node 30
60
22
20 70
40
50
35
25 34
45
60 70
Still unbalanced at node 30 (BF = -2), Tree is left heavy, so perform Left rotation at node 30.
Case 2
The node to be deleted has one child node. Deletion of a node having one child node may also imbalance multiple nodes at a time. So restore its “AVL-ness” property by performing required rotation, if get violated upon deletion.
Let us see an Example:
BF =0 - (2) = - 2
22
20
30
20
Left Rotation at node 25
30
Delete 22
28
27
30
25
25
40
28
40
27
35
40
25 20
35
28
35
27
Delete 40
30
28
30
25
20
Left-Right Rotation at node 30
27
35
35
25
20
28
27
Case 3
The node to be deleted has two children. Deletion of a node having two children may also imbalance multiple nodes at a time. So restore its “AVL-ness” property, if get violated by deletion. Let us see an Example:
45
45
BF = 1-(-1) =2
68
28 20
15
30
80
50
35
25
28
Delete 68
30
20
15
55
80 50
35
25
55
18
18
Left-Right Rotation at Node 80
45
28
15
25
18
Right Rotation at node 45
45
20
20 0
30
30 35
28
28
30
15
50
30
25 18
55
35
80
Example
Let us take an example of deletion which covers all the three cases as discussed above. 65
65
50 40
Delete 40
70 68
60
55
50
68 67
55
75
Right-Left Rotation at node 50
70
60
80
67
65
80
55
50
70
60
75
68
67
80
75
Delete 60
65
65 70 70
50 65
80
Left Rotation at node 65
68 50
68
75 67
55
Delete 55
50
80
67
Delete 70
68
75
65
80
68
50
40
65
50
68 67
75
Left-Right Rotation at node 75
70
75
40
80
80 75
