What is the range of β in finding the length of the longest path in
a randomized binary search tree?
a) (-1, 0)
b) (1, 0)
c) (0, 5)
d) (0, 1)
What is the expected number of leaves in a randomized binary search
tree?
a) n + 1
b) (n + 1)/3
c) (n + 1)/2
d) n + 3
Explanation: In a random mathematical model, the expected value of number of leaves in a randomized binary search tree is found to be exactly (n + 1)/3 using probability.
What is the probability of selecting a tree uniformly at random?
a) Equal to Catalan Number
b) Less Than Catalan Number
c) Greater than Catalan Number
d) Reciprocal of Catalan Number
AA Trees are implemented using?
a) Colors
b) Levels
c) Node size
d) Heaps
Explanation: AA Trees are implemented using levels instead of colors to overcome the disadvantages of Red-Black trees.
Which of the following is the correct definition for a horizontal link?
a) connection between node and a child of equal levels
b) connection between two nodes
c) connection between two child nodes
d) connection between root node and leaf node
Explanation: A horizontal link is a connection between a node and a child of equal levels.
How will you remove a left horizontal link in an AA-tree?
a) by performing right rotation
b) by performing left rotation
c) by deleting both the elements
d) by inserting a new element
Explanation: A left horizontal link is removed by right rotation. A right horizontal link is removed by left rotation.
