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-4 Tree

-
Image
 Generally all the process is same as 2-3 Tree. So here we discuss the differences of 2-3-4 Tree from 2-3 Tree. Every Node must have at least ceil(n/2 here 4/2) children and maximum 4 children that's why is is called 2-3-4 tree b/c it will have 2 or 3 or 4 child of a node. Also called B-Tree of degree 4 Every node must be at same level Representation: Splitting:          When we insert element while node is full we will have even(4) number of elements so we can't divide element uniformly for splitting. So either we put more element to right, i.e. right biased or to left i.e. left biased.      Let we insert 40 in non-empty node: 
Read more