AVL Tree

Question

The minimum number of node in an AVL Tree of height $10$ is ____________

Comments

n(h)=n(h-1)+1+n(h-2)

       =1        h=0

        =2       h=1

use this u will get the answer

---

assuming height 0 having 1 node & using h(n)=h(n-1)+h(n-2)+1 recursively h(10)=232.

---

thanks

Answer 1

AVL Tree: 

• AVL tree is the self-balancing Binary Search Tree.
• In an AVL tree, the heights of the two child subtrees of any node differ by at most one.
  • Height(LST)-Height(RST) =−1,0,1
• Rebalancing is needed at any time if they differ by more than one.

Using the recursive function N(h) = 1 + N(h-1) + N(h-2) we can find the minimum number of nodes in any given AVL tree of height h.

• We know that 
  • N(0) = 1
  • N(1) = 2
  • N(2) = 4
  • N(3) = 1 + N(2) + N(1)
    • => 1 + 2 + 4 = 7
  • N(4) = 1 + N(3) + N (2)
    • => 1 + 7 + 4 = 12
  • N(5) = 1 + N(4) + N(3)
    • => 1 + 12 + 7 = 20
  • N(6) = 1 + N(5) + N(4)
    • => 1 + 20 + 12 = 33
  • N(7) = 1 + N(6) + N(5)
    • => 1 + 33 + 20 = 54
  • N(8) = 1 + N(7) + N(6)
    • => 1 + 54 + 33 = 88
  • N(9) = 1 + N(8) + N(7)
    • => 1 + 88 + 54 = 143
  • N(10) = 1 + N(9) + N(8)
    • => 1 + 143 + 88 = 232

Comments

In AVL Tree Height(LST)-Height(RST) $= {-1,0,1}$

Otherwise Rebalancing is needed.

---

Yep. Added this point to the answer :)