Discuss AVL Trees.

14views

written 8.5 years ago by

teamques10 ★ 68k

A binary tree is a data structure in which every node has no more than two descendent nodes and no more than one parent node.
A binary search tree is a binary tree in which a node’s left child node has a value less than its and the node’s right node has a value greater than its.
An AVL tree is a binary search tree which has the following properties:-
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
In this example, every left subtree has a height one greater than each right subtree

The motivation of AVL trees was to guarantee a height of log(n) so that insertions and deletions always occur at O(log(n)).
A balanced factor is an integer which is associated with each node of the tree. It indicates weather a tree is left-heavy (height of left subtree is greater than that of right subtree), balanced (both subtress are of the same height), or right-heavy(opposite of left-heavy).
Balance factor of a node = height othe left subtree - the height of the right subtree
Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.
If the balanced factor’s magnitude exceeds 1 after an operation such as insertion or deletion, then balancing is required. This is done with the help of rotations.
There are basically 4 types of imbalance cases and 2 types of rotations to make the tree balanced.

ADD COMMENT EDIT