با سلام. عزیزان ارتفاع یک هیپ درجه 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 حساب کردم .اگه ۴ تا عنصر داشته باشیم ارتفاع با فرمول بالا میشه۲ در حالیکه باید ۱ بدست بیاد.
باید دقت کنید که در آخرین سطح یک درخت کامل تعداد گره‌ها میتونه بین ۱ تا [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 میشه ۲ و h=1 بدست میاد.
البته گفتم این دو فرمول برای وقتی هست که یا حداقل گره رو داشته باشیم یا حداکثر و در هر صورت ارتفاع h هست.