درخت ای‌وی‌ال

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو
درخت ای‌وی‌ال
نوع درخت
سال اختراع شدن ۱۹۶۲
اختراع شده توسط جرجی اندلسون-ولسکی و اوگنی لاندیس
پیچیدگی زمانی
بر حسب نماد اوی بزرگ
میانگین بدترین حالت
فضا O(n)‎ O(n)‎
جستجو O(log n)‎ O(log n)‎
درج O(log n)‎
حذف O(log n)‎ O(log n)‎

در علوم رایانه، درخت ای‌وی‌ال (به انگلیسی: AVL tree)، یک نوع درخت جستجوی دودویی خود متوازن‌کننده‌است و اولین ساختار داده‌ای می‌باشد که اختراع شد.[۱] در یک درخت ای‌وی‌ال اختلاف ارتفاع دو زیر شاخه‌ی هر گره حداکثر برابر یک است. بنابراین به این درخت، درخت با ارتفاع متوازن نیز گفته می‌شود. توجه کنید که عملیات درج، حذف و جستجو در یک درخت ای‌وی‌ال در بدترین حالت و حالت متوسط به اندازه خواهد بود به‌طوری‌که n تعداد گره‌های درخت می‌باشد. در عملیات درج و حذف ممکن است نیاز باشد که درخت به وسیله چرخش درخت‌ها، یک یا چند بار متوازن گردد.

عنوان AVL TREE از اول نام‌های دو مخترع آن به نام‌های G.M. Adelson-Velsky و E.M. Landis، که مقاله خود را در سال ۱۹۶۲ با موضوع«یک الگوریتم برای سازماندهی اطلاعات» منتشر کردند گرفته شده‌است.

درخت‌های ای‌وی‌ال غالباً با درخت‌های قرمز-سیاه مقایسه می‌شود. دلیل آن این است که هر دو داده ساختار قادر به انجام یک مجموعه از عملیات یکسان می‌باشند. در درخت‌های قرمز-سیاه نیز زمان لازم برای انجام عملیات اساسی به اندازه است. درخت‌های ای‌وی‌ال برای کاربردهای وسیع و گسترده جستجو بهتر از درخت‌های قرمز-سیاه هستند. الگوریتم‌های متوازن کردن درخت‌ها در بسیاری از دوره‌های علوم رایانه ظاهر شده و مورد استفاده قرار می‌گیرد.[۲]

AVL Tree Example

تعریف اولیه[ویرایش]

ضریب توازن هر گره، تفاضل ارتفاع زیردرخت چپ آن گره از ارتفاع زیردرخت راست آن گره است. برای راس داریم:

[۳]

AVL-tree

هر گره ای که ضریب توازن آن برابر 1، 0 یا 1- باشد به عنوان گره متوازن درنظر گرفته می شود. هر درخت جست‌و‌جوی دودویی که تمام راس های آن متوازن باشند درخت ای‌وی‌ال است.

با دانستن تعریف یک درخت ای‌وی‌ال و ضریب توازن، با اضافه شدن گره جدید و تغییر ارتفاع، می‌توان یک درخت ای‌وی‌ال را متوازن نگه داشت. دقت شود که نیازی به نگه داشتن ارتفاع دقیق هر گره نیست. تنها کافی است برای هر گره ضریب توازن را نگه داریم. در روش قدیمی برای هر گره دو بیت نگه داشته می شد ولی تحقیقات بعدی نشان داد که تنها یک بیت برای هر گره کافی است. به این صورت که برای در هر گره تفاضل ارتفاع گره با از ارتفاع پدرش ذخیره می شود و همانطور که واضح است این مقدار همواره برابر 1 یا 2 است. ارتفاع هر درخت ای‌وی‌ال با تعداد n گره همواره در محدوده زیر قرار دارد:

که در آن با تعریف عدد طلایی   ، و . دلیل این محدوده این است که هر درخت ای‌وی‌ال با ارتفاع h ، حداقل به تعداد Fh+2 – 1 گره دارد که در آن F دنباله فیبوناتچی است.

عملیات[ویرایش]

توصيف تصويري متوازن كردن درخت توسط چرخش هاويك مرحله از مسير بازيابي يه سمت ريشه يراي اصلاح فاكتور توازن گره‌ها.

به‌طور کلی عملیات اساسی در درخت‌های ای‌وی‌ال شامل همان عملیاتی که در درختهای جستجوی دودویی انجام می‌شود می‌باشد، اما اصلاحات وتغییرات به صورت فراخوانی یک یا چند باره چرخش درخت خواهد بود که به باز ذخیره کردن ارتفاع زیر درخت کمک می‌کند.

