PDA

View Full Version : سوال: توضیح در مورد درج الگوریتم avl



vb8334
دوشنبه 18 مرداد 1389, 11:56 صبح
با سلام به تمامی دوستان

دوستان اگه کسی اطلاعاتی در مورد الگوریتم avl روش درج کردن رو داره ممنون میشم

توضیح بده یا اگه مقاله یا کتاب الکترونیکی دارید اینجا قرار بدین

ممنون

vb8334
سه شنبه 19 مرداد 1389, 17:12 عصر
دوستان کسی در مورد این موضوع اطلاعاتی نداره

کسییییییییییییییییییییی نیست به ما کمک کنه

ممنون

vb8334
پنج شنبه 21 مرداد 1389, 10:54 صبح
دوستان من خودم این مطالب رو خوندم ولی هیچی نفهمیدم این توضیحات برای درج کردن هستش

اینجا منظورش از فاکتور توازن چیه؟

درج کردن :

اگر فاکتور توازن ۱-، ۰ یا ۱ باشد درخت در حال حاضر در حالت متوازن است و هیچ چرخش دیگری نیاز ندارد.
اگر فاکتور توازن ۲ یا -۲ شود، درخت با ریشه این گره نا متوازن است ویک چرخش درخت نیاز است.حد اکثر یک یا دو چرخش برای متوازن کردن درخت نیاز خواهد بود.
چهار حالت اساسی برای محاسبه وجود دارد که دو تای آنها متناسب، یا به عبارت دیگر متقارن با دو حالت دیگر است.برای سادگی ریشه زیر در خت نا متوازن را P، فرزند سمت راست آن را R، و فزند سمت چپ را L بنامید.اگر فاکتور توازنP مساوی ۲ بود یعنی زیر درخت سمت راست سنگین تر از زیر درخت سمت چپ است وبایدفاکتور توازت فرزند سمت راست بررسی شود.اگر فاکتور توازن (R)برابر ۱ است، این بدان معنا است که درج در سمت رایت آن گره رخ داده و یک چرخش درخت (http://fa.wikipedia.org/wiki/%DA%86%D8%B1%D8%AE%D8%B4_%D8%AF%D8%B1%D8%AE%D8%AA) به چپ با محوریت ریشه P است.اگر فاکتور توازن R برابر ۱- باشد، این بدان معنا است که درج در سمت چپ گره اتفاق افتاده‌است.در این حالت نیاز به دو بار چرخش می‌باشد.اولین چرخش به سمت راست با محوریت R به عنوان ریشه وسپس یک چرخش به سمت چپ با محوریت P است.