Q.1 What is the primary property of an AVL tree?
All leaves are at the same depth
The difference of heights of left and right subtrees of any node is at most 1
All keys are unique
Every node has two children
Explanation - An AVL tree maintains balance by ensuring that the heights of left and right subtrees of any node differ by at most 1, guaranteeing O(log n) height.
Correct answer is: The difference of heights of left and right subtrees of any node is at most 1
Q.2 Which operation may cause an AVL tree to perform a rotation?
Searching a node
Insertion or deletion
Finding minimum
Tree traversal
Explanation - Rotations in AVL trees are performed after insertions or deletions if the balance factor of any node becomes -2 or 2.
Correct answer is: Insertion or deletion
Q.3 What is the worst-case height of an AVL tree with n nodes?
O(n)
O(log n)
O(n log n)
O(√n)
Explanation - AVL trees are height-balanced, ensuring their height is proportional to O(log n) for n nodes.
Correct answer is: O(log n)
Q.4 Which of the following is true about a Red-Black tree?
It is always perfectly balanced
It allows O(log n) operations and maintains balance with colors
It is a binary search tree without balance
It allows duplicate keys in all cases
Explanation - Red-Black trees are binary search trees with additional color properties that ensure the tree remains approximately balanced, supporting O(log n) search, insert, and delete.
Correct answer is: It allows O(log n) operations and maintains balance with colors
Q.5 In a Red-Black tree, what is the color of the root node?
Red
Black
Can be red or black
Depends on tree height
Explanation - One of the properties of Red-Black trees is that the root is always black to help maintain balance.
Correct answer is: Black
Q.6 What is the minimum number of keys in a B-tree of order m and height h?
m^h
(2^(h-1))
2*(m^(h-1))
2*(ceil(m/2)^(h-1)) - 1
Explanation - In a B-tree, each node except root has at least ceil(m/2)-1 keys. This formula calculates the minimum number of keys based on height and order.
Correct answer is: 2*(ceil(m/2)^(h-1)) - 1
Q.7 Which rotation is required when a left-right imbalance occurs in an AVL tree?
Single left rotation
Single right rotation
Left-Right rotation
Right-Left rotation
Explanation - A left-right imbalance requires a double rotation: first left rotation on the left child, then right rotation on the root.
Correct answer is: Left-Right rotation
Q.8 Which of the following properties is NOT true for B-trees?
All leaves appear at the same level
Keys in a node are sorted
Internal nodes can have any number of children
The root has at least two children if not a leaf
Explanation - In a B-tree of order m, internal nodes can have at most m children and at least ceil(m/2) children (except root).
Correct answer is: Internal nodes can have any number of children
Q.9 What is the maximum height of a Red-Black tree with n nodes?
n
2*log2(n+1)
log2(n)
√n
Explanation - A Red-Black tree of n nodes has height at most 2*log2(n+1), ensuring logarithmic operations.
Correct answer is: 2*log2(n+1)
Q.10 What is the balance factor of a node in an AVL tree?
Height of left subtree minus height of right subtree
Number of nodes in left minus right subtree
Difference between maximum and minimum key
Level of node in tree
Explanation - Balance factor = height(left subtree) - height(right subtree). AVL trees maintain this value between -1 and 1.
Correct answer is: Height of left subtree minus height of right subtree
Q.11 What is the main advantage of using B-trees in databases?
Faster hash computation
Minimized disk reads
Simpler implementation
Supports unbalanced insertions
Explanation - B-trees are designed to reduce disk I/O by keeping nodes with multiple keys, ideal for large databases.
Correct answer is: Minimized disk reads
Q.12 Which case requires a right-left rotation in an AVL tree?
Left-Left imbalance
Left-Right imbalance
Right-Left imbalance
Right-Right imbalance
Explanation - A right-left imbalance requires a double rotation: first right rotation on right child, then left rotation on root.
Correct answer is: Right-Left imbalance
Q.13 How many children can a node in a B-tree of order m have?
At most m and at least 2
At most m-1 and at least 1
At most m and at least ceil(m/2)
Unlimited
Explanation - In a B-tree of order m, nodes (except root) have at least ceil(m/2) children and at most m children.
Correct answer is: At most m and at least ceil(m/2)
Q.14 Which of the following is true about Red-Black trees?
Every path from root to leaf has the same number of red nodes
No two red nodes can be adjacent
All leaves are red
Black nodes can have more than two children
Explanation - Red-Black trees maintain balance by ensuring no two consecutive red nodes exist in a path from root to leaf.
Correct answer is: No two red nodes can be adjacent
Q.15 In a B-tree, when a node is full, what happens during insertion?
Tree is deleted
Node is split
Insertion is ignored
Entire tree is rotated
Explanation - If a B-tree node is full, it splits and the middle key moves up to maintain order and balance.
Correct answer is: Node is split
Q.16 Which traversal is generally used to print keys of a Red-Black tree in sorted order?
Pre-order
Post-order
In-order
Level-order
Explanation - In-order traversal of any binary search tree, including Red-Black trees, prints keys in ascending order.
Correct answer is: In-order
Q.17 How many rotations are needed to fix a left-left imbalance in an AVL tree?
One right rotation
One left rotation
Left-Right rotation
Right-Left rotation
Explanation - A left-left imbalance requires a single right rotation to restore balance.
Correct answer is: One right rotation
Q.18 Which of these operations can be performed in O(log n) time in a Red-Black tree?
Search, insert, delete
Only search
Only insert
Only delete
Explanation - Red-Black trees maintain balance properties that allow search, insertion, and deletion in logarithmic time.
Correct answer is: Search, insert, delete
Q.19 Which property ensures that all leaves in a B-tree are at the same level?
Height-balance property
Node split property
Leaf level property
Binary search property
Explanation - B-trees maintain that all leaves appear at the same level, ensuring balanced tree height.
Correct answer is: Leaf level property
Q.20 In an AVL tree, the balance factor of a leaf node is:
1
0
-1
Can be any integer
Explanation - Leaf nodes have no children, so their left and right subtree heights are zero; balance factor = 0.
Correct answer is: 0
Q.21 What is the key difference between AVL and Red-Black trees?
AVL is height-balanced, Red-Black is color-balanced
AVL is unordered, Red-Black is ordered
AVL allows duplicate keys, Red-Black does not
No difference
Explanation - AVL trees maintain strict height balance, while Red-Black trees use colors to enforce approximate balance.
Correct answer is: AVL is height-balanced, Red-Black is color-balanced
Q.22 Which of the following is true about the height of a B-tree?
It is always logarithmic in the number of keys
It is linear in the number of keys
It is constant
It is equal to the order of the tree
Explanation - B-trees grow slowly in height due to multiple keys per node, ensuring height is logarithmic in the number of keys.
Correct answer is: It is always logarithmic in the number of keys
Q.23 In a Red-Black tree, if a newly inserted node is red and its parent is red, which property is violated?
Root is black
No two red nodes in a row
Black height property
BST property
Explanation - Red-Black property prevents two consecutive red nodes; inserting a red child to a red parent violates this rule.
Correct answer is: No two red nodes in a row
Q.24 In an AVL tree, if a node has a balance factor of -2, what does it indicate?
Left-heavy imbalance
Right-heavy imbalance
Perfectly balanced
Node is a leaf
Explanation - Balance factor = height(left) - height(right). BF = -2 means the right subtree is heavier, requiring rotation.
Correct answer is: Right-heavy imbalance