AA Tree Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “AA Tree”.

1. AA Trees are implemented using?
a) Colors
b) Levels
c) Node size
d) Heaps
View Answer

Answer: b
Explanation: AA Trees are implemented using levels instead of colors to overcome the disadvantages of Red-Black trees.

2. 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
View Answer

Answer: a
Explanation: A horizontal link is a connection between a node and a child of equal levels.

3. 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
View Answer

Answer: a
Explanation: A left horizontal link is removed by right rotation. A right horizontal link is removed by left rotation.
advertisement
advertisement

4. 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
View Answer

Answer: b
Explanation: A skew removes a left horizontal link by right rotation and a split removes a right horizontal link by left rotation.

5. In an AA-tree, we process split first, followed by a skew.
a) True
b) False
View Answer

Answer: b
Explanation: In an AA-tree, skew is processed first followed by a split.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. How many different shapes does maintenance of AA-Tree need to consider?
a) 7
b) 5
c) 2
d) 3
View Answer

Answer: c
Explanation: An AA-Tree needs to consider only two shapes unlike a red-black tree which needs to consider seven shapes of transformation.

7. 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
View Answer

Answer: a
Explanation: The prime condition of AA-Tree is that only the right children can be red to eliminate possible restructuring cases.
advertisement

8. 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
View Answer

Answer: d
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.

9. 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)
View Answer

Answer: b
Explanation: The worst case analysis of an AA-Tree is mathematically found to be O(log N).
advertisement

10. AA-Trees makes more rotations than a red-black tree.
a) True
b) False
View Answer

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
View Answer

Answer: a
Explanation: AA-tree is invented by Arne Anderson. Daniel Sleator invented Splay Tree. Rudolf Bayer invented a Red-Black tree. Jon Louis Bentley invented K-d tree.

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
View Answer

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
View Answer

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. In the given figure, find ‘?’.
B is initially the right child of X then rotated right side
a) left rotation
b) right rotation
c) insertion
d) deletion
View Answer

Answer: b
Explanation: B is initially the right child of X. It is then rotated right side and now, B is the left child of P.

15. 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
View Answer

Answer: a
Explanation: Since an AA-tree tends to be flatter, AA-tree has a faster search time than a Red-Black tree.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.