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