CS-62 JUNE 2003 QNO 3(c)

3 (c) What is an AVL tree? How does it differ from a Binary Tree?
Answer

A Tree is called AVL tree (Balanced Binary tree) if each node possesses one of the following properties:
(i) A node is called left heavy, if the longest path in its left subtree is one longer then the longest past of its right subtree.
(ii) A node is called right heavy, if the longest part in the right subtree is one longer than the longest path in its left subtree.
(iii) a node is called balanced if the longest paths in both the right and the left subtrees are equal.

Binary tree: A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then its is called binary tree. In a binary tree left and right subtrees distinguish subtrees of a node.

An AVL tree is a balanced tree, but binary tree can be unbalanced also.