حداقل و حداکثر گره های یک درخت دودویی

[lvenoos]

حداقل و حداکثر تعدادگره های یک درخت دودویی به ارتفاع hچقدر است؟

[whitehat]

Min: 2^h
Max:2^(h+1)-1

[lvenoos]

این سوال در تست سراسری 81 ارشد مطرح شده بود و جواب max با پاسخ شما مطابقت داشت اما جواب minنه.برای minگفته بود حداقل در درختان مورب به چپ یا مورب به راست به وجود می آید که می شود 2h+1. به نظر شما این پاسخ صحیح است؟ در کتاب دیگری پاسخ شما مطرح شده بود.

[whitehat]

جواب شما درسته،من به صورت سوال دقت نکرده بودم! درصورتی که درخت دودویی کامل نباشد ، مثل درخت دودیی محض شما یک ریشه دارید و نود های دارای دو فرزند هستند و سطح آخر یک برگ داشته باشد فرمول به شکل 2h+1 می باشد.

[icmaster]

سلام.
ولی تو درخت مورب حداقل گره ها میشه h+1

مثل:


5
\
6
\
7


که تعداد گره ها 3 و ارتفاع 2 هست (البته اگه ارتفاع ریشه رو صفر بگیریم)

[whitehat]

دوست عزیز منظور درخت دو دویی محض است، درختی که نودهای آن صفر یا 2 فرزند غیر از سطح آخر دارند

[icmaster]

دوست من این تعریفی که شما گفتی تعریف درخت دودویی محض هست!


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

[lvenoos]

پس حداقل تعداد گره هابا فرض صفر بودن ارتفاع ریشه چقدر شد؟

[icmaster]

اگر در صورت سوال فقط گفته درخت دودویی مسلماً حداقل گره هاش h+1 خواهد بود.

[whitehat]

اگر در صورت سوال فقط گفته درخت دودویی مسلماً حداقل گره هاش h+1 خواهد بود.
چرا؟ معمولا در تست ها منظور از درخت دودویی درخت دودویی محض است

[icmaster]

چرا؟ معمولا در تست ها منظور از درخت دودویی درخت دودویی محض است


ولی فکر نمیکنم اینجوری باشه، البته از روی گزینه ها هم میشه فهمید منظور چی بوده مثلاً اگر در این سوال در گزینه ها h+1 وجود نداشته باشه و 2h+1 وجود داشته باشه میشه فهمید که منظور درخت دودویی محض هست.

[whitehat]

درخت مورب جزء درخت دودیی حساب می شود؟

[lvenoos]

در صورت سوال فقط ذکر شده بود یک درخت دودویی درختی است که هر گره آن صفر یا 2 فرزند دارد.و در گزینه ها هم h+1را داده بود و هم 2h+1را.

[whitehat]

منظور من از پست قبلی همین بود، درخت مورب را جزء درختان دودویی حساب نکنید !

[icmaster]

خوب چون صورت سوال خودش گفته منظرش چه نوع درختی هست 2h+1 صحیح است.
ولی طبق تعریف معمول درخت دودویی، درخت مورب هم دودویی هست.

[viviano]

Min: 2^h
Max:2^(h+1)-1


این همون بهترین و بدترین حالت در جست و جوی دودیی محسوب می شه؟

[مسعود اقدسی فام]

این همون بهترین و بدترین حالت در جست و جوی دودیی محسوب می شه؟

بدترین حالت جستجوی دودویی ( O( log n و بهترین حالت ( O( 1 هست. بدترین حالت زمانیه که تمام عمق درخت رو برای پیدا کردن عنصر مورد نظر پیمایش کنیم، که log2 n می‌شه. و بهترین حالت اینه که عنصر ریشه درخت همون عنصر مورد نظر باشه که با یه مقایسه به دست می‌یاد و ( O( 1 می‌شه.

البته من در اینجا آرایه مرتب برای استفاده از جستجوی دودویی رو با یه درخت جستجوی دودویی معادل کردم. ابهام پیش نیاد.