در این قسمت تیم کدگیت را با آموزش درخت AVL در جاوا همراهی کنید. در این جلسه به معرفی یکی دیگر از ساختار دادهها میپردازیم. با معرفی درخت AVL کار خود را آغاز کرده و در ادامه به پیاده سازی این درخت در جاوا خواهیم پرداخت. پیشنهاد میکنیم قبل از مطالعه این جلسه، آموزشهای زیر را بررسی کنید:
- درخت دودویی جست جو در جاوا
- شی گرایی در جاوا
- متد در جاوا
- آشنایی با روش بازگشتی
- Constructor در جاوا
- آشنایی با if
- آشنایی با for
- آشنایی با this
- While در جاوا
درخت AVL
عملیاتهای درج گره و حذف گره در درخت دودویی جستجو به طور معمول O(logn) است. اما درخت جستجوی دودویی زیر را ببینید:

در این شرایط حذف و اضافه کردن گره زمان O(n) میگیرد. اگر در درخت فوق پس از هر حذف و یا اضافه کردن درخت، ما تضمین کنیم ارتفاع درخت log n است پس هزینه درج و حذف همانطور که انتظار داریم Log n خواهد بود (در بدترین حالت). درخت AVL نوعی درخت جستجوی دودویی با ارتفاع متعادل است بدین معنی که تضمین میکند ارتفاع درخت همیشه O(logn) است.
در این آموزش تنها به توضیح و پیاده سازی عملیات درج گره در درخت AVL خواهیم پرداخت. در جلسات آینده عملیاتهای مانند حذف و … نیز توضیح داده میشود.
درج گره در درخت AVL
برای درج گره در درخت AVL ابتدا همانند BST عمل کرده و گره را در درخت درج میکنیم. سپس با عملیاتی (که توضیح خواهیم داد) ارتفاع درخت را متعادل میکنیم. برای متعادل کردن ارتفاع درخت AVL ما نیاز به عملیاتهایی به نام چرخش راست و چرخش چپ داریم. تصویر زیر این چرخشها را به صورت ساده نمایش داده است:

مطابق با تصویر فوق متغیرهای T1 و T2 و T3 فرزندان درختی هستند که ریشه آن گره X یا Y است. دقت کنید چرخش چپ و راست به صورت همزمان در یک تصویر آورده شده است.
برای درج گره در درخت AVL، مانند درخت BST عمل کرده و گره را وارد درخت میکنیم. پس از وارد کردن گره بررسی میکنیم درخت ما شرط AVL را دارد (متعادل هست یا خیر). برای ایجاد تعادل در درخت AVL حالات زیر در درخت رخ خواهد داد:
- Y فرزند چپ z و x فرزند چپ y است:

- Y فرزند چپ z و x فرزند راست y است:

- Y فرزند راست z و x فرزند راست y است:

- Y فرزند راست z و x فرزند چپ y است:

پیاده سازی درخت AVL در جاوا
برای پیاده سازی درخت AVL در جاوا همانند پیاده سازی درخت BST یک کلاس Node ایجاد میکنیم. سورس این کلاس مانند درخت BST بوده و تنها برای نگهداری ارتفاع گرهها متغیری به نام Height به آن اضافه کردیم. کد کلاس Node به صورت زیر است:
public class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
public Node(int key, int height) {
this.key = key;
this.height = height;
}
}
حال نوبت به پیاده سازی درخت است. ابتدا کد درخت AVL را با هم ببینیم:
public class AVLTree {
private Node root;
private int height(Node x) {
if (x == null)
return -1;
return x.height;
}
public void insert(int key) {
root = put(root, key);
}
private Node put(Node x, int key) {
if (x == null)
return new Node(key, 0);
if (key < x.key) {
x.left = put(x.left, key);
} else if (key > x.key) {
x.right = put(x.right, key);
} else {
return x;
}
x.height = 1 + Math.max(height(x.left), height(x.right));
return balance(x);
}
private Node balance(Node x) {
if (balanceFactor(x) < -1) {
if (balanceFactor(x.right) > 0) {
x.right = rotateRight(x.right);
}
x = rotateLeft(x);
} else if (balanceFactor(x) > 1) {
if (balanceFactor(x.left) < 0) {
x.left = rotateLeft(x.left);
}
x = rotateRight(x);
}
return x;
}
private int balanceFactor(Node x) {
return height(x.left) - height(x.right);
}
private Node rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
y.right = x;
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right));
return y;
}
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right));
return y;
}
public void inOrder() {
inOrder(root);
}
private void inOrder(Node node)
{
if (node != null)
{
inOrder(node.left);
System.out.print(node.key + " ");
inOrder(node.right);
}
}
}
متدها و متغیرهای استفاده شده در کد بالا به صورت زیر میباشد:
- متد Height: ارتفاع یک گره در درخت را برمیگرداند.
- متدهای insert و Put : متد Put به صورت بازگشتی یک گره را در دخت اضافه میکند. متد insert، متد Put را صدا میزند.
- متد Balance: این متد یک گره را به عنوان ورودی گرفته و بررسی میکند آیا شرایط درخت AVL برای آن گره برقرار است یا خیر.
- متد BalanceFactor: این متد یک گره را به عنوان ورودی میگیرد و اختلاف زیردرخت راست و چپ آن را برمیگرداند. وقتی این متد عدد بزرگتر از 1 را برمیگرداند بدین معنی است که درخت متعادل نیست و ما با چرخش (چرخش راست یا چرخش چپ سپس چرخش راست) نیاز داریم. در صورتی که عدد کوچکتر از -1 برگردانده شود یعنی ما در شرایط عکس حالت قبل هستیم.
- متد RotateLeft: این متد چرخش چپ را انجام میدهد.
- متد RotateRight: این متد چرخش راست را انجام میدهد.
- متد Inorder: این متد برای پیمایش درخت میباشد. از این متد برای چاپ گرههای درخت در این مثال استفاده خواهد شد.
تست برنامه
برای تست کدهای بالا، کد Main زیر را پیاده سازی کنید:
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.insert(9);
tree.insert(5);
tree.insert(10);
tree.insert(0);
tree.insert(6);
tree.insert(11);
tree.insert(-1);
tree.insert(1);
tree.insert(2);
tree.inOrder();
}
خروجی کد بالا به صورت زیر است:
-1 0 1 2 5 6 9 10 11
اگر سوالی در خصوص درخت AVL دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.