एक सामान्य BST एक लिंक्ड सूची में पतित हो सकता है (O(n) संचालन) यदि कुंजियाँ क्रमबद्ध क्रम में आती हैं। स्व-संतुलन BSTs — जैसे AVL और लाल-काली वृक्ष — insertion/deletion के बाद नोड्स को स्वचालित रूप से घुमाते हैं ताकि ऊंचाई ~log n बनी रहे, O(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 वृक्ष | लाल-काली वृक्ष | |
|---|---|---|
| संतुलन कठोरता | कठोर (ऊंचाई-संतुलित) | शिथिल |
| खोज | तेजी (छोटी) | थोड़ी धीमी |
| Insert/delete | अधिक घुमाव | कम घुमाव |
| सर्वोत्तम | पढ़ने-भारी कार्यभार | लिखने-भारी कार्यभार |
| संचालन | समय |
|---|---|
| search | O(log n) |
| insert | O(log n) |
| delete | O(log n) |
दोनों घुमाव के माध्यम से संतुलन बनाए रखते हैं — स्थानीय O(1) पुनर्गठन जो BST क्रमबद्धता को संरक्षित करते हैं और ऊंचाई को कम करते हैं।
संतुलित वृक्ष मानक पुस्तकालयों में क्रमबद्ध मानचित्र और समुच्चय का समर्थन करते हैं (उदाहरण के लिए, Java TreeMap, C++ std::map लाल-काली वृक्षों का उपयोग करते हैं), क्रमबद्ध पुनरावृत्ति और गारंटीकृत लघुगणकीय संचालन प्रदान करते हैं।
जब आपको BST की क्रमबद्धता और विरोधी इनपुट के विरुद्ध कठोर प्रदर्शन गारंटी की आवश्यकता हो तो ये उत्तर हैं।