यहाँ हम देखेंगे कि संतुलित बाइनरी खोज ट्री (Balanced Binary Search Tree) क्या है। बाइनरी खोज ट्री (BST) बाइनरी ट्री हैं, जिनमें बाएं बच्चे में छोटा तत्व होता है, और दाएं बच्चे में बड़ा तत्व होता है।
BST में तत्वों को खोजने के लिए औसत समय जटिलता O(log n) है। यह बाइनरी खोज ट्री की ऊंचाई पर निर्भर करता है। बाइनरी खोज ट्री के गुणों को बनाए रखने के लिए, कभी-कभी ट्री विषम (skewed) हो जाती है। इसलिए विषम ट्री नीचे जैसी दिखेगी:
यह वास्तव में एक ट्री है, लेकिन यह लिंक्ड सूची की तरह दिख रही है। इस तरह के ट्री के लिए, खोज समय O(n) होगा। जो बाइनरी ट्री के लिए प्रभावी नहीं है।
इन समस्याओं को दूर करने के लिए, हम एक ट्री बना सकते हैं जो ऊंचाई-संतुलित (height balanced) हो। ताकि ट्री विषम न हो। जबरदस्ती, हम उन्हें संतुलित बनाएंगे। ताकि एक नोड का प्रत्येक पक्ष एक उपट्री रखे जिसकी ऊंचाई लगभग समान हो।
संतुलन के लिए अलग-अलग तकनीकें हैं। उनमें से कुछ हैं:
AVL ट्री
रेड-ब्लैक ट्री (Red-Black Tree)
उपरोक्त उदाहरण का ऊंचाई-संतुलित रूप नीचे जैसा दिखेगा:
