عملیات های روی درخت های حست وجو یعنی 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/