Table of Contents
संतुलित द्विआधारी खोज पेड़ डेटा संरचनाएं हैं जो सॉर्ट किए गए डेटा को बनाए रखते हैं और खोज, सम्मिलित करने और हटाने जैसे कुशल संचालन सुनिश्चित करते हैं। दो सामान्य प्रकार के एवीएल पेड़ और रेड-ब्लैक पेड़ हैं, जिनमें से प्रत्येक अद्वितीय संतुलन सिद्धांतों के साथ प्रदर्शन को अनुकूलित करते हैं।
एवीएल पेड़
AVL पेड़ स्वयं संतुलन द्विआधारी खोज पेड़ हैं जहां किसी भी नोड के बाएं और दाएं उप-वर्गों के बीच की ऊंचाई में अंतर सबसे अधिक है। यह सख्त संतुलन तेजी से खोज समय सुनिश्चित करता है लेकिन संतुलन बनाए रखने के लिए सम्मिलन और विलोपन के दौरान अधिक घूर्णन की आवश्यकता होती है।
जब एक नोड एक ऑपरेशन के बाद असंतुलित हो जाता है, तो एवीएल संपत्ति को बहाल करने के लिए घूर्णन किया जाता है। इन घूर्णनों में एकल और डबल रोटेशन शामिल हैं, जो ऊंचाई अंतर को बनाए रखने में मदद करते हैं।
लाल-काले पेड़
लाल-काले पेड़ एक प्रकार का आत्म संतुलन द्विआधारी खोज पेड़ है जो प्रत्येक नोड को एक रंग (लाल या काला) सौंपता है। रंग नियम यह सुनिश्चित करते हैं कि पेड़ लगभग संतुलित रहता है, जड़ से पत्ती तक कोई रास्ता नहीं, जब तक किसी अन्य के रूप में दो बार से अधिक नहीं होता है।
प्रमुख गुण निम्न हैं:
- हर नोड लाल या काला होता है।
- जड़ हमेशा काला होती है।
- लाल नोड्स में लाल बच्चे नहीं हो सकते हैं।
- एक नोड से उसके वंशज पत्तियों तक के हर रास्ते में काले नोड्स की समान संख्या होती है।
ये गुण लाल-काले पेड़ों को पुन: रंग और घूर्णन के माध्यम से संतुलन बनाए रखते हुए सम्मिलन और हटाने को कुशलतापूर्वक करने की अनुमति देते हैं।
एवीएल और रेड-ब्लैक ट्री की तुलना
दोनों एवीएल और रेड-ब्लैक पेड़ इष्टतम प्रदर्शन के लिए संतुलित पेड़ को रखने का लक्ष्य रखते हैं। एवीएल पेड़ अधिक कड़ाई से संतुलित होते हैं, जो तेजी से लुकअप प्रदान करते हैं, लेकिन अपडेट के दौरान अधिक रोटेशन की आवश्यकता हो सकती है। रेड-ब्लैक पेड़ कम सख्त होते हैं, जो थोड़ा धीमी नज़र के साथ तेजी से सम्मिलन और हटाने की पेशकश करते हैं।