بعد از اضافه کردن عنصر ۱۴ پیمایش پیش ترتیب رو خواسته .
من یه مقدار در روشی که چرخش باید بدیم شک کردم می شه یه راهنمایی کنین
روی چه راس هایی چرخش انجام داده ؟؟شما با چند تا چرخش این رو در میارین ؟
من راهی رو میگم که خودم بهش رسیدم و فکر کنم درست باشه. به این صورت که پس از اضافه کردن گره (گره ۱۴)اگر مشکلی در توازن درخت ایجاد شد باید اصلاح شود. برای این کار از سمت گره ایجاد شده به سمت بالا حرکت می کنیم تا اینکه به اولین گره ای برسیم که مشکل توازن در زیردرخت چپ و راستش دارد (گره ۱۰). این گره مکانش باید عوض شود و گره ای دیگر جایگزینش شود. برای پیدا کردن گره تعویضی با گره ۱۰، به فرزندان این گره نگاه می کنیم. اگر مسیر فرزند راست و سپس چپ وجود داشت(۱۲ که در اینجا وجود دارد) باید این گره ۱۲ جایگزین آن شود، در غیر این صورت اگر مسیر فرزند چپ و سپس راست وجود داشت، همین کار را برای آن می کردیم. تنها یکی از این حالات اتفاق می افتد. با جایگذاری ۱۲ به جای ۱۰، ۱۰ به پایین حرکت می کند و بقیه گره ها نیز به همان ترتیب قرار می گیرند. تنها یک حالت باقی می ماند. درختی را فرض کنید که گره های ۲۰ ۳۰ ۴۰ به آن اضافه شده باشد. در این صورت درخت ما در گره ۲۰ مشکل دارد اما این گره مسیر راست چپ و یا چپ راست ندارد.(کلا مسیر چپ ندارد). در این حالت تنها کافیست فرزند موجود در اینجا راست (۳۰) جایگزین ۲۰ شود و بنابراین ۲۰ به چپ و ۴۰ نیز راست قرار می گیرد. امیدوارم توضیحم مفید واقع شه.
۱- ابتدا ۱۴ به سمت راست ۱۲ اضافه میشه.
۲- حالا باید AVL متوازی بشه.
۳- بین ۱۵,۱۲,۱۰ باید ۲ جابجایی کنیم. یعنی ۱۲ میاد جای ۱۰ و خود ۱۰ هم میاد سمت راست ۱۲/
۴- عدد ۵ میاد سمت راست ۱۰
۵- عدد ۱۴ هم میاد سمت راست ۱۵
امیدوارم گرفته باشید.
حالا زمان این کار چقدره؟ یعنی می خوایم یک درختو به AVL تبدیل کنیم در هر گام
(۱۳ بهمن ۱۳۹۱ ۰۳:۳۹ ب.ظ)mahdiii نوشته شده توسط: من راهی رو میگم که خودم بهش رسیدم و فکر کنم درست باشه. به این صورت که پس از اضافه کردن گره (گره ۱۴)اگر مشکلی در توازن درخت ایجاد شد باید اصلاح شود. برای این کار از سمت گره ایجاد شده به سمت بالا حرکت می کنیم تا اینکه به اولین گره ای برسیم که مشکل توازن در زیردرخت چپ و راستش دارد (گره ۱۰). این گره مکانش باید عوض شود و گره ای دیگر جایگزینش شود.
مرسی این نکته ای بود که بهش دقت نمی کردم و همش از نود راس شروع می کردم .
(۱۳ بهمن ۱۳۹۱ ۰۹:۴۹ ب.ظ)adel28 نوشته شده توسط: ۱- ابتدا ۱۴ به سمت راست ۱۲ اضافه میشه.
۲- حالا باید AVL متوازی بشه.
۳- بین ۱۵,۱۲,۱۰ باید ۲ جابجایی کنیم. یعنی ۱۲ میاد جای ۱۰ و خود ۱۰ هم میاد سمت راست ۱۲/
۴- عدد ۵ میاد سمت راست ۱۰
۵- عدد ۱۴ هم میاد سمت راست ۱۵
امیدوارم گرفته باشید.
نه دوست عزیز من چرخش هاش رو می خواستم و قانونش رو . شما چون مسلطی دیگه سزیع تشخیص می دی.
مرسی دوستان الان تو پوران دیدم که ۴ نوع چرخش رو گفته .
به این نوع گفته چرخش right left ..چرخش اول چرخش به راست و ۱۲ میاد جای ۱۵ ، چرخش دوم ۱۲ میاد جای ۱۰
(۱۳ بهمن ۱۳۹۱ ۱۰:۳۰ ب.ظ)mahdiii نوشته شده توسط: حالا زمان این کار چقدره؟ یعنی می خوایم یک درختو به AVL تبدیل کنیم در هر گام
فکر کنم ماکزیمم دیگه n باشه .
حالا بقیم نظرشون رو بگن عالی
دقیقا چهار چرخش داریم الآن منم نگاه کردم. همونا رو یاد بگیرید خارج از اون حالات نیست.
این چهار حالتم هر کدوم قانون خاص خودشو داره و بر اساس اینکه گره ایجاد شده در زیر درخت چپ یا راست فرزند چپ یا راست گره محور قرار بگیره تعیین میشه.RR,RL,LR,LL
(۱۴ بهمن ۱۳۹۱ ۱۲:۵۱ ق.ظ)ana_12345 نوشته شده توسط: نه دوست عزیز من چرخش هاش رو می خواستم و قانونش رو . شما چون مسلطی دیگه سزیع تشخیص می دی.
مرسی دوستان الان تو پوران دیدم که ۴ نوع چرخش رو گفته .
به این نوع گفته چرخش right left ..چرخش اول چرخش به راست و ۱۲ میاد جای ۱۵ ، چرخش دوم ۱۲ میاد جای ۱۰
قانون چرخش هاش که تقریبا تو همه کتاب ها هست.
من این چرخشارو درست متوجه نمیشمم میشه قانون کلیشونو یکی بگه؟؟؟؟؟؟