What is the maximum height of an AVL tree with 7 nodes assume that a tree containing only the root node is said to have a height of 1?

As you mentioned for different positive integers,so I am assuming numbers will be 1 to N,for some positive integer N>=2:: Answer is::
N-1+2^{[log(N-1)]+2} , where in above formula,

N=ROOT KEY

log x= logarithmic value of x to base 2
[ x]=Floor of x i.e. highest integer less than or equal to x and

x^y= x raise to power of y.

Explanation:: As AVL Tree with root N will contain exactly N-1 nodes in it's left subtree with height log(N-1) and it's left subtree will be balanced in itself with height balance property of AVL Tree.
Let us say the height of left subtree be h ::
So , it's right subtree can be of h+1height and hence can contain at max -1+ 2^{h+1+1} nodes,
hence the answer will be left subtree nodes +1+right subtree nodes. Now left subtree nodes=N-1,so MAXIMUM NO. OF NODES IN AVL TREE WITH ROOT NODE N WILL BE::

N-1+2^{[log(N-1)]+2}.

The solution below is appropriate for working things out by hand and gaining an intuition, please see the exact formulas at the bottom of this answer for larger trees (54+ nodes).1

Well the minimum height2 is easy, just fill each level of the tree with nodes until you run out. That height is the minimum.

To find the maximum, do the same as for the minimum, but then go back one step (remove the last placed node) and see if adding that node to the opposite sub-tree (from where it just was) violates the AVL tree property. If it does, your max height is just your min height. Otherwise this new height (which should be min height+1) is your max height.

If you need an overview of what the properties of an AVL tree are, or just a general explanation of an AVL tree, Wikipedia is a great place to start.

Example:

Let's take the 7 node example case. You fill in all levels and find a completely filled tree of height 3. (1 at level 1, 2 at level 2, 4 at level 3. 1+2+4=7 nodes.) That means 3 is your minimum.

Now find the max. Remove that last node and place it on the left subtree instead of the right. The right subtree still has height 3, but the left subtree now has height 4. However these values differ by less than 2, so it is still an AVL tree. Therefore your max height is 4. (Which is min+1)

All three examples worked out below (note that the numbers correspond to order of placement, NOT value):

Formulas:

The technique shown above doesn't hold if you have a tree with a very large number nodes. In this case, one can use the following formulas to calculate the exact min/max height2.

Given n nodes3:

Minimum: ceil(log2(n+1))

Maximum: floor(1.44*log2(n+2)-.328)

If you're curious, the first time max-min>1 is when n=54.

1Thanks to Jamie S for bringing this failure at larger node counts to my attention.

2Technically, the height of a tree is the longest path length (in edges) between the root and any leaf node. However the OP's textbook uses a common alternate definition of height as the number of levels in a tree. For consistency with the OP and Wikipedia, we use that definition in this post as well.

3These formulas are from the Wikipedia AVL page, with constants plugged in. The original source is Sorting and searching by Donald E. Knuth (2nd Edition).

AVL tree is binary search tree with additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1. Here are some key points about AVL trees:

• If there are n nodes in AVL tree, minimum height of AVL tree is floor(log2n).
• If there are n nodes in AVL tree, maximum height can’t exceed 1.44*log2n.
• If height of AVL tree is h, maximum number of nodes can be 2h+1 – 1.
• Minimum number of nodes in a tree with height h can be represented as: N(h) = N(h-1) + N(h-2) + 1 for n>2 where N(0) = 1 and N(1) = 2.
• The complexity of searching, inserting and deletion in AVL tree is O(log n).

We have discussed types of questions based on AVL trees. 

Type 1: Relationship between number of nodes and height of AVL tree – 

Given number of nodes, the question can be asked to find minimum and maximum height of AVL tree. Also, given the height, maximum or minimum number of nodes can be asked. 

Que – 1. What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0. 

Solution: For finding maximum height, the nodes should be minimum at each level. Assuming height as 2, minimum number of nodes required: N(h) = N(h-1) + N(h-2) + 1 N(2) = N(1) + N(0) + 1 = 2 + 1 + 1 = 4. It means, height 2 is achieved using minimum 4 nodes. Assuming height as 3, minimum number of nodes required: N(h) = N(h-1) + N(h-2) + 1 N(3) = N(2) + N(1) + 1 = 4 + 2 + 1 = 7. It means, height 3 is achieved using minimum 7 nodes. Therefore, using 7 nodes, we can achieve maximum height as 3. Following is the AVL tree with 7 nodes and height 3. 

 Que – 2. What is the worst case possible height of AVL tree? 

• (A) 2*logn 
• (B) 1.44*log n
• (C) Depends upon implementation 
• (D) θ(n) 

Solution: The worst case possible height of AVL tree with n nodes is 1.44*logn. This can be verified using AVL tree having 7 nodes and maximum height. 

Checking for option (A), 2*log7 = 5.6, however height of tree is 3. 

Checking for option (B), 1.44*log7 = 4, which is near to 3. 

Checking for option (D), n = 7, however height of tree is 3. 

Out of these, option (B) is the best possible answer. 

Type 2: Based on complexity of insertion, deletion and searching in AVL tree – 

Que – 3. Which of the following is TRUE? 

• (A) The cost of searching an AVL tree is θ(log n) but that of a binary search tree is O(n) 
• (B) The cost of searching an AVL tree is θ(log n) but that of a complete binary tree is θ(n log n) 
• (C) The cost of searching a binary search tree is O(log n ) but that of an AVL tree is θ(n) 
• (D) The cost of searching an AVL tree is θ(n log n) but that of a binary search tree is O(n) 

Solution: AVL tree’s time complexity of searching, insertion and deletion = O(logn). But a binary search tree, may be skewed tree, so in worst case BST searching, insertion and deletion complexity = O(n). 

Que – 4. The worst case running time to search for an element in a balanced in a binary search tree with n*2^n elements is 

 Solution: Time taken to search an element is Θ(logn) where n is number of elements in AVL tree. As number of elements given is n*2^n, the searching complexity will be Θ(log(n*2^n)) which can be written as:

As logn is asymptotically smaller than n, Θ(log(n)) + Θ(n) can be written as Θ(n) which matches option C. 

Type 3: Insertion and Deletion in AVL tree – The question can be asked on the resultant tree when keys are inserted or deleted from AVL tree. Appropriate rotations need to be made if balance factor is disturbed. 

Que – 5. Consider the following AVL tree. 

 Which of the following is updated AVL tree after insertion of 70? 

Solution: The element is first inserted in the same way as BST. Therefore after insertion of 70, BST can be shown as: 

 However, balance factor is disturbed requiring RL rotation. To remove RL rotation, it is first converted into RR rotation as: 

 After removal of RR rotation, AVL tree generated is same as option (C).

Article Tags :