The binary tree sort implemented using a self – balancing binary search tree takes……… time is worst case.
a) O(n log n)
b) O(n)
c) O(n2)
d) O(log n)
Explanation: The worst case running time of the binary tree sort is O(n2). But, the worst case running time can be improved to the O(n log n) using a self – balancing binary search tree.
An AVL tree is a self – balancing binary search tree, in which the heights of the two child sub trees of any node differ by
a) At least one
b) At most one
c) Two
d) At most two
Explanation: In an AVL tree, the difference between heights of the two child sub trees of any node is at most one. If the height differs by more than one, AVL tree performs rotations to balance the tree.
Associative arrays can be implemented using…
a) B-tree
b) A doubly linked list
c) A single linked list
d) A self-balancing binary search tree
Explanation: Associative arrays can be implemented using a self-balancing binary search tree as the worst-case time performance of self – balancing binary search trees is O(log n).
Which of the following is a self – balancing binary search tree?
a) 2-3 tree
b) Threaded binary tree
c) AA tree
d) Treap
Explanation: An AA tree, which is a variation of red-black tree, is a self – balancing binary search tree. 2-3 is B-tree of order 3 and Treat is a randomized binary search tree. A threaded binary tree is not a balanced tree.
A self – balancing binary search tree can be used to implement………
a) Priority queue
b) Hash table
c) Heap sort
d) Priority queue and Heap sort
In which of the following self – balancing binary search tree the recently accessed element can be accessed quickly?
a) AVL tree
b) AA tree
c) Splay tree
d) Red – Black tree
Explanation: In a Splay tree, the recently accessed element can be accessed quickly. In Splay tree, the frequently accessed nodes are moved towards the root so they are quick to access again.
