Question

construct the Avl tree for the following numbers
21,26,30,9,4,14,28,18,15​

Answer 1

Answer:

Section 4 SOLUTION: AVL Trees & B-Trees

1. What 3 properties must an AVL tree have?

a. Be a binary tree

b. Have Binary Search Tree ordering property (left children < parent, right children > parent)

c. Be a balanced tree: | n.left.height – n.right.height | ≤ 1 for all nodes n in the tree.

2. Draw an AVL tree of height 4 that contains the minimum possible number of nodes.

Construct a minimum size AVL tree of height h by creating a new root, and making one of its children a

minimum AVL tree of height h-1, and the other a minimum AVL tree of h-2. So to get a minimum

AVL tree of height 4, we need to build up minimum AVL trees of heights 0-3 first. The image below

shows each of these, and finally a minimum AVL tree of height 4. Values are left out here, but any

valid BST values could be filled in. Note that there are many different possible orderings of branches

(left versus right); the ones shown below are one way to do it. The minimum number of nodes is 12.

3. In a typical BST, inserting keys in order result in a worst-case height. Show the result when an

initially empty AVL tree has keys 1 through 7 inserted in order.

4. Insert 18 into the following AVL tree. What type of imbalance does it cause? Show the result after

balancing.

a. Inserting any value greater than 20 causes a right-right imbalance at node 10, the root, because

the root’s left child now has height 1 and the right child has height 3.

b. Inserting any value LESS than 20 causes a right-left imbalance also at the root, for the same

reason.