Maintaining the Consistency of an Avl Tree Through Modified Use of Predefined Four Cases (Rr, Ll, Lr, Rl)

Maintaining the consistency of AVL tree through modified use of predefined four

cases (RR,LL,LR,RL).

PANKAJ KUMAWAT,JASPREET SAHOTA

(Students of Arya college of Engineering and Research Center)

Mail-Id- pankajkumawat43@yahoo.in

Sahotajaspreet24@gmail.com

Abstract - A tree rotation, which is quite a browbeat concept initially, is required when any insertion or

deletion of a node is performed which leaves the AVL tree in an unbalanced state i.e. a state in which any

node has a balance factor of greater than 1, or less than -1.When an imbalance is detected, it is

necessary to balance it by doing the appropriate rotation. It turns out that there are only four cases to

consider and each case has its own rotation (RR, LL, LR, RL). We have surfaced a modified use of these

rotations to overcome the consistency failure of complex structured AVL tree.

Index Terms - binary tree strategy, nodes pointers concept, predefined rotations.

Introduction- A tree rotation can be an

intimidating concept at first. You end up in a

situation where you're juggling nodes, and these

nodes have trees attached to them, and it can all

become confusing very fast. I find it helps to

block out what's going on with any of the sub

trees which are attached to the nodes you're

fumbling with, but that can be hard.

A right rotation is a mirror of the left rotation

operation described above. Imagine we have

this situation:

Left Rotation (LL)

Imagine we have this situation:

4 becomes the new root.

3 takes ownership of 4's left child as its right

child, or in this case, null.

5 takes ownership of a as its left child.

Left-Right Rotation (LR) or "Double left"

4 becomes the new root.

3 takes ownership of 4's left child as its right

child, or in this case, null.

5 takes ownership of a as its left child.

Right Rotation (RR)

Sometimes a single left rotation is not sufficient

to balance an unbalanced tree. Take this

situation:

After that we can see that...