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

حداکثر تعداد کلید در یک B.Tree با مینیمم درجه نود t و ارتفاع h چقدر است؟
منظور از کلید، همون عناصر درخته؟
جواب این تست میشه:[tex](2t)^{h 1}-1[/tex]

می دانیم که در هر گره حداقل ۲t-1 و حداکتر t-1 کلید وجود دارد
جون در اینحا حداکتر کلید را می خواهد هر گره باید ۲t-1 کلید و درحت باید یک درخت پر با ارتفاع h باشد
در سطح ۰ یک گره با ۲t-1 کلید داریم
در سطح ۱ ۲t گره داربم که در کل در این سطح ۲t ضزبدر ۲t-1 کلید داریم
در سطح ۲ ۲t به توان ۲ گره داربم که در کل در این سطح ۲t^2 ضزبدر ۲t-1 کلید داریم
...
در سطح h هم ۲t^h گره داربم که در کل در این سطح ۲t^h ضزبدر ۲t-1 کلید داریم

پس در کل داریم

(24 بهمن 1390 07:04 ب.ظ)zeinab نوشته شده توسط: [ -> ]میشه بیشتر توضیح بدین !!
یه جوریه!
متوجه نمی شم

در درخت btree وقتی میگه مینیمم درجه t هست یعنی در هر گره از این درخت میتونیم به صورت زیر کلید قرار بدیم:

تعداد کلید‌ها در یک گره از درخت = N پس داریم: [tex](t-1)\leq N\leq (2t-1)[/tex]

اینجا گفته حداکثر کلید‌ها چقد ر هست پس ما باید تو هر گره بیشترین تعداد کلید که میشه جا بگیره رو انتخاب کنیم یعنی مقدار (2t-1)

اگه تو هر گره ما (2t-1) کلید داشته باشیم تعداد فرزندان برای اون گره میشه --->2t

حالا مسئله رو حل میکنیم:
1.تو سطح ریشه ما یک گره داریم و اون هم حداکثر تعداد کلید‌ها رو داره پس (2t-1 )کلید داره.
2.ریشه 2t فرزند داره .هر فرزند یک گره هست که داخل هر گره فرزند هم حداکثر تعداد کلید داریم یعنی هر کدم از 2t فرزند (2t-1) کلید دارن پس در سطح دوم مثل اینه که ما 2t خونه داریم و تو هر خونه (2t-1) نفر حضور دارن پس در کل ----->[tex](2t-1)*2t[/tex]

3.تو سطح سوم هر کدوم از اون فرزند‌ها باز 2t فرزند دارن پس از سطح دوم ما 2t فرزند داشتیم که هر کدوم هم 2t فرزند دارن و هر یک از این فرزند فرزندان هم (2t-1) کلید دارن پس اینجا: [tex](2t-1)*(2t)^{2}[/tex]
(اگه برا خودت شکل بکشی خیلی راحت متوجه میشی)

به همین ترتیب تا سطح اخر یا همون ارتفاع h که به این صورت داریم:

[tex](2t)^{0} (2t-1)*(2t)^{1} (2t-1)*(2t)^{2} (2t-1)*(2t)^{3} ... (2t-1)*(2t)^{h}[/tex]

[tex](2t-1)*\frac{((2t)^{h 1}-1)}{(2t-1)}=(2t)^{h 1}-1[/tex]