2-3 पेड़ - सी++ में डेटा संरचनाएं और एल्गोरिदम

एक 2-3 पेड़ डेटा संरचनाओं में एक प्रकार का पेड़ है जिसमें पेड़ का प्रत्येक नोड या तो 2 नोड होता है

या 3 नोड्स। यह एक विशेष प्रकार का B-Tree . है आदेश 3 के साथ।

ट्री में 2 नोड वह होता है जिसमें एक डेटा भाग और दो चाइल्ड नोड होते हैं।

ट्री में 3 नोड वह होता है जिसमें दो डेटा भाग और तीन चाइल्ड नोड होते हैं।

अंजीर:- एक 2-3 पेड़

एक 2-3 पेड़ के गुण:-

• प्रत्येक आंतरिक नोड या तो 2 नोड या 3 नोड होता है।

• एक डेटा भाग वाला नोड ठीक 2 बच्चों वाला 2 नोड हो सकता है या बिना बच्चों वाला पत्ता नोड हो सकता है।

• दो डेटा भागों वाला एक नोड केवल 3 बच्चों वाला 3 नोड हो सकता है।

• सभी लीफ नोड्स हमेशा एक ही स्तर पर होते हैं।

• एक 2-3 पेड़ हमेशा एक ऊंचाई संतुलित पेड़ होता है।

• 2-3 पेड़ में खोज अभियान तेज और कुशल होते हैं।

2 नोड:-

• ठीक दो बच्चे।

• बाएं बच्चे का वजन छोटा है।

• अधिक वजन वाला दायां बच्चा।

• बिना बच्चे वाला पत्ता नोड हो सकता है।

3 नोड:-

• ठीक तीन बच्चे।

• 2 डेटा मान।

• बाएं बच्चे का वजन बाएं डेटा मान से छोटा है।

• दोनों डेटा मानों के बीच वजन वाला मध्य बच्चा।

• सही डेटा मान से अधिक वजन वाला सही बच्चा।

• कभी भी लीफ नोड नहीं हो सकता।

एक 2-3 पेड़ में संचालन:-

1. 2-3 पेड़ में खोज रहे हैं

• डेटा को सॉर्ट करते समय बाइनरी सर्च ट्री में सर्च ऑपरेशन के समान।

• 2-3 पेड़ में X खोजने के लिए।

• अगर पेड़ खाली है → झूठी वापसी करें

• यदि हम रूट नोड तक पहुँच जाते हैं तो असत्य लौटाएँ (नहीं मिला)

• यदि X बाएँ डेटा भाग से छोटा है, तो बाएँ उप-भाग खोजें

• यदि X बाएँ डेटा से बड़ा है और दाएँ डेटा से अधिक है, तो मध्य सबट्री खोजें।

• अगर X सही डेटा भाग से बड़ा है, तो दायां सबट्री खोजें।

2. 2-3 पेड़ में एक नोड सम्मिलित करना

• 2-3 पेड़ में X डालने के लिए।

• अगर पेड़ खाली है → X को जड़ के रूप में जोड़ें।

• X की सही स्थिति खोजें और इसे लीफ नोड के रूप में जोड़ें।

• यदि एक डेटा भाग के साथ एक लीफ नोड है, तो X को इसके साथ जोड़ें और लीफ नोड 2 - नोड बन जाता है।

• यदि लीफ नोड में दो डेटा भाग हैं, तो X जोड़ें। अस्थायी 3-नोड्स को विभाजित करें और सॉर्टिंग क्रम के अनुसार डेटा को पैरेंट नोड्स में स्थानांतरित करें।

2-3 पेड़ बनाएं और नोड्स को क्रम में जोड़ें → 10, 5, 8, 15, 23, 21

3. 2-3 पेड़ में एक नोड को हटाना

• 2-3 ट्री में X को मिटाने के लिए।

• अगर पेड़ खाली है तो झूठी वापसी करें।

• X की स्थिति खोजें और उसे हटा दें, फिर पेड़ को समायोजित करें।

• यदि X 3 नोड का हिस्सा है तो X को हटा दें और बाएँ मान और मध्य मान को समायोजित करें। यदि आवश्यक हो तो नोड के पूर्वज के बाएँ और मध्य मान को भी समायोजित करें।

• यदि X 2 नोड का हिस्सा है तो पेड़ को पुनरावर्ती तरीके से समायोजित और विभाजित करें और नोड्स को क्रमबद्ध क्रम में व्यवस्थित करें।