AVL TREES

Information about AVL TREES

Published on April 22, 2012

Author: arorajitin93

Source: authorstream.com

Content

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

Related presentations


Other presentations created by arorajitin93

Different Types Of SDLC Models
03. 02. 2012
0 views

Different Types Of SDLC Models

Software Project Planning
31. 01. 2013
0 views

Software Project Planning

CASE tools
29. 05. 2012
0 views

CASE tools

Wi-FI Technology
22. 04. 2012
0 views

Wi-FI Technology

five pointsome1 12
10. 02. 2012
0 views

five pointsome1 12

gnu project
03. 02. 2012
0 views

gnu project