एक 2-3 पेड़ को ट्री डेटा संरचना के रूप में परिभाषित किया जाता है, जहां बच्चों (आंतरिक नोड) वाले प्रत्येक नोड में या तो दो बच्चे (2-नोड) के साथ-साथ एक डेटा तत्व या तीन बच्चे (3-नोड्स) और साथ ही दो डेटा होते हैं। तत्व।
परिभाषाएं
हम कहते हैं कि एक आंतरिक नोड एक 2-नोड है यदि इसमें एक डेटा तत्व और दो बच्चे हैं।
हम कहते हैं कि एक आंतरिक नोड एक 3-नोड है यदि इसमें दो डेटा तत्व और तीन बच्चे हैं।
हम कहते हैं कि T एक 2-3 पेड़ है यदि और केवल यदि निम्नलिखित में से कोई एक कथन संतुष्ट करता है -
-
T खाली या खाली है। दूसरे शब्दों में, T में कोई नोड नहीं है।
-
T एक 2-नोड है जो डेटा तत्व a से सुसज्जित है। यदि T के बाएं बच्चे L और दाएं बच्चे R हैं, तो हम निष्कर्ष निकालते हैं
-
L और R को समान ऊंचाई के गैर-रिक्त 2-3 पेड़ के रूप में माना जाता है;
-
ए एल में प्रत्येक तत्व से अधिक है; और
-
a, R में प्रत्येक डेटा तत्व से छोटा या उसके बराबर है।
-
टी डेटा तत्वों ए और बी के साथ एक 3-नोड है, जहां ए बी से कम है। यदि T के बाएं बच्चे L, मध्यम बच्चे M और दाएं बच्चे R हैं, तो हम निष्कर्ष निकालते हैं
-
L, M, और R को समान ऊंचाई के गैर-रिक्त 2-3 पेड़ के रूप में माना जाता है;
-
ए एल में प्रत्येक डेटा तत्व से अधिक है और एम में प्रत्येक डेटा तत्व से छोटा या बराबर है; और
-
b, M में प्रत्येक डेटा तत्व से अधिक है और R में प्रत्येक डेटा तत्व से छोटा या उसके बराबर है।
गुण
-
प्रत्येक आंतरिक नोड को 2-नोड या 3-नोड के रूप में माना जाता है।
-
सभी पत्ते एक ही स्तर पर स्थित होते हैं।
-
सभी डेटा बनाए रखा जाता है या क्रमबद्ध क्रम में रखा जाता है।
ऑपरेशन
खोज
2-3 ट्री में किसी आइटम की खोज करना बाइनरी सर्च ट्री में किसी आइटम की खोज करने के समान है। चूंकि प्रत्येक नोड में डेटा तत्वों को आदेश के रूप में माना जाता है, एक खोज फ़ंक्शन को सही सबट्री और अंततः सही नोड पर निर्देशित किया जाएगा जिसमें आइटम शामिल है।
-
टी को 2-3 पेड़ के रूप में माना जाता है और डी वह डेटा तत्व होता है जिसे हम खोजना चाहते हैं। यदि T खाली है, तो d, T में नहीं है और हम प्रदर्शन कर रहे हैं।
-
माना कि r को T का मूल माना जाता है।
-
माना r एक पत्ता है। यदि d, r में नहीं है, परिणामस्वरूप d, T में नहीं है। अन्यथा, d, T में है। विशेष रूप से, d को लीफ नोड पर पाया जा सकता है। हमें किसी और कदम की आवश्यकता नहीं है और हम प्रदर्शन कर रहे हैं।
-
मान लीजिए r को बाएं बच्चे L और दाएं बच्चे R के साथ 2-नोड के रूप में माना जाता है। मान लें कि e को r में डेटा तत्व के रूप में माना जाता है।
तीन मामले हैं -
-
यदि d, e के बराबर है, तो हमने d को T में पाया है और हम प्रदर्शन कर रहे हैं।
-
यदि d, e से कम है, तो T को L पर सेट करें, जो परिभाषा के अनुसार एक 2-3 पेड़ है, और चरण 2 पर वापस लौटें।
-
यदि d बड़ा e है, तो T को R पर सेट करें और चरण 2 पर वापस लौटें।
-
मान लीजिए r एक 3-नोड है जिसमें बायां बच्चा L, मध्य बच्चा M, और दायां बच्चा R है। मान लीजिए कि a और b को r के दो डेटा तत्वों के रूप में माना जाता है, जहां a
-
यदि d, a या b के बराबर है, तो d, T में है और हम प्रदर्शन कर रहे हैं।
-
यदि d, a से कम है, तो T को L पर सेट करें और चरण 2 पर वापस लौटें।
-
यदि ais d से कम है और d b से कम है, तो T को M पर सेट करें और चरण 2 पर वापस लौटें।
-
यदि d, b से बड़ा है, तो T को R पर सेट करें और वापस चरण 2 पर जाएं।
-
सम्मिलन
इंसर्शन कुंजी के उचित स्थान की खोज करके और उसे वहां जोड़ने या जोड़ने का कार्य करता है। यदि नोड 4-नोड बन जाता है तो नोड को दो 2-नोड्स में विभाजित किया जाता है और मध्य कुंजी को पैरेंट तक ले जाया जाता है। माता-पिता तब 4-नोड बन सकते हैं, जिस स्थिति में इसे भी विभाजित किया जाता है, अपने स्वयं के माता-पिता की कुंजी का प्रचार करता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कि हम एक माता-पिता तक नहीं पहुंच जाते जो कि 2-नोड है और इसे विभाजित करने की आवश्यकता नहीं है, या जब हम रूट तक पहुंच जाते हैं, तो उस स्थिति में हम एक नया रूट बनाने के लिए प्रचारित तत्व को लागू करते हैं जो कि 2-नोड है . इस एल्गोरिथम की मदद से, प्रदर्शन करने के लिए संचालन की संख्या पेड़ की ऊंचाई के समानुपाती होती है, इसलिए लॉगरिदमिक होता है क्योंकि पेड़ पूरी तरह से संतुलित होता है। प्रक्रिया सुनिश्चित करती है कि इसके परिणाम को 2-3 पेड़ के रूप में माना जाता है:विशेष रूप से, सभी पत्ते एक ही गहराई पर रहते हैं।
नीचे दिया गया चित्र इस प्रक्रिया के संभावित मामलों की व्याख्या या चित्रण करता है।
3 संभावित मामलों के लिए 2-3 पेड़ में एक संख्या का सम्मिलन।