# AVL TREES

Published on April 22, 2012

Author: arorajitin93

Source: authorstream.com

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

03. 02. 2012
0 views

31. 01. 2013
0 views

29. 05. 2012
0 views

22. 04. 2012
0 views

10. 02. 2012
0 views

03. 02. 2012
0 views