Write Short notes on AVL Tree

First time here? Checkout the FAQ!

x

An AVL tree is a height balance tree. These trees are binary search trees in which the

heights of two siblings are not permitted to differ by more than one.

Searching time in a binary search tree is O(h) where h is the height of the tree. For

efficient searching it is necessary that the height should be kept minimum.

A full binary search tree with n nodes will have a height of O(log n). In practice, it is

very difficult to control the height of a BST. It lies between O(n) to O(log n). An AVL tree is

a close approximation of full binary search tree.

The balance factor of a node in a AVL tree could be -1, 0 or 1.

1. 0 indicates that the left and right subtrees are equal.

2. +1 means the height of the left subtree is one more than the height of the right

subtree.

3. -1 indicates that the height of the right subtree is one more than the height of the left

subtree.

Example::https://quesnit.in/476/insert-elements-avl-tree-44-17-32-78-50

Explore more Questions in Data Structure