تالار گفتمان مانشت

کسی سوال ۵صفحه ۵۲۳ ساختمان داده مقسمی در مورد B-tree رو فهمیده جوابش رو؟ برای چی توی جوابشE ,J,V ترکیب شدن و یک گره تشگیل دادن؟ لزومی نداشت!

این تست خارج از سرفصل ارشد هستش و دکتر قدسی نامه دادند که حذف بشه.

[attachment=7407]

---

جدا از سرفصل بودن یا نبودن جواب توی مقسمی گزینه 1 هست اصلا نمیدونم چجوری شد!!!!!

به خاطر اینکه در B_tree وقتی می خواید حذف بکنید باید از جایی که شروع میکنید به پیمایش اگر اون گره دو فرزند داشته باشه با t-1 کلید (دو گره همزاد) باید آنها را با هم ترکیب کنید. (یعنی گره پدر رو باید یک سطح بیارید پایین و بین دو گره فرزند قرار بدید.)
این سوال رو در کتاب پارسه صفحه 206 توضیح داده

به خاطر اینکه در B_tree وقتی می خواید حذف بکنید باید از جایی که شروع میکنید به پیمایش اگر اون گره دو فرزند داشته باشه با t-1 کلید (دو گره همزاد) باید آنها را با هم ترکیب کنید. (یعنی گره پدر رو باید یک سطح بیارید پایین و بین دو گره فرزند قرار بدید.)
این سوال رو در کتاب پارسه صفحه ۲۰۶ توضیح داد

خودتون میگین که اگر هر دو فرزند t-1 کلید داشته باشن.. این ک فرزند سمت راستش t کلید داره... فک میکنم این قسمتش ک E رو انتخاب کرده درسته...نظر من اینه که نباید توی جواب ارایه شده توسط مقسمی ترکیبش می کرد...

ببینید از اول که بخوایم شروع کنیم به پیمایش:
میگیم J پدر D و V هست و این دو فرزند هر کدام t-1 کلید دارن پس با هم ترکیب میشن و میشه DJV و برای اینکه D رو حذف کنیم باید عنصر قبل از D رو جایگزینش بکنیم که عنصر بعد از D هم F هست و چون F گره میانی هست و نمیشه همینجوری حذفش کنیم باید درخت رو پیمایش کنیم تا به برگ برسیم وقتی به بچه های F میرسیم میبینیم که هردو t-1 کلید دارن پس F رو یک سطح میاریم پایین و با بچه هاش ترکیبش میکنیم ( که شکل درخت به این صورت میشه که EFG میشه فرزند چپ H) حالا نگاه میکنیم که عنصر بعد از D کدوم حرف هست . که میبینیم E هست پس E رو حذف کرده و به جای D میگذاریم که در سطح صفر است.

برا چی D,J,V رو همون اول با هم ترکیب کردین.. به فرزندای D نگاه میکنیم اگه t-1 فرزند داشت با D ترکیب میکنن بعد D رو پاک میکنن... اگه اینجوری ک شما انجام دادین و از همون اول صورت سوال رو دست زدین ... پس اشکالی نداره برگهای زیر درخت راست هم این وضعیت رو داره پس باید ترکیب شن...

ببینید چون نگفته از نود D شروع میکنیم به پیمایش من از ریشه درخت رو پیمایش کردم (با توجه به شکلی که تو کتاب پارسه بود علامت زده بود که باید از ریشه شروع بشه ولی شکل این کتاب هیچ علامتی نداره که پیمایش رو از کجا باید شروع کنیم) ولی اگر پیمایش رو از D شروع کنیم دیگه نیازی نیست که D,J,V رو با هم ترکیب کنیم و اونوقت E در سطح 1 قرار میگیره.
در مورد برگهای زیر درخت راست : ما اصلا با اونها کاری نداریم که بخوایم بهشون دست بزنیم اگر هم این کار رو بکنیم هیچ تاثیری در جوابمون نداره.

---

البته قانون حذف این هست که شما وقتی نودی رو میخواید حذف کنید از پدرانش شروع به پیمایش میکنید که اگر آنها دارای حداقل کلید بودن با هم ترکیب بشن و مجبور نباشیم وقتی اون عنصر رو حذف میکنیم مجددا درخت رو به B-tree تبدیل کنیم. (البته میتونید این کار رو هم نکنید و در آخر درخت رو مرتب کنید)

پس فکر کنم که دکتر قدسی بنا به گفتهali این تست رو حذف کرده نه بخاطر جز سرفصل نبودن شاید بخاطر اشتباه در تست حذف کردن!!!!

نامه دکتر قدسی برای حذف این سئوال.

خداروشکر که واقعا سوال غلط بود وگرنه به خودم و خوندنم شک میکردم و قید ارشدو میزدماز آقای ali هم ممنونم ک ما رو از اشتباه در آورد...