حداکثر تعداد کلید در یک 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 کلید داریم
پس در کل داریم
۲t-1)(1+2t + 2t^2+ 2t^3 + ... + 2t^h) = (2t^(h+1)) - 1
(۲۴ بهمن ۱۳۹۰ ۰۷:۰۴ ب.ظ)zeinab نوشته شده توسط: میشه بیشتر توضیح بدین !!
یه جوریه!
متوجه نمی شم
در درخت btree وقتی میگه مینیمم درجه t هست یعنی در هر گره از این درخت میتونیم به صورت زیر کلید قرار بدیم:
تعداد کلید‌ها در یک گره از درخت = N پس داریم: [tex](t-1)\leq N\leq (2t-1)[/tex]
اینجا گفته حداکثر کلید‌ها چقد ر هست پس ما باید تو هر گره بیشترین تعداد کلید که میشه جا بگیره رو انتخاب کنیم یعنی مقدار (۲t-1)
اگه تو هر گره ما (۲t-1) کلید داشته باشیم تعداد فرزندان برای اون گره میشه --->2t
حالا مسئله رو حل میکنیم:
۱/تو سطح ریشه ما یک گره داریم و اون هم حداکثر تعداد کلید‌ها رو داره پس (۲t-1 )کلید داره.
۲/ریشه ۲t فرزند داره .هر فرزند یک گره هست که داخل هر گره فرزند هم حداکثر تعداد کلید داریم یعنی هر کدم از ۲t فرزند (۲t-1) کلید دارن پس در سطح دوم مثل اینه که ما ۲t خونه داریم و تو هر خونه (۲t-1) نفر حضور دارن پس در کل ----->[tex](2t-1)*2t[/tex]
۳/تو سطح سوم هر کدوم از اون فرزند‌ها باز ۲t فرزند دارن پس از سطح دوم ما ۲t فرزند داشتیم که هر کدوم هم ۲t فرزند دارن و هر یک از این فرزند فرزندان هم (۲t-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]