What are the two different operations done in an AA-Tree?
a) shift and color
b) skew and split
c) zig and zag
d) enqueue and dequeue
Explanation: A skew removes a left horizontal link by right rotation and a split removes a right horizontal link by left rotation.
In an AA-tree, we process split first, followed by a skew.
a) True
b) False
Explanation: In an AA-tree, skew is processed first followed by a split.
How many different shapes does maintenance of AA-Tree need to consider?
a) 7
b) 5
c) 2
d) 3
Explanation: An AA-Tree needs to consider only two shapes unlike a red-black tree which needs to consider seven shapes of transformation.
What is the prime condition of AA-tree which makes it simpler than
a red-black tree?
a) Only right children can be red
b) Only left children can be red
c) Right children should strictly be black
d) There should be no left children
Explanation: The prime condition of AA-Tree is that only the right children can be red to eliminate possible restructuring cases.
Which of the following trees is similar to that of an AA-Tree?
a) Splay Tree
b) B+ Tree
c) AVL Tree
d) Red-Black Tree
Explanation: AA- Tree is a small variation of Red-Black tree. AA-Trees overcome the complexity faced in performing insertion and deletion in Red-Black Trees.
What is the worst case analysis of an AA-Tree?
a) O(N)
b) O(log N)
c) O( N log N)
d) O(N2)
Explanation: The worst case analysis of an AA-Tree is mathematically found to be O(log N).
