با چه هزینه زمانی می توان تشخیص داد که یک BST یک AVL است؟
سلام. به نظرم nlogn کافی باشه. کافیه درخت پیمایش بشه. درصورتی که درخت avl نبود و عمقش بیشتر از logn بود سریعتر متوجه متوازن نبودن میشیم و به جواب میرسیم.
سلام
جواب کلید n زده
در واقع با بررسی هر گره فکر میکنم این رو نتیجه گرفته
در واقع هر گره اختلاف ارتفاع چپ و راست رو نگه میداره
البته شاید کلید اشتباه باشه
(۲۹ خرداد ۱۳۹۴ ۰۹:۲۴ ب.ظ)oatashgah69 نوشته شده توسط: سلام
جواب کلید n زده
در واقع با بررسی هر گره فکر میکنم این رو نتیجه گرفته
در واقع هر گره اختلاف ارتفاع چپ و راست رو نگه میداره
البته شاید کلید اشتباه باشه
به نظرم برای این کار باید بدون پیمایش درخت این محاسبه رو انجام بده. با روش بررسی تمام گره ها بعید میدونم کمتر از nlogn بشه.