(۱۴ دى ۱۳۹۲ ۰۴:۲۰ ب.ظ)sonia1990 نوشته شده توسط:  یکی از سوالات کامپیوتر ۸۴ گفته با چند عدد دوران می توان درخت دودویی جستجوی سمت چپ را به درخت سمت راست تبدیل کرد؟
(ببخشید که شکل رو نمیتونم بزارم حتما همه توی کتاباشون دارن)

کتاب مقسمی گفته درخت چپ می تواند با ورودی dcbagef ساخته شده باشد حالا با ۳جابه جایی عنصرهای کنار هم درخت چپ بدست میاد یعنی با ترتیب ورودی dbcafeg
تا اینجا مشکلی ندارم(یعنی بدون رسم شکل و دوران سوال رو حل میکنم).

سوال من روی ترتیب شکل هاست اینکه اول دوران به راست میده بعد به چپ بعد به راست! ترتیب این دوران ها و شکل ها رو متوجه نمیشم

دوران ها توی درخت AVL بر اساس ارتفاع نود ها هستش،اول اینکه باید ببینیم که ارتفاع زیر درخت چپ بزرگ تر شده با اضافع کردنه نود جدید یا زیر درخت راست،بعدش باید ببینیم نود اضافه شده سمت چپ پدرشه یا سمته راستش و بر اساس چپ یا راست بودن دوران بدیم. ولی کلا اینجوری فرمول بندی شده یاد نگیره ادم بهتره
ولی در کل
۱/اگر با اضافه کردن نود ارتفاع درخت سمت چپ +۲ شد، و نود در سمت چپ پدرش قرار داشت،جد این نود رو به سمت راست دوران میدیم. مثلا ۳ و ۲ و ۱ اضافه شدن و نود جدید یک هستش و نود جد ۳ هستش، ۳ رو به سمت راست دوران میدیم و ۲ میشه ریشه، ۱ میشه درخت چپ و ۳ میشه درخت راست

۲/اگر با اضافه کردن نود ارتفاع درخت راست +۲ شد و نود هم سمت راست نود پدر قرار گرفت،جدش رو به سمت چپ دوران میدیم
۳/اگر نود یه درخت سمت چپ اضافه شد،ولی در سمت راست پدرش قرار گرفت، با یک دوران به چپ پدرشو میاریم زیر نود جدید(یعنی جای پدر و فرزند عوض میشه) اینجوری شکل شبیه حالت ۱ میشه که گفتم،حالا با یه دوران راست(مثه حالت ۱عمل میکنیم) ریشه میاد سمت راست، پدر میشه ریشه و فرزند جدید میشه درخت سمت چپ
۴/اگر نود به درخت سمت راست اضافه شد ولی سمت چپ پدرش قرار گرفت،با یه دوران به راست پدرش میاد زیرش،یعنی با دوران به راست جای پدر و فرزندو عوض میکنیم اینجوری شکل شبیه حالت ۲ شده،حالا با یه دوران به چپ ریشه این سه گره، میشه فرزند چپ، پدر میشه ریشه و نود اخر هم میشه فرزند راست

کلا حالتی که شبیه ۱ یا ۲ نیست رو اول با دوران به شکل ۱ یا دو در میاریم بعدش مثه حالت اول یا دوم عمل میکنیم.پس بجای حفظ کردن چرخشای چپ یا راست کافیه شکلشونو یادمون بمونه