Question

Write Short notes on AVL Tree

Answer 1

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