PDA

View Full Version : سوال: این درخت متوازنه ؟


majidmir
شنبه 30 خرداد 1388, 13:15 عصر
سلام
این درخت متوازن هست یا نه ؟ اگه متوازنه تو کدوم برگ ها توازن رخ میده ؟
http://www.freezpic.com/pics/6b3952ace558de589d7ac6629774b85a.JPG
pesar irooni
یک شنبه 31 خرداد 1388, 18:11 عصر
این درخت یک درخت متوازن یا AVL هست چون تفاوت سطح دوبرگ حداکثر 1 است و هیچ دو برگ با بیش از یک سطح فاصله وجود نداره.
majidmir
یک شنبه 31 خرداد 1388, 20:42 عصر
این درخت یک درخت متوازن یا AVL هست چون تفاوت سطح دوبرگ حداکثر 1 است و هیچ دو برگ با بیش از یک سطح فاصله وجود نداره.
سلام
دوست عزیز کدوم دو برگ رو در نظر گرفته که متوازن شده ؟
Mbt925
دوشنبه 01 تیر 1388, 16:56 عصر
سلام
این درخت متوازن هست یا نه ؟ اگه متوازنه تو کدوم برگ ها توازن رخ میده ؟
http://www.freezpic.com/pics/6b3952ace558de589d7ac6629774b85a.JPG


ابتدا به توضيحات زير توجه كنيد:

تعريف: درخت AVL يك درخت BST موازنه هست.

BST مخفف درخت جستجوي دودويي هست. در اين درخت مقدار هر فرزند سمت چپ از ريشه كمتر و زيردرخت سمت راست از ريشه بيشتره.

موازنه به اين معني اه كه براي هر گره موجود در درخت، اختلاف ارتفاع زيردرخت سمت راست و چپ كمتر يا مساوي يك باشه.

----------------

درختي كه شما مثال زديد :

- BST نيست بخاطره وجود گره 25 ( از گره 50 كوچكتره)

- موازنه نيست بخاطره وجود گره 41 (ارتفاع زيردرخت سمت چپ = 2 --- ارتفاع زيردرخت سمت راست= 0 ==> اختلاف ارتفاعشون دو هست كه بيشتر از يكه )

==> در نتيجه درخت بالا AVL هم نيست.
pesar irooni
سه شنبه 02 تیر 1388, 18:01 عصر
دوستمون راست میگه. من متوجه گره 41 نشده بودم. عذر میخوام.
اما میشه توازن رو جدا از BST هم در نظر گرفت ولی به هر حال دیگه AVL نمیشه که من به این هم توجه نکردم.