حداقل و حداکثر تعدادگره های یک درخت دودویی به ارتفاع hچقدر است؟
حداقل و حداکثر تعدادگره های یک درخت دودویی به ارتفاع hچقدر است؟
Min: 2^h
Max:2^(h+1)-1
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
این سوال در تست سراسری 81 ارشد مطرح شده بود و جواب max با پاسخ شما مطابقت داشت اما جواب minنه.برای minگفته بود حداقل در درختان مورب به چپ یا مورب به راست به وجود می آید که می شود 2h+1. به نظر شما این پاسخ صحیح است؟ در کتاب دیگری پاسخ شما مطرح شده بود.
جواب شما درسته،من به صورت سوال دقت نکرده بودم! درصورتی که درخت دودویی کامل نباشد ، مثل درخت دودیی محض شما یک ریشه دارید و نود های دارای دو فرزند هستند و سطح آخر یک برگ داشته باشد فرمول به شکل 2h+1 می باشد.
آخرین ویرایش به وسیله whitehat : یک شنبه 27 آبان 1386 در 23:32 عصر دلیل: تعریف اشتباه در درخت دودویی محض
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
سلام.
ولی تو درخت مورب حداقل گره ها میشه h+1
مثل:
5
\
6
\
7
که تعداد گره ها 3 و ارتفاع 2 هست (البته اگه ارتفاع ریشه رو صفر بگیریم)
دوست عزیز منظور درخت دو دویی محض است، درختی که نودهای آن صفر یا 2 فرزند غیر از سطح آخر دارند
آخرین ویرایش به وسیله whitehat : یک شنبه 27 آبان 1386 در 23:31 عصر دلیل: اشتباه در تعریف درخت دودویی محض
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
دوست من این تعریفی که شما گفتی تعریف درخت دودویی محض هست!
برای تعریف درخت دودویی میتونی به صفحه 248 کتاب ساختمان داده هوروویتس ترجمه قلزم مراجعه کنی.
پس حداقل تعداد گره هابا فرض صفر بودن ارتفاع ریشه چقدر شد؟
اگر در صورت سوال فقط گفته درخت دودویی مسلماً حداقل گره هاش h+1 خواهد بود.
چرا؟ معمولا در تست ها منظور از درخت دودویی درخت دودویی محض استاگر در صورت سوال فقط گفته درخت دودویی مسلماً حداقل گره هاش h+1 خواهد بود.
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
نوشته شده توسط whitehat
ولی فکر نمیکنم اینجوری باشه، البته از روی گزینه ها هم میشه فهمید منظور چی بوده مثلاً اگر در این سوال در گزینه ها h+1 وجود نداشته باشه و 2h+1 وجود داشته باشه میشه فهمید که منظور درخت دودویی محض هست.
درخت مورب جزء درخت دودیی حساب می شود؟
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
در صورت سوال فقط ذکر شده بود یک درخت دودویی درختی است که هر گره آن صفر یا 2 فرزند دارد.و در گزینه ها هم h+1را داده بود و هم 2h+1را.
منظور من از پست قبلی همین بود، درخت مورب را جزء درختان دودویی حساب نکنید !
To follow the path:
Look to the master
Follow the master
Walk with the master
See through the master
Become the master
خوب چون صورت سوال خودش گفته منظرش چه نوع درختی هست 2h+1 صحیح است.
ولی طبق تعریف معمول درخت دودویی، درخت مورب هم دودویی هست.
این همون بهترین و بدترین حالت در جست و جوی دودیی محسوب می شه؟
بدترین حالت جستجوی دودویی ( O( log n و بهترین حالت ( O( 1 هست. بدترین حالت زمانیه که تمام عمق درخت رو برای پیدا کردن عنصر مورد نظر پیمایش کنیم، که log2 n میشه. و بهترین حالت اینه که عنصر ریشه درخت همون عنصر مورد نظر باشه که با یه مقایسه به دست می‌یاد و ( O( 1 میشه.
البته من در اینجا آرایه مرتب برای استفاده از جستجوی دودویی رو با یه درخت جستجوی دودویی معادل کردم. ابهام پیش نیاد.
آخرین ویرایش به وسیله مسعود اقدسی فام : یک شنبه 07 فروردین 1390 در 10:59 صبح
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول