# AVL TREES

Views:

Category: Education

## Presentation Description

No description available.

## 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

### 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

After deleting

case2

After deleting

Case 3

After deleting