बीटीआई सम्मिलन

Question

के साथ एक विशेष समस्या मैं slady.net पर बहुत ठंडा btree एप्लेट के साथ खेल रहा हूं। मुझे एक विशेष व्यवहार को समझने में परेशानी हो रही है। इस शुरू करने राज्य पर एक नज़र डालें: 10, 15, 30, 16, 70, 1, 9, 27, 45, 50, 55:

alt text http://www.freeimagehosting.net/uploads/db2931c7da.jpg

यह विशेष रूप से राज्य निम्न क्रम डालने से पर पहुंचे किया गया था ।

मेरा प्रश्न के संबंध में है क्या [45] नोड के लिए होता है जब मैं क्रम में अगला मान सम्मिलित, 65.

alt text http://www.freeimagehosting.net/uploads/3b70c1d302.jpg

[55,70] नोड द्वारा विभाजित किया जाएगा 65, और मध्य मूल्य होने के नाते, टी वह 65 बैक अप यात्रा करेगा और फिर [30,50] नोड को भी विभाजित करेगा। मेरा सवाल है: [45,] नोड [30,] नोड के बच्चे को क्यों समाप्त करता है? इसके माता-पिता के मूल रूप से 3 बच्चे थे, बाएं सबसे अधिक और दाएं सबसे नए नए नोड बन गए। 45 उन मूल्यों के बीच था और ऐसा लगता है जैसे यह [65,] नोड के तहत भी समाप्त हो सकता था ... क्यों?

Answer 1

एक तस्वीर हजारों शब्दों के लायक है; एक एनीमेशन एक लाख के लायक है:

http://constellationmedia.com/~funsite/static/btree-insert-animation.gif

कुंजी यहाँ सूचना के लिए बात है जब केंद्र नोड 50 खिंचाई की है, यह अपने अधिकार बच्चा फेंक यह बहुत दूर से बंद होता है होता है। हालांकि, 65 को एक नए बाएं बच्चे की जरूरत है, इसलिए 50 हाथ 45 से 65 तक। 50 अब एक नए दाहिने बच्चे की जरूरत है, और 65 युक्त नोड को बच्चे की जरूरत है, इसलिए यह नव निर्मित 65 को अपने स्थान पर ले जाता है।

यहाँ दर्शाए गए हैं बी पेड़ प्रविष्टि नियम (जहां अधिकतम नोड आकार 4 आइटम, 5 बच्चे नोड्स है):

http://constellationmedia.com/~funsite/static/btree-insertion-rules.png

xr मौजूद नहीं होगा और कोई फर्क नहीं होगा अगर आप एक पत्ते में डालना (जो आप पहले करते हैं)। हालांकि, अगर आपको आधा में नोड को विभाजित करना है, तो नया x वह केंद्र वस्तु है जिसे आपने खींचा है, और नया xrx का सही बच्चा है।

Answer 2

45 नोड को दूसरे आरेख में 65 नोड का बच्चा होने का कोई मतलब नहीं है क्योंकि सही शाखा मूल्यों के लिए है> 50 (रूट नोड के दाएं-मूल्य पर आधारित) - तो 45 को जाना है कहीं दूसरी शाखा में।

Answer 3

प्रत्येक नोड में हमेशा एन + 1 बच्चे होते हैं, जहां एन उस नोड में चाबियों की संख्या होती है।

विभाजन से पहले, [30, 50] नोड की अपेक्षा की जाने वाली दो चाबियाँ और तीन बच्चे हैं। जब आप इसे विभाजित करते हैं, तो आप [30, -] नोड और एक [65, -] नोड (और 50 को एक स्तर तक दबाते हैं) के साथ समाप्त होते हैं।

अगले स्तर पर, आपके पास (पहले मौजूद) [16, 27] और [45, -], और नव-विभाजन [55, -] और [70, -] नोड्स हैं।

आपके पास दो पैरेंट नोड्स और चार बच्चे हैं। प्रत्येक माता-पिता के दो बच्चे होने चाहिए क्योंकि इसमें एक ही कुंजी है। इसलिए, आदेश नियमों को देखते हुए, [45, -] [30, -] का बच्चा होना चाहिए क्योंकि अन्यथा (1) [30, -] में पर्याप्त बच्चे नहीं होंगे, और (2) [65, -] बहुत सारे बच्चे होंगे। [संपादित करें - अवैध रूप से नोड के लिए बहुत अधिक नहीं, लेकिन विभाजन को संतुलित किया जाना चाहिए]।

क्या ए भी सही होगा। मध्य-परत नोड को विभाजित करते समय 50 कुंजी को धक्का देने का यह एक परिणाम है, लेकिन यह वास्तव में एक विकल्प नहीं था। या तो उत्पादन करने के लिए विभाजित [-, -] और [50, 65] 30 को दबाकर, या [30, 50] और [-, -] 65 को दबाकर नियम का उल्लंघन होगा कि प्रत्येक नोड कम से कम आधा भरा होना चाहिए।