درج کردن[ویرایش]

اگر ضریب توازن تمام گره ها ۱-، ۰ یا ۱ باشد درخت در حال حاضر متوازن است و هیچ چرخش دیگری نیاز ندارد.

اگر ضریب توازن یک گره ۲ یا ۲- شود، درخت با ریشه این گره نامتوازن است و چرخش درخت نیاز است. حداکثر دو چرخش برای متوازن کردن درخت نیاز خواهد بود.

چهار حالت اساسی برای محاسبه وجود دارد که دو تای آن‌ها متناسب، یا به عبارت دیگر متقارن با دو حالت دیگر است.

برای سادگی ریشه زیر درخت نامتوازن را P، فرزند سمت راست آن را R، و فرزند سمت چپ را L بنامید. اگر ضریب توازن P مساوی ۲ بود یعنی زیر درخت سمت راست سنگین تر از زیر درخت سمت چپ است و باید ضریب توازن فرزند سمت راست بررسی شود. اگر ضریب توازن (R)برابر ۱ است، این بدان معنا است که درج در سمت راست آن گره رخ داده و یک چرخش درخت به چپ با محوریت ریشه P است. اگر ضریب توازن R برابر ۱- باشد، این بدان معنا است که درج در سمت چپ گره اتفاق افتاده‌است. در این حالت نیاز به دو بار چرخش می‌باشد. اولین چرخش به سمت راست با محوریت R به عنوان ریشه و سپس یک چرخش به سمت چپ با محوریت P است.[۴] مراحل کامل متوازن کردن در بخش متوازن‌سازی توضیح داده خواهد شد.

 1 for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
 2     // BalanceFactor(X) has to be updated:
 3     if (Z == right_child(X)) { // The right subtree increases
 4         if (BalanceFactor(X) > 0) { // X is right-heavy
 5             // ===> the temporary BalanceFactor(X) == +2
 6             // ===> rebalancing is required.
 7             G = parent(X); // Save parent of X around rotations
 8             if (BalanceFactor(Z) < 0)      // Right Left Case     (see figure 5)
 9                 N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
10             else                           // Right Right Case    (see figure 4)
11                 N = rotate_Left(X, Z);     // Single rotation Left(X)
12             // After rotation adapt parent link
13         } else {
14             if (BalanceFactor(X) < 0) {
15                 BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
16                 break; // Leave the loop
17             }
18             BalanceFactor(X) = +1;
19             Z = X; // Height(Z) increases by 1
20             continue;
21         }
22     } else { // Z == left_child(X): the left subtree increases
23         if (BalanceFactor(X) < 0) { // X is left-heavy
24             // ===> the temporary BalanceFactor(X) == –2
25             // ===> rebalancing is required.
26             G = parent(X); // Save parent of X around rotations
27             if (BalanceFactor(Z) > 0)      // Left Right Case
28                 N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
29             else                           // Left Left Case
30                 N = rotate_Right(X, Z);    // Single rotation Right(X)
31             // After rotation adapt parent link
32         } else {
33             if (BalanceFactor(X) > 0) {
34                 BalanceFactor(X) = 0; // Z’s height increase is absorbed at X.
35                 break; // Leave the loop
36             }
37             BalanceFactor(X) = 1;
38             Z = X; // Height(Z) increases by 1
39             continue;
40         }
41     }
42     // After a rotation adapt parent link:
43     // N is the new root of the rotated subtree
44     // Height does not change: Height(N) == old Height(X)
45     parent(N) = G;
46     if (G != null) {
47         if (X == left_child(G))
48             left_child(G) = N;
49         else
50             right_child(G) = N;
51         break;
52     } else {
53         tree->root = N; // N is the new root of the total tree
54         break;
55     }
56     // There is no fall thru, only break; or continue;
57 }
58 // Unless loop is left via break, the height of the total tree increases by 1.

حذف کردن[ویرایش]

