Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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

2-3 ट्री डेटा संरचनाओं में एक प्रकार का ट्री है जिसमें ट्री का प्रत्येक नोड या तो 2 नोड होता है या 3 नोड्स। यह ऑर्डर 3 के साथ एक विशेष प्रकार का B-Tree है।

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

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

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

2-3 ट्री के गुण:

  • प्रत्येक आंतरिक नोड या तो 2 नोड या 3 नोड होता है।
  • एक डेटा भाग वाला नोड या तो 2 चाइल्ड्स के साथ 2 नोड हो सकता है या बिना चाइल्ड्स के लीफ नोड।
  • दो डेटा भागों वाला नोड केवल 3 चाइल्ड्स के साथ 3 नोड हो सकता है।
  • सभी लीफ नोड्स हमेशा एक ही स्तर पर होते हैं।
  • 2-3 ट्री हमेशा एक ऊंचाई-संतुलित ट्री होता है।
  • 2-3 ट्री में खोज संचालन तेज और कुशल होते हैं।

2 नोड:

  • ठीक दो चाइल्ड्स।
  • बायां चाइल्ड छोटे वजन के साथ।
  • दायां चाइल्ड बड़े वजन के साथ।
  • बिना चाइल्ड के लीफ नोड हो सकता है।

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

3 नोड:

  • ठीक तीन चाइल्ड्स।
  • 2 डेटा मान।
  • बायां चाइल्ड बाएं डेटा मान से छोटे वजन के साथ।
  • मध्य चाइल्ड दोनों डेटा मानों के बीच के वजन के साथ।
  • दायां चाइल्ड दाएं डेटा मान से बड़े वजन के साथ।
  • कभी लीफ नोड नहीं हो सकता।

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

2-3 ट्री में संचालन:

1. 2-3 ट्री में खोज

  • बाइनरी सर्च ट्री में खोज संचालन के समान क्योंकि डेटा क्रमबद्ध है।
  • 2-3 ट्री में X खोजने के लिए।
  • यदि ट्री खाली है → false लौटाएं।
  • यदि हम रूट नोड पर पहुंचते हैं तो false लौटाएं (नहीं मिला)।
  • यदि X बाएं डेटा भाग से कम है, तो बाएं सबट्री में खोजें।
  • यदि X बाएं डेटा से बड़ा है और दाएं डेटा से अधिक है, तो मध्य सबट्री में खोजें।
  • यदि X दाएं डेटा भाग से बड़ा है, तो दाएं सबट्री में खोजें।

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

2. 2-3 ट्री में नोड डालना

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

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

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

3. 2-3 ट्री में नोड हटाना

  • 2-3 ट्री में X हटाने के लिए।
  • यदि ट्री खाली है तो false लौटाएं।
  • X की स्थिति खोजें और इसे हटाएं, फिर ट्री को समायोजित करें।
  • यदि X 3 नोड का हिस्सा है तो X को हटाएं और बाएं मान और मध्य मान को समायोजित करें। यदि आवश्यक हो तो नोड के पूर्वजों के बाएं और मध्य मान को भी समायोजित करें।
  • यदि X 2 नोड का हिस्सा है तो ट्री को पुनरावर्ती तरीके से समायोजित और विभाजित करें, नोड्स को क्रमबद्ध क्रम में व्यवस्थित करें।
  1. C/C++ में 2-3 ट्री (खोज और सम्मिलन) C/C++ में 2-3 ट्री (खोज और सम्मिलन)

    2-3 ट्री को एक ट्री डेटा संरचना के रूप में परिभाषित किया गया है, जहां बच्चों वाला हर नोड (आंतरिक नोड) या तो दो बच्चे (2-नोड) और एक डेटा तत्व या तीन बच्चे (3-नोड्स) और दो डेटा तत्व रखता है।परिभाषाएंहम कहते हैं कि एक आंतरिक नोड 2-नोड है यदि इसमें एक डेटा तत्व और दो बच्चे हैं।हम कहते हैं कि एक आंतरिक न

  1. डेटा स्ट्रक्चर में बाइनरी ट्री ट्रैवर्सल डेटा स्ट्रक्चर में बाइनरी ट्री ट्रैवर्सल

    इस खंड में हम बाइनरी सर्च ट्री में मौजूद कीज़ को ट्रैवर्स करने के लिए विभिन्न ट्रैवर्सल एल्गोरिदम देखेंगे। ये ट्रैवर्सल हैं: इनऑर्डर ट्रैवर्सल, प्रीऑर्डर ट्रैवर्सल, पोस्टऑर्डर ट्रैवर्सल और लेवल ऑर्डर ट्रैवर्सल।मान लीजिए हमारे पास ऐसा एक ट्री है:इनऑर्डर ट्रैवर्सल क्रम इस प्रकार होगा: 5 8 10 15 16 20

  1. डेटा स्ट्रक्चर में बाइनरी ट्री और गुण डेटा स्ट्रक्चर में बाइनरी ट्री और गुण

    इस खंड में हम बाइनरी ट्री डेटा स्ट्रक्चर के कुछ महत्वपूर्ण गुण देखेंगे। मान लीजिए हमारे पास ऐसा बाइनरी ट्री है।कुछ गुण हैं:लेवल l पर नोड्स की अधिकतम संख्या $2^{l-1}$ होगी। यहां लेवल रूट से नोड तक के पथ पर नोड्स की संख्या है, जिसमें रूट स्वयं शामिल है। हम रूट का लेवल 1 मान रहे हैं।ऊंचाई h के बाइनरी ट