Before you go through this article, make sure that you have gone through the previous article on AVL Trees. Show We have discussed-
In this article, we will discuss AVL Tree Properties. AVL Tree Properties-Important properties of AVL tree are- Property-01:
Example-Maximum possible number of nodes in AVL tree of height-3 = 23+1 – 1 = 16 – 1 = 15 Thus, in AVL tree of height-3, maximum number of nodes that can be inserted = 15. We can not insert more number of nodes in this AVL tree. Property-02:
Base conditions for this recursive relation are- Example-Minimum possible number of nodes in AVL tree of height-3 = 7 (For explanation, Refer problem-01) Property-03:
Example-Minimum possible height of AVL Tree using 8 nodes = ⌊log28⌋ = ⌊log223⌋ = ⌊3log22⌋ = ⌊3⌋ = 3 Property-04:
Base conditions for this recursive relation are- NOTE-
PRACTICE PROBLEMS BASED ON AVL TREE PROPERTIES-Problem-01:Find the minimum number of nodes required to construct AVL Tree of height = 3. Solution-We know, minimum number of nodes in AVL tree of height H is given by a recursive relation-
where N(0) = 1 and N(1) = 2 Step-01:Substituting H = 3 in the recursive relation, we get- N(3) = N(3-1) + N(3-2) + 1 N(3) = N(2) + N(1) + 1 N(3) = N(2) + 2 + 1 (Using base condition) N(3) = N(2) + 3 …………(1) To solve this recursive relation, we need the value of N(2). Step-02:Substituting H = 2 in the recursive relation, we get- N(2) = N(2-1) + N(2-2) + 1 N(2) = N(1) + N(0) + 1 N(2) = 2 + 1 + 1 (Using base conditions) ∴ N(2) = 4 …………(2) Step-03:Using (2) in (1), we get- N(3) = 4 + 3 ∴ N(3) = 7 Thus, minimum number of nodes required to construct AVL tree of height-3 = 7. Problem-02:Find the minimum number of nodes required to construct AVL Tree of height = 4. Solution-We know, minimum number of nodes in AVL tree of height H is given by a recursive relation-
where N(0) = 1 and N(1) = 2 Step-01:Substituting H = 4 in the recursive relation, we get- N(4) = N(4-1) + N(4-2) + 1 N(4) = N(3) + N(2) + 1 …………(1) To solve this recursive relation, we need the value of N(2) and N(3). Step-02:Substituting H = 2 in the recursive relation, we get- N(2) = N(2-1) + N(2-2) + 1 N(2) = N(1) + N(0) + 1 N(2) = 2 + 1 + 1 (Using base conditions) ∴ N(2) = 4 …………(2) Step-03:Substituting H = 3 in the recursive relation, we get- N(3) = N(3-1) + N(3-2) + 1 N(3) = N(2) + N(1) + 1 N(3) = 4 + 2 + 1 (Using (2) and base condition) ∴ N(3) = 7 …………(3) Step-04:Using (2) and (3) in (1), we get- N(4) = 7 + 4 + 1 ∴ N(4) = 12 Thus, minimum number of nodes required to construct AVL tree of height-4 = 12. Problem-03:What is the maximum height of any AVL tree with 10 nodes? Solution-For calculating the maximum height of AVL tree with n nodes, we use a recursive relation-
Step-01:Substituting H = 2 in the recursive relation, we get- N(2) = N(2-1) + N(2-2) + 1 N(2) = N(1) + N(0) + 1 N(2) = 2 + 1 + 1 (Using base conditions) ∴ N(2) = 4 …………(1) So, minimum number of nodes required to construct AVL tree of height-2 = 4. Step-02:Substituting H = 3 in the recursive relation, we get- N(3) = N(3-1) + N(3-2) + 1 N(3) = N(2) + N(1) + 1 N(3) = 4 + 2 + 1 (Using (1) and base condition) ∴ N(3) = 7 …………(2) So, minimum number of nodes required to construct AVL tree of height-3 = 7. Step-03:Substituting H = 4 in the recursive relation, we get- N(4) = N(4-1) + N(4-2) + 1 N(4) = N(3) + N(2) + 1 N(4) = 7 + 4 + 1 (Using (1) and (2)) ∴ N(4) = 12 So, minimum number of nodes required to construct AVL tree of height-4 = 12. But given number of nodes = 10 which is less than 12. Thus, maximum height of AVL tree that can be obtained using 10 nodes = 3. Problem-04:What is the maximum height of any AVL tree with 77 nodes? Solution-For calculating the maximum height of AVL tree with n nodes, we use a recursive relation-
Step-01:Substituting H = 2 in the recursive relation, we get- N(2) = N(2-1) + N(2-2) + 1 N(2) = N(1) + N(0) + 1 N(2) = 2 + 1 + 1 (Using base conditions) ∴ N(2) = 4 …………(1) So, minimum number of nodes required to construct AVL tree of height-2 = 4. Step-02:Substituting H = 3 in the recursive relation, we get- N(3) = N(3-1) + N(3-2) + 1 N(3) = N(2) + N(1) + 1 N(3) = 4 + 2 + 1 (Using (1) and base condition) ∴ N(3) = 7 …………(2) So, minimum number of nodes required to construct AVL tree of height-3 = 7. Step-03:Substituting H = 4 in the recursive relation, we get- N(4) = N(4-1) + N(4-2) + 1 N(4) = N(3) + N(2) + 1 N(4) = 7 + 4 + 1 (Using (1) and (2)) ∴ N(4) = 12 …………(3) So, minimum number of nodes required to construct AVL tree of height-4 = 12. Step-04:Substituting H = 5 in the recursive relation, we get- N(5) = N(5-1) + N(5-2) + 1 N(5) = N(4) + N(3) + 1 N(5) = 12 + 7 + 1 (Using (2) and (3)) ∴ N(5) = 20 …………(4) So, minimum number of nodes required to construct AVL tree of height-5 = 20. Step-05:Substituting H = 6 in the recursive relation, we get- N(6) = N(6-1) + N(6-2) + 1 N(6) = N(5) + N(4) + 1 N(6) = 20 + 12 + 1 (Using (3) and (4)) ∴ N(6) = 33 …………(5) So, minimum number of nodes required to construct AVL tree of height-6 = 33. Step-06:Substituting H = 7 in the recursive relation, we get- N(7) = N(7-1) + N(7-2) + 1 N(7) = N(6) + N(5) + 1 N(7) = 33 + 20 + 1 (Using (4) and (5)) ∴ N(7) = 54 …………(6) So, minimum number of nodes required to construct AVL tree of height-7 = 54. Step-07:Substituting H = 8 in the recursive relation, we get- N(8) = N(8-1) + N(8-2) + 1 N(8) = N(7) + N(6) + 1 N(8) = 54 + 33 + 1 (Using (5) and (6)) ∴ N(8) = 88 …………(6) So, minimum number of nodes required to construct AVL tree of height-8 = 88. But given number of nodes = 77 which is less than 88. Thus, maximum height of AVL tree that can be obtained using 77 nodes = 7. Next Article- Insertion in AVL Tree Get more notes and other study material of Data Structures. Watch video lectures by visiting our YouTube channel LearnVidFun. |