0
1.7kviews
Discuss AVL Trees.
0
13views
• 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.