Suppose T

is an initially empty search tree and we insert the sequence of n

keys $1,2,3,...,$n

$,$ in increasing order, into T

$.$ Then the height of the resulting search tree T

is

Question $6$Answer

a$.$

$\backslash$Theta $($n$)$

$,$ regardless of whether T

is a BST or a Splay tree or an AVL tree

b$.$

$\backslash$Theta $($logn$)$

$,$ regardless of whether T

is a Splay tree or an AVL tree

c$.$

$\backslash$Theta $($n$)$

if T

is a Splay tree, but is $\backslash$Theta $($logn$)$

if T

is an AVL tree

d$.$

$\backslash$Theta $($logn$)$

if T

is a Splay tree, but is $\backslash$Theta $($n$)$

if T

is a BST