Saved Bookmarks
| 1. |
Give mathematical recursive definition of an AVL tree. |
|
Answer» AVL tree definition: 1. An empty binary tree a is an AVL tree 2. If ‘Bt’ is the non-empty binary tree with ‘BtL’ and ‘BtR’ as its left and right sub trees, then ‘Bt’ is an AVL tree if only if: • ‘BtL’ and ‘BtR’ are AVL trees and • | hL-hR | ≤ 1 where hL and hR are the heights of ‘BtL’ and ‘BtR’ respectively. | hL-hR | is called balance factor of a node, its value can be {-1, 0, 1} |
|