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

با سلام. عزیزان ارتفاع یک هیپ درجه d و یا هر درخت کاملی با این درجه و تعداد گره های n از چه مرتبه ای میشه؟

تله گذاشتی؟!
ارتفاعش که میشه‌: [tex]\left \lceil \log_{d}(d-1) \log_{d}n -1 \right \rceil[/tex]
{فکر نکنی اینو بلد بودم! از توی اینترنت پیداش کردم.}
ولی شما مرتبه‌ی پیدا کردن ارتفاع رو خواستی،که از دید من میشه [tex]O(1)[/tex] چونکه n را توی صورت سوال داریم.ولی اگر n را نداشتیم مرتبه میشد[tex]O(\log_{d}n)[/tex] (اگر d رو کمتر از n در نظر بگیریم.)

اگه ارتفاع رو بخوایم بدونیم ،واسه یه درخت کامل درجه d با n گره ارتفاع رو همیشه نمیشه گرفت [tex]( log_{d}(n))[/tex].آخه من واسه d=3 حساب کردم .اگه 4 تا عنصر داشته باشیم ارتفاع با فرمول بالا میشه2 در حالیکه باید 1 بدست بیاد.

باید دقت کنید که در آخرین سطح یک درخت کامل تعداد گره‌ها میتونه بین 1 تا [tex]d^{h}[/tex]
باشه .

پس نمیتونید فرمول خاصی برای اون بگید.مگر اینکه تعداد n رو داشته باشید سعی کنید فرمول حفظ نکنید با تحلیل درخت ارتفاع رو محاسبه کنید.

بله من یه لحظه با درخت پر اشتباه کردم بعدش که گفتم باید خودتون تحلیل کنید و فرمول قبل حداکثر n رو به ما میداد . حداقلش هم میشه

[tex]d^{h}-1/d-1 1 =d^{h} d-2/d-1[/tex]


برای اون مثال که d=3 و n=4 بود چون درخت پره. از فرمول اول میریم یعنی

[tex]d^{h 1}-1/d-1 [/tex]
[tex]4=3^{h 1}-1/3-1 [/tex] یعنی h+1 میشه 2 و h=1 بدست میاد.

البته گفتم این دو فرمول برای وقتی هست که یا حداقل گره رو داشته باشیم یا حداکثر و در هر صورت ارتفاع h هست.