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