यहां हम देखेंगे कि संतुलित बाइनरी सर्च ट्री क्या है। बाइनरी सर्च ट्री (BST) बाइनरी ट्री होते हैं, जिनके बाएं बच्चे में कम तत्व होते हैं, और दाएं बच्चे में अधिक तत्व होते हैं।
बीएसटी में तत्वों की खोज के लिए औसत समय जटिलता ओ (लॉग एन) है। यह बाइनरी सर्च ट्री की ऊंचाई पर निर्भर करता है। बाइनरी सर्च ट्री के गुणों को बनाए रखने के लिए कभी-कभी ट्री तिरछा हो जाता है। तो तिरछा पेड़ इस तरह दिखेगा -
यह वास्तव में एक पेड़ है, लेकिन यह एक लिंक्ड सूची की तरह दिख रहा है। इस प्रकार के वृक्षों के लिए खोज समय O(n) होगा। यह बाइनरी ट्री के लिए प्रभावी नहीं है।
इन समस्याओं को दूर करने के लिए हम एक ऐसा पेड़ बना सकते हैं जो ऊंचाई संतुलित हो। तो पेड़ नहीं काटा जाएगा। बलपूर्वक, हम तब संतुलित करेंगे। तो नोड के प्रत्येक पक्ष में एक सबट्री होगी जिसकी ऊंचाई लगभग समान होगी
संतुलन के लिए विभिन्न तकनीकें हैं। उनमें से कुछ हैं -
-
एवीएल पेड़
-
लाल-काले पेड़
उपरोक्त उदाहरण का ऊंचाई संतुलित रूप इस तरह दिखेगा -
