سلام
این درخت متوازن هست یا نه ؟ اگه متوازنه تو کدوم برگ ها توازن رخ میده ؟
این درخت متوازنه ؟
سلام
این درخت متوازن هست یا نه ؟ اگه متوازنه تو کدوم برگ ها توازن رخ میده ؟
این درخت یک درخت متوازن یا AVL هست چون تفاوت سطح دوبرگ حداکثر 1 است و هیچ دو برگ با بیش از یک سطح فاصله وجود نداره.
سلامنوشته شده توسط pesar irooni
دوست عزیز کدوم دو برگ رو در نظر گرفته که متوازن شده ؟
ابتدا به توضيحات زير توجه كنيد:سلام
این درخت متوازن هست یا نه ؟ اگه متوازنه تو کدوم برگ ها توازن رخ میده ؟
تعريف: درخت AVL يك درخت BST موازنه هست.
BST مخفف درخت جستجوي دودويي هست. در اين درخت مقدار هر فرزند سمت چپ از ريشه كمتر و زيردرخت سمت راست از ريشه بيشتره.
موازنه به اين معني اه كه براي هر گره موجود در درخت، اختلاف ارتفاع زيردرخت سمت راست و چپ كمتر يا مساوي يك باشه.
----------------
درختي كه شما مثال زديد :
- BST نيست بخاطره وجود گره 25 ( از گره 50 كوچكتره)
- موازنه نيست بخاطره وجود گره 41 (ارتفاع زيردرخت سمت چپ = 2 --- ارتفاع زيردرخت سمت راست= 0 ==> اختلاف ارتفاعشون دو هست كه بيشتر از يكه )
==> در نتيجه درخت بالا AVL هم نيست.
دوستمون راست میگه. من متوجه گره 41 نشده بودم. عذر میخوام.
اما میشه توازن رو جدا از BST هم در نظر گرفت ولی به هر حال دیگه AVL نمیشه که من به این هم توجه نکردم.
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول