बी-ट्री - यहां तक ​​कि चाबियों की संख्या के साथ नोड क्यों नहीं हो सकता है?

Question

मैं "एल्गोरिदम के परिचय" में अध्याय "बी-पेड़" के अनुसार बी-ट्री को लागू करने की कोशिश कर रहा हूं।

मैं काफी क्या नहीं मिलता है "कम से कम डिग्री" है। पुस्तक में यह कहा गया कि डिग्री एक संख्या जो कुंजियों की संख्या एक नोड धारण कर सकते हैं के लिए कम/ऊपरी सीमा को व्यक्त करता है। यह इसे आगे कहा गया है कि:

1. प्रत्येक गैर-रूट नोड भंडार कम से कम t - 1 कुंजी और t बच्चों है।
2. प्रत्येक नोड स्टोर 2*t - 1 कुंजी पर और 2*t बच्चे है।

तो तुम टी के लिए मिलता है = 2:

1. t - 1 = 1 कुंजी और टी = 2 बच्चों
2. 2*t - 1 = 3 कुंजी और 4 बच्चों

टी = 3

के लिए

1. t - 1 = 2 कुंजी और टी = 3 ch ildren
2. 2*t - 1 = 5 कुंजी और 6 बच्चों

अब यहाँ समस्या है: ऐसा लगता है कि एक बी पेड़ में नोड्स केवल एक अजीब कुंजियों की संख्या स्टोर कर सकते हैं, जब वे भरे हुए हैं।

क्यों साथ एक नोड नहीं किया जा सकता, के ज्यादा से ज्यादा 4 कुंजी और 5 बच्चों कहना है? क्या यह नोड को विभाजित करने के साथ कुछ करने के लिए है?

Answer 1

ऐसा लगता है कि बी-ट्री में नोड्स केवल चाबियों की एक विषम संख्या को स्टोर कर सकते हैं?

निश्चित रूप से नहीं

। आपके द्वारा लिखी गई संख्या क्रमशः न्यूनतम और अधिकतम कुंजी की कुंजी है, इसलिए t = 2 के लिए, 1, 2, 3 कुंजी वाले नोड्स की अनुमति है। t = 3 के लिए, 2, 3, 4, 5 कुंजी के साथ नोड्स की अनुमति है।

इसके अलावा, पेड़ की जड़ को केवल 1 कुंजी होने की अनुमति है।

यह परिभाषित करने के लिए (और लागू) पेड़ों कि जैसे है संभव है। एक नोड में 1 या 2 कुंजी (तथाकथित 2-3 पेड़)। कारण बी-पेड़ को एक और समायोजित करने के लिए परिभाषित किया गया है, यह है कि इससे तेज प्रदर्शन होता है। विशेष रूप से, यह अमूर्त O(1) (विभाजन विभाजन और संचालन में गिनती) को हटा देता है और संचालन को सम्मिलित करता है।

Answer 2

यह असंभव नहीं है लेकिन उपमहाद्वीप है। आप बच्चों की एक विषम संख्या के साथ एक नोड कैसे विभाजित करते हैं?