retagged by
508 views
0 votes
0 votes

Which of these statements is not true about an $AVL$ tree $T$ containing $n$ nodes?

  1. Rotations may be required during key insertion to keep $T$ balanced.
  2. The height of $T$ cannot exceed $1.5$ * $\log 2^{n}$ . And  It is possible to insert nodes into $T$ in $O$$\left ( \lg n \right )$ asymptotic algorithmic complexity.
  3. The number of interior nodes in $T$ cannot exceed the number of leaves in $T$.
  4. If each node in $T$ is augmented with an integer showing the size of that node’s sub-tree, then $T$ can be used to perform order statistic searches in $O$$\left ( \lg n \right )$ asymptotic algorithmic complexity.
retagged by

1 Answer

Best answer
2 votes
2 votes

C   The number of interior nodes in T can exceed the number of leaves in T .

 

edited by
Answer:

Related questions

1 votes
1 votes
1 answer
2
Bikram asked Jan 24, 2017
310 views
Suppose that six keys are inserted into an unbalanced binary search tree in the following order: $4, 6, 3, 8, 2$, and $5$.Then which of the following statements is/are co...
2 votes
2 votes
3 answers
4
learncp asked Jan 26, 2016
750 views
Insert the given values in the order in initially empty $\text{AVL}$ tree.$\text{34,21,10,27,24,43,15,6}$What is the value at the root of the tree$?$