AVL Tree

-

 AVL tree is a self-balancing binary search tree.

Comments

Post a Comment

Popular posts from this blog

Insertion/Deletion in 2-3 Tree

-
Image
Insertion:               Let we create 2-3 tree by inserting elements:                                                                      20, 30, 40, 50, 60, 10, 15, 70, 80                Insert 20,30:               Now we insert these two element in a single node as it can hold 2 elements so,       Insert 40:               Node is already full so split the node             In splitting: We take two nodes left and right and a root node Left node contain smallest element Right node contain greatest element Root node contain middle element and take lest and ...
Read more

AVL Rotations

-
Image
Rotation is required only in the nodes which are imbalance, imbalance means that | height of right sub-tree - height of left sub-tree | > 1. Balancing reduce the height of tree like a tree with node n have maximum height (n-1) but after rotation it will be about log(n).
Read more

2-3 Trees

-
Image
 Some properties: Multiway/M-way search tree Degree : 3 (maximum no. of children) All leaf at same level Every node must have at least ceil(n/2 here 3/2) children Also call B-Tree of degree 3 Can't have duplicate element Representation: l contain all the element smaller than k1 m contain all the element b/w k1 and k2 n contain all the element greater than n k1 < k2 for every node Applications: Used as example during study B-Tree and B+ Tree Used internally in DBMS    
Read more