written 8.0 years ago by | • modified 8.0 years ago |

Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

**Marks:** 10 M

**Year:** May 2015

**1 Answer**

0

31kviews

What is AVL tree? Construct AVL tree using following sequence of data: 16, 27, 9,11,36,54,81,63,72

written 8.0 years ago by | • modified 8.0 years ago |

Mumbai University > Information Technology > Sem 3 > Data Structure and Algorithm analysis

**Marks:** 10 M

**Year:** May 2015

ADD COMMENT
EDIT

2

3.8kviews

written 8.0 years ago by |

An AVL tree is a binary search tree which has the following properties:-

The sub-trees of every node differ in height by at most one.

Every sub-tree is an AVL tree.

Each node in the AVL Tree possesses any one of the following properties:

A node is called left heavy, if the largest path in its left sub tree is one level larger than the largest path of its right sub tree.

A node is called right heavy, if the largest path in its right sub tree is one level larger than the largest path of its left sub tree.

The node is called balanced, if the largest paths in both the right and left sub trees are equal. Consider the following example of AVL tree where every left subtree has a height one greater than each right subtree.

*Figure 1: AVL Tree*

The motivation of AVL trees was to guarentee a height of log(n) so that insertions and deletions always occour at O(log(n)).

Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.

If the balanced factorâ€™s magniture exceeds 1after an operation such as insertion or deletion, then balancing is required. This is done with the help of rotations.

ADD COMMENT
EDIT

Please log in to add an answer.