retagged by
390 views
1 votes
1 votes

In a height balanced binary search tree, the heights of the left and right descendants of any node differ at most by $1.$ Which of the following statements are TRUE for such kind of tree?

  1. Worst case search time is logarithmic in the number of nodes.
  2. Average case search time is logarithmic in the number of nodes.  
  3. Best case search time is proportional to the height of the tree.
  4. The height of the tree is logarithmic in the number of nodes.
  1. II and IV only
  2. I, II and IV
  3. I and III only
  4. I, III and IV
retagged by

1 Answer

Best answer
2 votes
2 votes

In a height balanced binary search tree, the heights of the left and right descendants of any node differ by at most 1.

This is the definition of $AVL$ tree which is also known as Balanced Binary Search tree.

In this height of the tree: $O$$\left ( \log n \right )$

worst case and complexity of searching an element in $AVL$ tree: $O$$\left ( \log n \right )$

Average case complexity of searching an element in $AVL$ tree: $\Theta \left ( \log n \right )$

so option  $B$

edited by
Answer:

Related questions

2 votes
2 votes
1 answer
1
Bikram asked May 14, 2017
655 views
The worst case running time to search for an element in binary search tree with $2^{\log_2 n}$ elements is represented as $\Theta\left(n^{x \log_2 y}\right)$ .The value o...