Questions
41
Suppose a binary tree is constructed with n nodes, such that each node has exactly either zero or two children. The maximum height of the tree will be?
Answer: (n-1)/2
42
The worst case height of an AVL tree with n nodes is ……………
Answer: 1.44 lg n
43
An insertion into a ……………………….. is performed by inserting the new node in the location referenced by next in the array and then “sifting it up” by comparing the key of the newly inserted node with the key of the parent.
Answer: Binary Heap
44
In a …………………….. for every node X with a parent P, the key in P is less than or equal to the key in X.
Answer: Binary Heap
45
For an AVL tree ………………………….. is the additional piece of information which indicates if the difference in height between the left and right subtree is the same or if not, which of the two subtrees has height one unit larger.
Answer: Balance Factor
46
While inserting into ………………………….., insertions are done at a leaf and will replace an external node with an internal node with two external children.
Answer: Red-Black Tree
47
Which of the following is/are properties of red-black tree.
i) every node is either red or black ii) the root is red iii) If a node is red, then both its children are black iv) every leaf is black
Answer: i, iii and iv only
48
A lemma is a red-black tree with n internal nodes has height at most ……………
Answer: 2lg(n+1)
49
…………………………… is a binary search tree whose left subtree and right subtree differ in height by at most 1 unit and whose left and right subtrees are themselves AVL trees.
Answer: AVL Tree
50
In binary search tree, a …………………… rooted to node n is the tree formed by imaging node n was a root.
Answer: subtree
51
The order with which the nodes are inserted affects the running time of the ……………………. search algorithm.
Answer: Binary Heap Tree
52
In the best case of BST, the time is on the order of ……………………, but in the worst case it requires linear time.
Answer: log₂n
