1. What is the special property of red-black trees and what root should always be?
a) a color which is either red or black and root should always be black color only
b) height of the tree
c) pointer to next node
d) a color which is either green or black
Answer: a
Explanation:
An extra attribute which is a color red or black is used. root is black because if it is red then one of red-black tree property which states that number of black nodes from root to null nodes must be same, will be violated.
2. Why do we impose restrictions like
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black
a) to get logarithm time complexity
b) to get linear time complexity
c) to get exponential time complexity
d) to get constant time complexity
Answer: a
Explanation:
We impose such restrictions to achieve self balancing trees with logarithmic complexities for insertions, deletions, search.
3. What are the operations that could be performed in O(logn) time complexity by red-black tree?
a) insertion, deletion, finding predecessor, successor
b) only insertion
c) only finding predecessor, successor
d) for sorting
Answer: a
Explanation:
We impose restrictions to achieve logarithm time complexities.
impose restrictions are:
. root property is black
. every leaf is black
. children of red node are black
. all leaves have same black.
4. Which of the following is an application of Red-black trees and why?
a) used to store strings efficiently
b) used to store integers efficiently
c) can be used in process schedulers, maps, sets
d) for efficient sorting
Answer: c
Explanation:
RB tree is used for Linux kernel in the form of completely fair scheduler process scheduling algorithm. It is used for faster insertions, retrievals.
5. When it would be optimal to prefer Red-black trees over AVL trees?
a) when there are more insertions or deletions
b) when more search is needed
c) when tree must be balanced
d) when log(nodes) time complexity is needed
Answer: a
Explanation:
Though both trees are balanced, when there are more insertions and deletions to make the tree balanced, AVL trees should have more rotations, it would be better to use red-black. but if more search is required AVL trees should be used.
6. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?
a) no they are not preferred
b) because of resizing issues of hash table and better ordering in redblack trees
c) because they can be implemented using trees
d) because they are balanced
Answer: b
Explanation:
Redblack trees have O(logn) for ordering elements in terms of finding first and next elements. also whenever table size increases or decreases in hash table you need to perform rehashing which can be very expensive in real time. also red black stores elements in sorted order rather than input order.
7. How can you save memory when storing color information in Red-Black tree?
a) using least significant bit of one of the pointers in the node for color information
b) using another array with colors of each node
c) storing color information in the node structure
d) using negative and positive numbering
Answer: a
Explanation:
The node pointers can be used to store color with the help of significant bits. the exceptions of this method are in languages like java where pointers are not used this may not work.
8. When to choose Red-Black tree, AVL tree and B-trees?
a) many inserts, many searches and when managing more items respectively
b) many searches, when managing more items respectively and many inserts respectively
c) sorting, sorting and retrieval respectively
d) retrieval, sorting and retrieval respectively
Answer: a
Explanation:
Red black when frequent inserts and deletes, AVL when less frequent inserts and deletes, B-tree when using paging from a slow storage device.
9. What is the below pseudo code trying to do, where pt is a node pointer and root pointer?
redblack(Node root, Node pt) :
if (root == NULL)
return pt
if (pt.data < root.data)
{
root.left = redblack(root.left, pt);
root.left.parent = root
}
else if (pt.data > root.data)
{
root.right = redblackt(root.right, pt)
root.right.parent = root
}
return root
a) insert a new node
b) delete a node
c) search a node
d) count the number of nodes
Answer: a
Explanation:
The code is taking the root node and to be inserted node and is performing insertion operation.
10. Elements in a tree can be indexed by its position under the ordering of the keys and the ordinal position of an element can be determined, both with good efficiency.
a) true
b) false
Answer: a
Explanation:
AA- trees make more rotations than a red-black tree since only two shapes are considered for an AA-Tree whereas seven shapes are considered in Red-Black trees.
11. Who is the inventor of AA-Tree?
a) Arne Anderson
b) Daniel Sleator
c) Rudolf Bayer
d) Jon Louis Bentley
Answer: a
Explanation:
In a weight balanced tree we can even store the key information so as to use as a key value pair.
12. What should be the condition for the level of a left node?
a) It should be less than or equal to that of its parent
b) It should be greater than that of its parent
c) It should be strictly less than that of its parent
d) The level should be equal to one
Answer: c
Explanation:
The level of a left node should be strictly less than that of its parent. The level of a right node is less than or equal to that of its parent.
13. Of the following rules that are followed by an AA-tree, which of the following is incorrect?
1- Only right children can be red
2- Procedures are coded recursively
3- Instead of storing colors, the level of a node is stored
4- There should not be any left children
a) 1
b) 2
c) 3
d) 4
Answer: d
Explanation:
In an AA-Tree, both left and right children can be present. The only condition is that only right children can be red.
14. Comparing the speed of execution of Red-Black trees and AA-trees, which one has the faster search time?
a) AA-tree
b) Red-Black tree
c) Both have an equal search time
d) It depends
Answer: a
Explanation:
Since an AA-tree tends to be flatter, AA-tree has a faster search time than a Red-Black tree.
15. What is the time complexity of the juggling algorithm to rotate an array?
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
Answer: b
Explanation:
Time complexity of juggling algorithm is O(n). Its auxiliary space complexity is O(1).
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
