AVL Tree Insertion Of Node Explained With Simple Example

An AVL (Adelson-Velskii and Landis) Tree is a self balancing Binary Search Tree which has the following properties.

For any node “A”, the height of the left subtree of “A” and height of the right subtree of “A” differ by 1 at max.

In case of Binary search Trees worst case search complexity is O(n) in cases when the Binary Search Tree is skewed. In AVL tree, since heights of left and right subtree are balanced, hence search complexity improves to O(log n). Before going ahead have a look into AVL Tree Basics.

(more…)
AVL Tree Insertion Of Node Explained With Simple Example Read More