This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “AA Tree”.
1. Comparing the speed of execution of Red-Black trees and AA-trees, which one has the faster search time?
B) Red-Black tree
C) Both have an equal search time
D) It depends
Explanation: Since an AA-tree is flatter than a Red-Black tree, it has a faster search time.
2. In the given figure, find ‘?’.
A) left rotation
B) right rotation
Explanation: B is initially the right child of X. It is then rotated right side and now, B is the left child of P.
3. How many different shapes does maintenance of AA-Tree need to consider?
Explanation: Unlike a red-black tree, which must consider seven transformation shapes, an AA-Tree only needs to consider two.
4. 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: To remove potential restructuring scenarios, AA-Tree requires that only the appropriate children be red.
5. 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: The AA- Tree is a subspecies of the Red-Black Tree. The difficulty of performing insertion and deletion in Red-Black Trees is solved by AA-Trees.
6. What is the worst case analysis of an AA-Tree?
B) O(log N)
C) O( N log N)
Explanation: The worst-case study of an AA-Tree is considered to be O mathematically (log N).
7. AA-Trees makes more rotations than a red-black tree.
Explanation: Since only two shapes are considered in an AA-Tree, while seven shapes are considered in Red-Black trees, AA-Trees make more rotations than Red-Black trees.
8. Who is the inventor of AA-Tree?
A) Arne Anderson
B) Daniel Sleator
C) Rudolf Bayer
D) Jon Louis Bentley
Explanation: Arne Anderson is the creator of the AA-tree. Stretch Tree was created by Daniel Sleator. A Red-Black tree was created by Rudolf Bayer. The K-d tree was created by Jon Louis Bentley.
9. 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
Explanation: A left node’s level should be strictly lower than that of its parent. A right node’s level is lower than or equal to that of its parent.
10. 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
Explanation: Both left and right children can be found in an AA-Tree. The only stipulation is that only the right children are allowed to be red.
11. 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 connection is a link between a node and a child with the same level as the node.
12. 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: Right rotation removes a left horizontal relation. Left rotation removes a right horizontal relation.
13. 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 rotates a left horizontal link to the right, while a split rotates a right horizontal link to the left.
14. In an AA-tree, we process split first, followed by a skew.
Explanation: The skew is processed first in an AA-tree, followed by the break.
15. AA Trees are implemented using?
C) Node size
Explanation: .To solve the drawbacks of Red-Black trees, AA Trees are implemented using levels rather than colours.
In computer science, an AA tree is a type of balanced tree that is used to efficiently store and retrieve ordered data. Arne Andersson, the tree’s inventor, is honoured with the name AA. The AA tree is a variant of the red-black tree, a type of binary search tree that allows for efficient entry addition and deletion. The deletion of an internal node may be transformed into the deletion of a leaf node, as in most balanced binary trees, by swapping the internal node with either its nearest predecessor or successor, depending on which is in the tree or on the implementor’s desires.