اگر گره یک برگ باشد می‌توان آن را حذف کرد. در غیر این صورت آن را با بزرگ‌ترین گره در زیر درخت سمت چپش یا با کوچک‌ترین گره در زیر درخت سمت راستش جایگزین می‌کنیم و محل جایگزینی را به خاطر می‌سپاریم .سپس آن گره را (که حالا حداکثر یک بچه دارد) در محل جایگزینی به راحتی حذف میکنیم. بعد از حذف گره مسیری را که از سمت محل جایگزینی به طرف ریشه‌ است را پیمایش می‌کنیم و ضریبهای توازن را در صورت لزوم اصلاح می‌کنیم.(این عمل را بازیابی مسیر می‌نامیم). اگر در طول مسیر در یک گره ضریب توازن ۲ یا ۲- شود ؛، این بدان معنا است که زیر درخت با ریشه آن گره نامتوازن است و برای متوازن شدن نیاز به چرخش می‌باشد. هزینه صرف شده برای حذف کردن برابر جمع هزینه‌های لازم برای جستجو و بازیابی مسیر است که هر دو به اندازه می‌باشد. در نتیجه هزینه لازم برای حذف نیز از مرتبه می‌باشد. عملیات چرخش در قسمت متوازن‌سازی توزیح داده شده است.

  1 class Node
  2 {
  3     int key, height;
  4     Node left, right;
  5  
  6     Node(int d)
  7     {
  8         key = d;
  9         height = 1;
 10     }
 11 }
 12  
 13 class AVLTree
 14 {
 15     Node root;
 16  
 17     // A utility function to get height of the tree
 18     int height(Node N)
 19     {
 20         if (N == null)
 21              return 0;
 22          return N.height;
 23     }
 24  
 25     // A utility function to get maximum of two integers
 26     int max(int a, int b)
 27     {
 28         return (a > b) ? a : b;
 29     }
 30  
 31     // A utility function to right rotate subtree rooted with y
 32     // See the diagram given above.
 33     Node rightRotate(Node y)
 34     {
 35         Node x = y.left;
 36         Node T2 = x.right;
 37  
 38         // Perform rotation
 39         x.right = y;
 40         y.left = T2;
 41  
 42         // Update heights
 43         y.height = max(height(y.left), height(y.right)) + 1;
 44         x.height = max(height(x.left), height(x.right)) + 1;
 45  
 46         // Return new root
 47         return x;
 48     }
 49  
 50     // A utility function to left rotate subtree rooted with x
 51     // See the diagram given above.
 52     Node leftRotate(Node x)
 53     {
 54         Node y = x.right;
 55         Node T2 = y.left;
 56  
 57         // Perform rotation
 58         y.left = x;
 59         x.right = T2;
 60  
 61         //  Update heights
 62         x.height = max(height(x.left), height(x.right)) + 1;
 63         y.height = max(height(y.left), height(y.right)) + 1;
 64  
 65         // Return new root
 66         return y;
 67     }
 68  
 69     // Get Balance factor of node N
 70     int getBalance(Node N)
 71     {
 72         if (N == null)
 73             return 0;
 74         return height(N.left) - height(N.right);
 75     }
 76  
 77     /* Given a non-empty binary search tree, return the
 78        node with minimum key value found in that tree.
 79        Note that the entire tree does not need to be
 80        searched. */
 81     Node minValueNode(Node node)
 82     {
 83         Node current = node;
 84  
 85         /* loop down to find the leftmost leaf */
 86         while (current.left != null)
 87            current = current.left;
 88  
 89         return current;
 90     }
 91  
 92     Node deleteNode(Node root, int key)
 93     {
 94         // STEP 1: PERFORM STANDARD BST DELETE
 95         if (root == null)
 96             return root;
 97  
 98         // If the key to be deleted is smaller than
 99         // the root's key, then it lies in left subtree
100         if (key < root.key)
101             root.left = deleteNode(root.left, key);
102  
103         // If the key to be deleted is greater than the
104         // root's key, then it lies in right subtree
105         else if (key > root.key)
106             root.right = deleteNode(root.right, key);
107  
108         // if key is same as root's key, then this is the node
109         // to be deleted
110         else
111         {
112  
113             // node with only one child or no child
114             if ((root.left == null) || (root.right == null))
115             {
116                 Node temp = null;
117                 if (temp == root.left)
118                     temp = root.right;
119                 else
120                     temp = root.left;
121  
122                 // No child case
123                 if (temp == null)
124                 {
125                     temp = root;
126                     root = null;
127                 }
128                 else   // One child case
129                     root = temp; // Copy the contents of
130                                  // the non-empty child
131             }
132             else
133             {
134  
135                 // node with two children: Get the inorder
136                 // successor (smallest in the right subtree)
137                 Node temp = minValueNode(root.right);
138  
139                 // Copy the inorder successor's data to this node
140                 root.key = temp.key;
141  
142                 // Delete the inorder successor
143                 root.right = deleteNode(root.right, temp.key);
144             }
145         }
146  
147         // If the tree had only one node then return
148         if (root == null)
149             return root;
150  
151         // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
152         root.height = max(height(root.left), height(root.right)) + 1;
153  
154         // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
155         //  this node became unbalanced)
156         int balance = getBalance(root);
157  
158         // If this node becomes unbalanced, then there are 4 cases
159         // Left Left Case
160         if (balance > 1 && getBalance(root.left) >= 0)
161             return rightRotate(root);
162  
163         // Left Right Case
164         if (balance > 1 && getBalance(root.left) < 0)
165         {
166             root.left = leftRotate(root.left);
167             return rightRotate(root);
168         }
169  
170         // Right Right Case
171         if (balance < -1 && getBalance(root.right) <= 0)
172             return leftRotate(root);
173  
174         // Right Left Case
175         if (balance < -1 && getBalance(root.right) > 0)
176         {
177             root.right = rightRotate(root.right);
178             return leftRotate(root);
179         }
180  
181         return root;
182     }

[۵]

جستجو[ویرایش]

جستجو در درخت ای‌وی‌ال همانند جستجو در در خت دودویی نامتوازن است. به دلیل توازن ارتفاع درخت هزینه جستجو در بد‌ترین حالت برابر است. هیچ شرط خاصی برای رعایت کردن وجود ندارد و در طول جستجو ساختار درخت تغییری نمی‌کند.(می توان جستجو در درخت ای‌وی‌ال را در تباین با جستجو در درخت گسترده دانست که در آن ساختار درخت در حین جستجو تغییر می‌کند.) اگر هر گره ارتفاع زیر درخت خود را نیز ذخیره کند، هر گره می‌تواند در زمان نیز بازیابی شود. گره قبل و بعد هر گره در درخت ای‌وی‌ال در یک زمان ثابت سرشکن قابل دسترسی است. در موارد محدودی حدود پیوند پیمایش می‌شود. در اکثر موارد یک پیوند و در حالت سرشکن دو پیوند پیمایش می‌شود.[نیازمند منبع]

متوازن‌سازی[ویرایش]

اگر در هنگام اجرای یک عملیات(درج یا حذف) روی یک درخت ای‌وی‌ال ضریب توازن یک گره 2 یا 2- شود،(از محدوده مجاز 1 تا 1- خارج شود) آن درخت نیازمند عمل متوازن‌سازی خواهد‌بود. فرض کنید گره ای که ضریب توازنش از محدوده مجاز خارج شده است X و فرزند بزرگتر آن (با ارتفاع بیشتر) Z باشند. توجه شود که می‌دانیم زیر درخت Z یک درخت ای‌وی‌ال‌ است. علت عدم توازن X در عمل درج، اضافه شدن یک نود به Z، و در عمل حذف، حذف شدن یک نود از بچه های برادر Z است.

اگر فرزندان Z را ZR(فرزند راست) و ZL(فرزند چپ) بنامیم چهار حالت پیش می‌آید:

  • راست راست: Z فرزند راست X باشد و ZL‌ سنگین تر از ZR نباشد.
  • چپ چپ: Z فرزند چپ X باشد و ZR سنگین تر از ZL نباشد.
  • راست چپ: Z فرزند راست X باشد و ZR سنگین تر از ZL نباشد.
  • چپ راست: Z فرزند چپ X باشد و ZL‌ سنگین تر از ZR نباشد.

در دو حالت اول (راست راست و چپ چپ) نیاز به تک-چرخش و در دو حالت دیگر نیاز به دو-چرخش است.

تک چرخش[ویرایش]

AVL-simple-left

در شکل مقابل یک نمونه از مشکل راست راست با یک چرخش چپ حل شده است.

همانطور که مشاهده می شود با تغییر سه یال و به روز رسانی دو ضریب توازن، این درخت دوباره متوازن شده است.

در چرخش چپ، همانطور که ملاحظه می شود، گره های سمت راست X و چپ Z تغییری نمی‌کنند. پدر X به جای X به Z‌ وصل می شود. X و Z جایشان را با هم عوض می‌کنند.(رابطه پدر فرزندی جابجا می‌شود.) و در نهایت فرزند چپ Z به راست X وصل می‌شود.

AVL Rotação Simples à Direita

یک نمونه کد از چرخش چپ:

node *rotate_Left(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    t23 = left_child(Z); // Inner child of Z
    right_child(X) = t23;
    if (t23 != null)
        parent(t23) = X;
    left_child(Z) = X;
    parent(X) = Z;
    // 1st case, BalanceFactor(Z) == 0, only happens with deletion, not insertion:
    if (BalanceFactor(Z) == 0) { // t23 has been of same height as t4
        BalanceFactor(X) = +1;   // t23 now higher
        BalanceFactor(Z) = 1;   // t4 now lower than X
    } else { // 2nd case happens with insertion or deletion:
        BalanceFactor(X) = 0;
        BalanceFactor(Z) = 0;
    }
    return Z; // return new root of rotated subtree
}













دو چرخش[ویرایش]

در شکل مقابل وضیت چپ راست نمایش داده شده است.

در این حالت ابتدا با جابحا کردن Y و Z به یکی از حالات چپ چپ یا راست راست میرسیم و سپس با یک چرخش درخت را متوازن می‌کنیم.

نمونه کد:

618.994x618.994پیکسل
ode *rotate_RightLeft(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    Y = left_child(Z); // Inner child of Z
    // Y is by 1 higher than sibling
    t3 = right_child(Y);
    left_child(Z) = t3;
    if (t3 != null)
        parent(t3) = Z;
    right_child(Y) = Z;
    parent(Z) = Y;
    t2 = left_child(Y);
    right_child(X) = t2;
    if (t2 != null)
        parent(t2) = X;
    left_child(Y) = X;
    parent(X) = Y;
    // 1st case, BalanceFactor(Y) > 0, happens with insertion or deletion:
    if (BalanceFactor(Y) > 0) { // t3 was higher
        BalanceFactor(X) = 1;  // t1 now higher
        BalanceFactor(Z) = 0;
    } else // 2nd case, BalanceFactor(Y) == 0, only happens with deletion, not insertion:
        if (BalanceFactor(Y) == 0) {
            BalanceFactor(X) = 0;
            BalanceFactor(Z) = 0;
        } else { // 3rd case happens with insertion or deletion:
            // t2 was higher
            BalanceFactor(X) = 0;
            BalanceFactor(Z) = +1;  // t4 now higher
        }
    BalanceFactor(Y) = 0;
    return Y; // return new root of rotated subtree
}
AVL Rotação Dupla à Direita
AVL Rotação Dupla à Esquerda



















مقایسه با ساختارهای دادهٔ دیگر[ویرایش]

درخت‌های ای‌وی‌ال و قرمز-سیاه، هر دو از نوع درخت‌های جستجوی دودویی خود متوازن‌کننده هستند، بنابراین از نظر قانون ریاضی تفاوتی ندارند. عملیات برای متوازن کردن آن‌ها متفاوتند اما هر دو در زمان ثابتی انجام می‌شوند. تفاوت بین آ نها در میزان ارتفاعشان است. برای یک درخت به سایز n:

  • ارتفاع درخت ای‌وی‌ال محدود می‌شود به:
  • ارتفاع درخت قرمز-سیاه محدود می‌شود به:

درخت ای‌وی‌ال دارای توازن بیشتری نسبت به درخت قرمز-سیاه‌است یا به عبارت دیگر بسیار متوازن تر از درخت قرمز-سیاه‌است، که این منجر به این می‌شود که حذف و درج کردن به صورت کند، اما بازیابی در زمان سریع تری انجام شود.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • ویکی‌پدیای انگلیسی:
  1. رابرت سدجویک, الگوریتم ها، ادیسون-ویسلی, ۱۹۸۳, شابک: ‎۰-۲۰۱-۰۶۶۷۲-۶، صفحه ۱۹۹، فصل ۱۵: درخت‌های متوازن.
  2. پی فاف، بن. «آنالیز BSTs در سیستم‌های نرم‌افزار (PDF)». دانشگاه استنفورد، ژوئن ۲۰۰۴. 
  3. 1938-، Knuth, Donald Ervin,. The art of computer programming. Reading, Mass.: Addison-Wesley Pub. Co، ©1973-©1981. شابک ‎۰۲۰۱۰۳۸۰۹۹. OCLC ۸۲۳۸۴۹. 
  4. یوسفی، جواد. «درخت AVL (PDF)». ۱۳۸۹. 
  5. «AVL Tree | Set 2 (Deletion) - GeeksforGeeks»(en-US)‎. به کوشش GeeksforGeeks. 2012-03-11. بازبینی‌شده در 2018-06-09. 
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN: 0-201-89685-0. Pages 458–475 of section 6.2.3: Balanced Trees.

پیوند به بیرون[ویرایش]

پیاده سازی‌ها[ویرایش]