एक साधा BST कळीजच्या क्रमबद्ध क्रमाने येऊ शकतो तर एक लिंक केलेली यादी (O(n) ऑपरेशन) मध्ये खराब होऊ शकते. स्व-संतुलन BST — जसे की AVL आणि लाल-काळे वृक्ष — सन्निहित होयीयाद्या/हटवणीच्या नंतर नोड्सला आपोआप फिरवतात उंची ~log n राखण्यासाठी, ऑपरेशन्स हमी देतात.
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| AVL वृक्ष | लाल-काळे वृक्ष | |
|---|---|---|
| संतुलन कडकपणा | कडक (उंचीने संतुलित) | हलक्या |
| शोध | वेगवान (लहान) | थोडेसे मंद |
| समाविष्ट/हटवणी | अधिक फिरवणे | कमी फिरवणे |
| सर्वोत्तम | वाचन-गहन कार्यभार | लेखन-गहन कार्यभार |
| ऑपरेशन | वेळ |
|---|---|
| शोध | O(log n) |
| समाविष्ट | O(log n) |
| हटवणी | O(log n) |
दोन्ही फिरवणीद्वारे संतुलन राखतात — स्थानिक O(1) पुनर्संरचना जो BST क्रम संरक्षित करते उंची कमी करताना.
संतुलित वृक्ष मानक लायब्ररीमध्ये क्रमबद्ध मानचित्र आणि संच समर्थित करतात (उदा. Java TreeMap, C++ std::map लाल-काळे वृक्ष वापरतात), क्रमबद्ध पुनरावृत्ती आणि हमीबद्ध लॉगरिदमिक ऑपरेशन देतात.
हे उत्तर आहे जेव्हा तुम्हाला BST च्या क्रमबद्धता आणि प्रतिकूल इनपुटविरुद्ध कठोर कार्यक्षमता गारंटी हवी असेल.
सविस्तर उत्तरांसह IT मुलाखत प्रश्नांचे ग्रंथालय — Junior पासून Senior पर्यंत.
देणगी द्या