AVL TREES

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

AVL TREES:

AVL TREES Jitin A rora

AVL Tree Defination:

AVL Tree Defination AVL trees are balanced. An AVL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most

Insertion:

Insertion Four cases to consider. The insertion is in the left subtree of the left child of x. right subtree of the left child of x. left subtree of the right child of x. right subtree of the right child of x. Idea: Cases 1 & 4 are solved by a single rotation. Cases 2 & 3 are solved by a double rotation.

Single rotation:

Single rotation

Double rotation :

Double rotation Step:1

Double rotation:

Double rotation Step:2

Deletition :

Deletition Deletion: Case 1: if X is a leaf, delete X Case 2: if X has 1 child, use it to replace X Case 3: if X has 2 children, replace X with its inorder predecessor (and recursively delete it) Rebalancing

Deletition case1:

Deletition case1

After deleting:

After deleting

case2:

case2

After deleting:

After deleting

Case 3:

Case 3

After deleting:

After deleting

authorStream Live Help