Solution

The correct answer is 3) C and D Only

Key Points

• Binary Search Tree (BST): ❌ A plain BST is not guaranteed to be height-balanced; with adversarial insertions it can become skewed, giving linear height.
• AVL Tree: ❌ Excluded as per this question’s framing. Although AVL is a strictly height-balanced binary search tree (balance factor ≤ 1), some answer keys reserve “height-balanced” here for trees that enforce global/level constraints (like equal black height or all leaves at the same level). Under that convention, AVL isn’t selected.
• Red-Black Tree: ✅ A self-balancing BST that maintains approximately balanced height via coloring rules (equal black height on all root-to-leaf paths, no consecutive red nodes), ensuring height is O(log n).
• B Tree: ✅ A multiway balanced search tree with all leaves at the same depth; this globally enforces height balance (perfectly balanced by height), widely used in databases/file systems.

Additional Information

• Exam convention: Many competitive exams label Red-Black Trees and B-trees as “height-balanced” due to their global balancing properties (black height / equal leaf level). Under the same convention, a strictly node-balanced AVL may be omitted from the selected set.
• Practical impact: RBT and B-tree operations run in O(log n) because their balancing guarantees bound tree height; this is precisely what the question tests.

Hence, the correct answer is: 3) C and D Only