Balanced Trees (Intro) Quiz
40 comprehensive questions exploring balanced tree concepts — with 16 code examples covering height balancing, AVL trees, red-black trees, rotations, and balance factors in this cpp quiz.
40 Questions
~80 minutes
1
Question 1
Why do trees need balancing?
A
To prevent performance degradation where unbalanced trees can become skewed like linked lists, causing operations to degrade from O(log n) to O(n) worst-case time complexity, ensuring consistent logarithmic performance regardless of insertion order
B
To use less memory
C
To make trees complete
D
To allow duplicate values
2
Question 2
What is height balance in trees?
text
Height balanced: difference in subtree heights
Is limited to prevent skewingA
A tree where the height difference between left and right subtrees of any node is bounded by a constant (usually 1 or 2), ensuring the tree remains approximately balanced and operations maintain logarithmic time complexity
B
All subtrees have the same height
C
The tree is perfectly balanced
D
No height restrictions
3
Question 3
What is the balance factor in AVL trees?
A
The difference between the height of the right subtree and the height of the left subtree for each node, which must be -1, 0, or +1 to maintain AVL balance, triggering rotations when this invariant is violated
B
The number of nodes in the tree
C
The depth of the node
D
The value stored in the node
4
Question 4
How do rotations fix tree imbalance?
text
Left rotation: right child becomes parent
Right rotation: left child becomes parentA
By restructuring the tree locally around an unbalanced node, changing the parent-child relationships to reduce height differences while preserving the binary search tree property and maintaining the inorder traversal order
B
By changing node values
C
By adding new nodes
D
By removing nodes
5
Question 5
What is an AVL tree?
A
A self-balancing binary search tree where the balance factor of every node is -1, 0, or +1, ensuring height is O(log n) and all operations maintain logarithmic time complexity through automatic rotations
B
A tree with no balance requirements
C
A complete binary tree
D
A tree that allows duplicates
6
Question 6
What are the red-black tree properties?
text
Red-black properties:
1. Nodes are red or black
2. Root is black
3. Red nodes have black children
4. All paths have same black heightA
Every node is colored red or black, the root is black, red nodes cannot have red children, and all paths from root to leaves have the same number of black nodes, ensuring the tree remains balanced with height at most 2*log(n+1)
B
All nodes are the same color
C
Colors determine node values
D
No color restrictions
7
Question 7
What is a left rotation in tree balancing?
A
A restructuring operation where the right child of a node becomes the new root of the subtree, the original root becomes the left child of the new root, and the left child of the right child (if any) becomes the right child of the original root
B
Rotating the tree 90 degrees left
C
Moving all nodes left
D
Changing node colors
8
Question 8
How does AVL insertion maintain balance?
cpp
After insertion: update heights, check balance
If |balance| > 1, perform rotationsA
By updating height information during insertion and checking balance factors along the path to the root, performing appropriate rotations (single or double) when any node's balance factor exceeds ±1 to restore the AVL property
B
By rebuilding the tree
C
By ignoring balance
D
By using red-black properties
9
Question 9
What is the maximum height of a red-black tree with n nodes?
A
At most 2*log2(n+1), due to the red-black properties that limit how unbalanced the tree can become, ensuring worst-case logarithmic height while being more relaxed than AVL trees for better average performance
B
log2(n)
C
n-1
D
2*n
10
Question 10
What is a right rotation?
text
Right rotation: left child becomes parent
Original parent becomes right childA
A tree restructuring where the left child becomes the new root of the subtree, the original root becomes the right child of the new root, and the right child of the left child (if any) becomes the left child of the original root
B
Rotating the tree 90 degrees right
C
Moving all nodes right
D
Changing node values
11
Question 11
What is the advantage of red-black trees over AVL trees?
A
Red-black trees require fewer rotations on average for insertions and deletions due to their more relaxed balance criteria, providing better performance for applications with frequent modifications while still guaranteeing O(log n) operations
B
Red-black trees are faster for searches
C
Red-black trees use less memory
D
AVL trees are always better
12
Question 12
How do double rotations work in AVL trees?
text
Left-right rotation: first left on left child
Then right on parentA
When a single rotation isn't sufficient, double rotations combine two rotations: left-right rotation (left rotation on child followed by right rotation on parent) or right-left rotation (right rotation on child followed by left rotation on parent) to fix complex imbalances
B
Two rotations on the same node
C
Rotations in opposite directions
D
Double rotations don't exist
13
Question 13
What is the balance factor calculation?
A
Balance factor = height(right subtree) - height(left subtree), where the result must be -1, 0, or +1 for AVL trees, with deviations triggering rotations to restore the balance invariant throughout the tree
B
Number of nodes in subtrees
C
Depth of the node
D
Node value difference
14
Question 14
In red-black trees, what does the black height property ensure?
text
Black height: number of black nodes on any path
Must be same for all root-to-leaf pathsA
All paths from root to leaves have the same number of black nodes, which bounds the maximum height of the tree and ensures that the longest path is at most twice the length of the shortest path in the tree
B
All nodes are black
C
The tree is perfectly balanced
D
No red nodes exist
15
Question 15
What is the time complexity of AVL tree operations?
A
O(log n) for search, insert, and delete operations due to the strict height balancing that guarantees the tree height remains logarithmic, with rotations adding only constant factors to the operation time
B
O(n)
C
O(1)
D
O(n log n)
16
Question 16
How does red-black tree insertion handle color conflicts?
cpp
After insertion: recolor and rotate
Fix red-red violations and black heightA
By performing recoloring and rotations to fix violations of the red-black properties, ensuring that red nodes don't have red children and maintaining equal black heights on all paths from root to leaves
B
By changing all colors
C
By removing nodes
D
By ignoring colors
17
Question 17
What is the significance of tree balancing in algorithm design?
A
Balanced trees provide guaranteed worst-case performance for dictionary operations, making them suitable for applications requiring predictable timing behavior and preventing performance degradation from adversarial input sequences
B
They are faster than unbalanced trees
C
They use less memory
D
They are easier to implement
18
Question 18
How do rotations preserve the BST property?
text
Rotation maintains inorder: left < parent < right
Order preserved through restructuringA
By rearranging nodes in a way that maintains the relative ordering of all elements, ensuring that the inorder traversal remains unchanged and the binary search tree property is preserved throughout the rotation operation
B
By changing node values
C
By adding new nodes
D
By violating BST properties
19
Question 19
What is the trade-off between AVL and red-black trees?
A
AVL trees provide stricter balance for slightly better search performance but require more rotations during modifications, while red-black trees allow more imbalance for fewer rotations and better modification performance with slightly worse search constants
B
AVL trees are always faster
C
Red-black trees are always faster
D
They have identical performance
20
Question 20
In AVL trees, when do you perform a left-right double rotation?
text
Left-right case: insertion in right subtree of left child
Causes balance factor -2, +1 patternA
When the balance factor of a node is -2 and the balance factor of its left child is +1, indicating that the insertion occurred in the right subtree of the left child, requiring a left rotation followed by a right rotation to restore balance
B
When the tree is left-heavy
C
When the tree is right-heavy
D
Double rotations are never needed
21
Question 21
What is the red-black tree recoloring process?
A
Changing the colors of nodes to fix red-black violations, such as changing red nodes to black or vice versa, which can resolve some imbalances without requiring rotations while maintaining the black height property
B
Making all nodes red
C
Making all nodes black
D
Removing colors
22
Question 22
How does height balancing prevent worst-case scenarios?
text
Height h ≤ c*log n
Prevents linked-list degradationA
By ensuring the tree height remains logarithmic regardless of insertion order, preventing the O(n) worst-case performance that occurs when unbalanced trees degenerate into linked lists with poor height-to-node ratios
B
By making trees complete
C
By limiting node values
D
By allowing only sorted insertions
23
Question 23
What is the balance factor range for AVL trees?
A
Balance factors must be -1, 0, or +1 for every node, with any deviation triggering immediate rotations to restore the invariant, ensuring the tree remains strictly height-balanced with optimal search performance
B
Any integer value
C
Only 0
D
No restrictions
24
Question 24
In red-black trees, why are rotations needed?
text
Rotations fix structural imbalances
After recoloring attempts failA
To restructure the tree when recoloring alone cannot fix violations of the red-black properties, particularly when maintaining equal black heights requires changing the tree topology to balance the black node distribution
B
To change node colors
C
To add new nodes
D
Rotations are not needed in red-black trees
25
Question 25
What is the practical difference between AVL and red-black trees?
A
AVL trees are more rigidly balanced with stricter height limits, making them better for read-heavy workloads, while red-black trees allow more flexibility for write-heavy workloads due to fewer rotations during modifications
B
AVL trees are always used
C
Red-black trees are always used
D
They are identical in practice
26
Question 26
How do rotations affect subtree heights?
text
Single rotation: may decrease height by 1
Double rotation: adjusts heights appropriatelyA
Rotations can reduce the height of the subtree by reorganizing the nodes, with single rotations potentially decreasing height by 1 and double rotations ensuring proper height adjustments to maintain the balance invariants of the tree structure
B
Rotations always increase height
C
Rotations have no effect on height
D
Rotations double the height
27
Question 27
What is the black height in red-black trees?
A
The number of black nodes on any path from a node to a leaf in its subtree, which must be the same for all paths from that node, ensuring local balance and contributing to the global height bound of the tree
B
The total number of black nodes
C
The height of black subtrees
D
The number of red nodes
28
Question 28
In AVL trees, what triggers a right-left double rotation?
text
Right-left case: insertion in left subtree of right child
Balance factor +2, -1 patternA
When the balance factor of a node is +2 and the balance factor of its right child is -1, indicating insertion in the left subtree of the right child, requiring a right rotation followed by a left rotation to restore proper balance
B
When the tree is perfectly balanced
C
When all nodes are balanced
D
Right-left rotations don't exist
29
Question 29
What is the amortized cost of red-black tree operations?
A
O(log n) amortized time for insertions and deletions due to the bounded number of recoloring and rotation operations that occur during any single operation, with the red-black properties ensuring that rebalancing costs are absorbed over multiple operations
B
O(1)
C
O(n)
D
O(log n) worst-case
30
Question 30
How do balanced trees compare to hash tables?
text
Balanced trees: ordered, log n worst-case
Hash tables: average O(1), no orderA
Balanced trees provide ordered operations with guaranteed worst-case performance, while hash tables offer average-case constant time but no ordering guarantees and potential worst-case degradation, making trees preferable for ordered data requirements
B
Hash tables are always better
C
Balanced trees are always better
D
They are identical
31
Question 31
What is the role of rotations in maintaining balance?
A
Rotations serve as the primary mechanism for restructuring unbalanced trees, reducing height differences by changing parent-child relationships locally while preserving the binary search tree ordering and balance invariants of the data structure
B
To change node values
C
To add balance factors
D
Rotations don't affect balance
32
Question 32
In red-black trees, what does the red property prevent?
text
No two adjacent red nodes
Prevents long red paths that could unbalanceA
Long chains of red nodes that would create unbalanced paths, as red nodes must have black children, ensuring that no path is more than twice as long as any other path in terms of red node count
B
Black nodes from existing
C
The tree from being balanced
D
Red property allows anything
33
Question 33
What is the height guarantee of AVL trees?
A
AVL trees guarantee that the height is at most 1.44*log2(n+2), providing the most balanced binary search trees with optimal worst-case height bounds for search operations among self-balancing BST variants
B
Height is always log2(n)
C
Height can be n-1
D
No height guarantee
34
Question 34
How does red-black tree deletion maintain properties?
text
Deletion: remove node, fix double black
Recolor and rotate to restore invariantsA
By handling the removal of nodes while fixing potential double-black violations through recoloring and rotations, ensuring that all red-black properties are maintained and the tree remains balanced after deletion operations
B
By rebuilding the tree
C
By ignoring properties
D
Deletion doesn't affect properties
35
Question 35
What is the significance of the root being black in red-black trees?
A
The black root ensures that the longest path (with alternating colors) is at most twice the shortest path (all black), contributing to the height bound and making the tree suitable for guaranteeing logarithmic performance in all operations
B
It makes the tree faster
C
It uses less memory
D
The root color doesn't matter
36
Question 36
How do balance factors help in tree operations?
text
Balance factor = height(R) - height(L)
Check |bf| <= 1 for AVLA
Balance factors provide a local measure of tree balance at each node, allowing quick detection of imbalances during insertions and deletions, triggering appropriate rotations to maintain the global balance invariant efficiently
B
They store node values
C
They count children
D
Balance factors are not useful
37
Question 37
What is the practical impact of tree balancing on performance?
A
Balanced trees prevent performance degradation from skewed inputs, ensuring consistent logarithmic performance for database operations, file systems, and other applications requiring reliable worst-case bounds for search and modification operations
B
They make operations slower
C
They increase memory usage significantly
D
They have no impact
38
Question 38
In red-black trees, what is the relationship between colors and balance?
text
Colors enforce balance indirectly
Black height ensures bounded heightA
Colors work together with the black height property to ensure balance, where the color constraints prevent excessive imbalances and the equal black heights on all paths guarantee that the tree height remains logarithmic
B
Colors determine balance directly
C
Colors have no effect on balance
D
Only red nodes affect balance
39
Question 39
What is the complexity of implementing rotations?
A
O(1) time and space for individual rotations since they involve only constant pointer updates and height recalculations, making them efficient local operations that can be performed quickly during balancing procedures
B
O(log n)
C
O(n)
D
O(n log n)
40
Question 40
Considering balanced tree concepts and their implementation challenges, which fundamental property makes height balancing crucial for maintaining efficient data structures despite the added complexity of rotation operations?
A
Height balancing provides guaranteed worst-case logarithmic performance for all dictionary operations, preventing the O(n) degradation that occurs in unbalanced trees and ensuring predictable timing behavior essential for mission-critical applications requiring consistent performance bounds
B
Guaranteed O(1) performance
C
Minimal memory overhead
D
Simplicity of implementation