codelike-logo
AVL Tree Visualization
AVL

AVL Tree


AVL tree is enhancement version of binary search tree. we know that avl tree is height balance tree. more information about avl tree .

15508617053037-118021012083079

Example Of AVL Tree

50042-121-175040370620370300310

Example of AVL Tree

Balance Factor


Balance factor of avl tree node is depends upon height of right subtree and height of left sub tree.

Balance Factor of Node :(height of right subtree)-(height of left subtree).

30 1 = [ 2-1 ]210370310370 Height of Right Subtree is [2] Height of Leftsubtree is [1]

Height Representation

Height of node [30] is : 1

Height of node [21] is : 0

Height of node [37] is : 0

Height of node [31] is : 0

Height of node [37] is : 0

C program to find Height of tree

Valid balance Factor


Valid balance factor of AVl tree are [ 0 , 1, -1] . If get other balance factor that means to need rotate avl tree node.

52-1861580305902001314-184-118-1199114112308801403000

Show balance factor

Rotation Of AVL Tree


4 Rotation of AVL tree

LL Rotation

LR Rotation

RL Rotation

RL Rotation

LL Rotation

90 L L-280-1700 Problem blance factor -2 [ L L ] Rotation

This is basic example to LL rotation. Now actual visualization on this given avl tree with NULL representation on Left and Right child.

root 90-2NULL80-1NULL700NULLNULL

After LL Rotation [view rotation]

900800700

Step 1: In this example root are involved to LL rotation. that means modifying root of tree. use one hold pointer variable that is pointed to left child of root.

hold root 90-2NULL80-1NULL700NULLNULL

Step 2: Modifying the change of root node left child.

hold root 90-2NULL80-1NULL700NULLNULL

Step 3: Change the link of hold pointer right_child to this root node.

hold root 90-2NULL80-1NULL700NULLNULL

Step 3: Change root node.

hold root, 90-2NULL80-1NULL700NULLNULL

Step 4: Final change blance Factor.

900800700NULLNULLNULLNULL

RR Rotation

30 2 Problem This Balance Factor [2] [ R R ]40 150 0

After RR Rotation [view rotation]

300400500

RL Rotation

50 270 -160 0 Problem This Balance Factor [2] [ R L ]

After RL Rotation [view rotation]

500700600

LR Rotation

80 -260 170 0 Problem This Balance Factor [-2] [ L R ]

After LR Rotation [view rotation]

800600700

Above perform AVL Tree all Operation.

Tree Questions and solution, Back To Home


Comments