Question:
In a Red-Black Tree, what is the maximum possible height of a tree with \(n\) internal nodes?
एक रेड-ब्लैक ट्री में \(n\) आंतरिक नोड्स वाले ट्री की अधिकतम संभावित ऊंचाई क्या हो सकती है?
Options:
- \(2 \log_2(n + 1)\)
- \(\log_2(n + 1)\)
- \(1.44 \log_2(n + 1)\)
- \(n\)
- \(2 \log_2(n + 1)\)
- \(\log_2(n + 1)\)
- \(1.44 \log_2(n + 1)\)
- \(n\)
Correct Answer: a)
Explanation:
A Red-Black tree of height \(h\) has black-height \(bh \ge h/2\). Since \(n \ge 2^{bh} – 1 \ge 2^{h/2} – 1\), solving for \(h\) yields \(h \le 2 \log_2(n + 1)\).
रेड-ब्लैक ट्री में लाल नोड का कोई लाल बच्चा नहीं हो सकता, जिससे कम से कम आधे नोड काले होते हैं। अतः अधिकतम ऊंचाई \(2 \log_2(n+1)\) होती है।