نحوه نوشتن درخت ای وی ال یا AVL tree

Question

دوستان AVL tree چیه ؟

بعد توابع مثل insert search delete داخلش چطوری نوشته میشن ؟

Answer 1

عملیات های روی درخت های حست وجو یعنی search,insert ,delete همشون از مرتبه logh هستن که h ارتفاع درخته  .برای این که h کمتر بشه از درخت های متوازن استفاده میکنن که حداقل h رو داشته باشیم

avl یک درخت جست و جوی تقریبا متوازن هستش

 تقریبا متوازنه(height balanced tree)  وکاملا متوازن نیست چون ارتفاع فرزند های چپ و راست هر گره  میتونه یک واحد با هم تفاوت داشته باشه

مثلا  درخت های زیر همشون به غیر از مورد آخر height balance هستن .

 

 

حداکثر ارتفاع  AVL ش 1.4logn هستش که  n تعداد گره های درخته .

 کد زیر  درخت جست و جوی معمولی هستش (برای سادگی فقط search ,insert گذاشته شده و کامل نیست ) :

با سی پلاس پلاس

با c

مشکلی که ساختار بالا داره اینه که اگر اطلاعاتی که قبلا مرتب هستن رو داخلش insert کنیم ارتفاع همون n میشه یعنی عملیات های روی درخت به جای این که مرتبشون logn باشه n میشن

مثلا اگر ۴-۷-۱۶-۲۰-۳۷-۳۸-۴۳ رو به ترتیب داخل درخت insert کنیم  درخت به شکل زیر در میاد که ارتفاعش همون n هست .

 

همون طوری که بالا گفتم AVL ساختاریه که مشکل بالا رو نداره و زمانی که اطلاعات مرتب شده هم واردش بشن درخت بصورت متوازن در میاد .

 

 

برای این که درخت تبدیل به AVL بشه کافیه که insert کد بالا رو عوض کنیم

برای نوشتن insert از 2 تا عملیات استفاده می کنن که اصطلاخا بهشون left rotate,right rotate میگن

 

Left Rotate

 

فرض کنید بعد از اضافه کردن عنصر  درخت ما به این شکل در امد :

 

حالا اگر ما 2 رو با 1 جابه جا کنیم و دوباره درخت رو بسازیم درخت به این شکل در میاد :

 

 

یعنی برای متوازن کردن درخت کافیه که 2 رو بصورت ریشه درخت قرار بدیم 1 رو به عنوان فرزند سمت چپ 2 قرار بدیم (مرحله 1)

فرزند های سمت چپ 2 رو به عنوان فرزند سمت راست 1 قرار بدیم (این جا 2 فرزند چپ نداره )  (مرحله 2)

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

در شکل زیر یک مثال کامل تر برای left rotation قرار داده شده :

 

کد مرحله بالا به این شکله :

    leftRotate(BST<T>* root)
    {    
        BST<T>* node_Right_Left=root->right->left;  
        BST<T>* newRoot=root->right;        
        //step 1
        newRoot->left=root;
        root->right=root->right->right;    
        //step 2
        newRoot->left->right=node_Right_Left;
    }

 

 

RIGHT ROTATE

 

این عملیات هم تقریبا مثل همون عملیات بالا انجام میشه ولی با این تفاوت که ریشه به سمت راست میره :

 

2 رو به عنوان ریشه قرار میدیم و 3 رو به عنوان فرزند سمت راست 2 قرارمیدیم (مرحله 1)

فرزند های سمت راست 2 رو به عنوان فرزند سمت چپ3 قرار میدیم(این جا 2 فرزند چپ نداره )  (مرحله 2)

مثال :

 

کد :

    rightRotate(BST<T>* root)
    {    
        BST<T>* node_Left_Right=root->left->right;  
        BST<T>* newRoot=root->left;        
        //step 1
        newRoot->right=root;
        root->left=root->left->left;    
        //step 2
        newRoot->right->left=node_Left_Right;
    }

 

بعضی وقت ها برای متوازن شدن در خت به انجام 2 بار left rotate , right rotate نیاز داریم شکل زیر رو در نظر بگیرید .

 

 

برای این که بفهمیم چه موقع نیاز به left و right نیاز داریم برای هر گره اختلاف بین ارتفاع ریشه سمت چپ و سمت راست رو حساب می کنیم (balanced factor )اگر 0 یا 1 یا -1 نبود یعنی نیاز به چرخش داریم .

مثلا داخل شکل بالا این اختلاف برای گره ریشه -2 و 2 هستش پس نیاز به چرخش داریم که با چرخش در 2 مرحله درخت متوازن شده .

شبه کد این کار به این شکله :

if (balance_factor(L) == 2) { //The left column
   let P=left_child(L)
   if (balance_factor(P) == -1) { //The "Left Right Case"
      rotate_left(P) //reduce to "Left Left Case"
   }
   //Left Left Case
   rotate_right(L);
 } else { // balance_factor(L) == -2, the right column
   let P=right_child(L)
   if (balance_factor(P) == 1) { //The "Right Left Case"
      rotate_right(P) //reduce to "Right Right Case"
   }
   //Right Right Case
   rotate_left(L);
 }

 

کد کامل این ساختار به زبان ++C رو میتونید این جا ببینید  : avl tree

 

منابع :

http://epaperpress.com/sortsearch/bin.html

http://en.wikipedia.org/wiki/AVL_tree

https://www.youtube.com/watch?v=FNeL18KsWPc

https://www.youtube.com/watch?v=YKt1kquKScY

http://pages.cs.wisc.edu/~paton/readings/liblitVersion/AVL-Tree-Rotations.pdf

http://stackoverflow.com/questions/19278236/avl-tree-balance

http://stackoverflow.com/questions/1986821/balance-factor-of-nodes-in-avl-tree

http://www.sanfoundry.com/cpp-program-implement-avl-trees/