درخت آآ

یک درخت AA در علوم کامپیوتر، نوعی از درخت جستجوی دودویی خود متوازن است که مورد استفاده آن در ذخیره‌سازی و بازیابی اطلاعات مرتب شده، به صورت بهینه و مناسب است. دلیل نامگذاری درخت AA، کاشفان آن، یعنی Arne Andersson می‌باشد. درخت‌های AA یک نوع درخت سرخ-سیاه(red-black) هستند، که به نوبه خود تعمیمی بر درخت جستجوی دودویی محسوب می‌شوند. برخلاف درختان سرخ-سیاه(red-black)، در درخت AA، گره‌های قرمز فقط می‌توانند به عنوان فرزند سمت راست اضافه شوند. به عبارت دیگر هیچ گره قرمزی نمی‌تواند به عنوان فرزند سمت چپ انتخاب شود. این باعث می‌شود که در شبیه‌سازی یک درخت ۲-۳ به جای یک درخت ۴-۳-۲، در ساده‌سازی عملیات‌های نگهداری بسیار کمک کند. الگوریتم‌های نگهداری برای یک درخت سرخ-سیاه(red-black) به هفت شکل متفاوت زیر، برای متعادل نگه کردن درخت، در نظر گرفته می‌شوند:

در صورتی که در یک درخت AA، فقط کافی است که به دو شکل زیر در نظر گرفته شود و علت آن هم این است که تنها لینک‌های سمت راست می‌توانند به رنگ قرمز باشند:

دوران‌های متعادل

از آنجایی که درخت‌های سرخ-سیاه به یک بیت از فراداده‌های هر گره (رنگ) برای متعادل ساز ی نیاز دارند، درخت‌های AA به پیچیدگی محاسباتی log N بیت از فراداده‌های هر گره نیاز دارد، به صورت یک عدد طبیعی به نام «سطح». یک درخت AA دارای ویژگی‌های زیر است:

1. سطح هر برگ برابر یک است.
2. سطح هر فرزند سمت چپ دقیقاً یکی کمتر از والد خود است.
3. سطح هر فرزند سمت راست، برابر یا یکی کمتر از والد خود است.
4. سطح هر نوه سمت راست، اکیداً کمتر از جد خود است.
5. هر گره از سطح بیشتر از یک دو فرزند دارد.

لینکی (یال) که در آن سطح یک فرزند با سطح والد خود برابر باشد را لینک (یال) افقی می‌نامند و مشابه آن لینک قرمز در درخت سرخ-سیاه است. تک یال‌های افقی به سمت راست مجاز ولی یال‌های متوالی غیرمجاز هستند. این‌ها محدودیت‌های بیشتری (در درخت AA) هستند از محدودیت‌های مشابه، در درخت سرخ-سیاه، با این نتیجه که متعادل‌سازی مجدد یک درخت AA بسیار ساده‌تر از درخت سرخ-سیاه است. درج کردن و حذف کردن در درخت AA به صورت موقتی آن را نامتعادل می‌کند (که باعث می‌شود با ویژگی‌های آن در تضاد باشد). تنها دو عملیات مجزا نیاز است تا درخت را مجدداً متعادل سازیم: “skew” (مورب) و ”split” (شکاف). مورب (skew) یک دوران به سمت راست است که منجر به جایگزاری یک زیر درخت، شامل یک یال افقی به سمت چپ، با، یک زیر درخت، شامل یک یال افقی به سمت راست، می‌شود. شکاف (split) یک دوران به سمت چپ و افزاینده سطح است که یک زیر درخت، شامل دو یا بیشتر از دو یال افقی متوالی به سمت راست، را با یک زیر درخت، شامل دو یا کمتر از دو یال افقی متوالی به سمت راست، جایگزین می‌کند. پیاده‌سازی «متعادل نگه داشتن» درج کردن و حذف کردن، توسط عملگرهای مورب (skew) و شکاف (split) ساده‌سازی شده است، تا فقط در صورت نیاز اصلاح درخت صورت گیرد، به جای اینکه صدا زننده‌های آن انتخاب کنند که مورب صورت بگیرد یا شکاف.

 '''function''' skew '''is'''
     '''input:''' T, a node representing an AA tree that needs to be rebalanced.
     '''output:''' Another node representing the rebalanced AA tree.

     '''if''' nil(T) '''then'''
         '''return''' Nil
     '''else if''' nil(left(T)) '''then'''
         '''return''' T
     '''else if''' level(left(T)) == level(T) '''then'''
         ''Swap the pointers of horizontal left links. ''
         L = left(T)
         left(T) := right(L)
         right(L) := T
         '''return''' L
     '''else'''
         '''return''' T
     '''end if'''
 '''end function'''

Skew:

 '''function''' split '''is'''
     '''input:''' T, a node representing an AA tree that needs to be rebalanced.
     '''output:''' Another node representing the rebalanced AA tree.

     '''if''' nil(T) '''then'''
         '''return''' Nil
     '''else if''' nil(right(T)) '''or''' nil(right(right(T))) '''then'''
         '''return''' T
     '''else if''' level(T) == level(right(right(T))) '''then'''
         ''We have two horizontal right links.  Take the middle node, elevate it, and return it. ''
         R = right(T)
         right(T) := left(R)
         left(R) := T
         level(R) := level(R) + 1
         '''return''' R
     '''else'''
         '''return''' T
     '''end if'''
 '''end function'''

Split:

درج کردن

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

 '''function''' insert '''is'''
     '''input:''' X, the value to be inserted, and T, the root of the tree to insert it into.
     '''output:''' A balanced version T including X.

     ''Do the normal binary tree insertion procedure. Set the result of the''
     ''recursive call to the correct child in case a new node was created or the''
     ''root of the subtree changes. ''
     '''if''' nil(T) '''then'''
         ''Create a new leaf node with X. ''
         '''return''' node(X, 1, Nil, Nil)
     '''else if''' X < value(T) '''then'''
         left(T) := insert(X, left(T))
     '''else if''' X > value(T) '''then'''
         right(T) := insert(X, right(T))
     '''end if'''
     ''Note that the case of X == value(T) is unspecified. As given, an insert''
     ''will have no effect. The implementor may desire different behavior. ''

     ''Perform skew and then split. The conditionals that determine whether or
     ''not a rotation will occur or not are inside of the procedures, as given''
     ''above. ''
     T := skew(T)
     T := split(T)

     '''return T'''
 '''end function'''

حذف کردن

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

برای دوباره متعادل‌سازی یک درخت چند رویکرد وجود دارد. روشی که توسط Andersson در مقاله‌اش original paper توصیف شده است، ساده‌ترین است، و اینجا هم شرح داده شده‌است. هر چند پیاده‌سازی‌های عملی ممکن است رویکرد بهینه تری داشته باشند. بعد از هر حذف اولین گام برای حفظ صحت درخت، این است که سطح هر گره‌ای که بچه‌هایش دو سطح پایین ترش باشند یا بچه نداشته باشد کاهش داده شود. این رویکرد به این علت مورد علاقه است که در دید کلی سه گام مجزای قابل فهم دارد:

1. اگر مناسب است، سطح را کاهش بده
2. سطح را مورب (skew) کن
3. سطح را شکاف (split) ده

البته اینبار به جای یک گره باید کل سطح را مورب (skew) کنیم یا شکاف (split) دهیم که باعث پیچیدگی کدمان می‌شود.

 '''function''' delete '''is'''
     '''input:''' X, the value to delete, and T, the root of the tree from which it should be deleted.
     '''output:''' T, balanced, without the value X.

     '''if''' nil(T) '''then'''
         return T
     '''else if''' X > value(T) '''then'''
         right(T) := delete(X, right(T))
     '''else if''' X < value(T) '''then'''
         left(T) := delete(X, left(T))
     '''else'''
         ''If we're a leaf, easy, otherwise reduce to leaf case. ''
         '''if''' leaf(T) '''then'''
             return Nil
         '''else if''' nil(left(T)) '''then'''
             L := successor(T)
             right(T) := delete(value(L), right(T))
             value(T) := value(L)
         '''else'''
             L := predecessor(T)
             left(T) := delete(value(L), left(T))
             value(T) := value(L)
         '''end if'''
     '''end if'''

     ''Rebalance the tree. Decrease the level of all nodes in this level if
     necessary, and then skew and split all nodes in the new level. ''
     T := decrease_level(T)
     T := skew(T)
     right(T) := skew(right(T))
     '''if not''' nil(right(T))
         right(right(T)) := skew(right(right(T)))
     '''end if'''
     T := split(T)
     right(T) := split(right(T))
     return T
 '''end function'''

 '''function''' decrease_level '''is'''
     '''input:''' T, a tree for which we want to remove links that skip levels.
     '''output:''' T with its level decreased.

     should_be = min(level(left(T)), level(right(T))) + 1
     '''if''' should_be < level(T) '''then'''
         level(T) := should_be
         '''if''' should_be < level(right(T)) '''then'''
             level(right(T)) := should_be
         '''end if'''
     '''end if'''
     return T
 '''end function'''

یک مثال خوب از این الگوریتم در این آدرس Andersson paper موجود است.

عمل‌کرد

عمل‌کرد یک درخت AA با عمل‌کرد یک درخت سرخ-سیاه معادل است. در حالی که درخت AA دوران‌های بیشتری نسبت به درخت سرخ-سیاه انجام می‌دهد، الگوریتم ساده‌تر سریعتر هم هست، و همه این‌ها منتج به یک عمل‌کرد مشابه می‌شود. یک درخت سرخ-سیاه عمل‌کرد پیوسته تری نسبت به درخت AA دارد، اما درخت AA به علت مسطح بودن، کمی جستجوی سریعتر دارد.

مطالب مشابه

• درخت سرخ-سیاه
• درخت بی
• درخت ای‌وی‌ال
• درخت قربانی

پیوند به بیرون

• A. Andersson. Balanced search trees made simple
• A. Andersson. A note on searching in a binary search tree
• AA-Tree Applet by Kubo Kovac
• BSTlib - Open source AA tree library for C by trijezdci
• AA Visual 2007 1.5 - OpenSource Delphi program for educating AA tree structures
• Thorough tutorial Julienne Walker with lots of code, including a practical implementation
• Object Oriented implementation with tests
• A Disquisition on The Performance Behavior of Binary Search Tree Data Structures (pages 67-75) - Comparison of AA trees, red-black trees, treaps, skip lists, and radix trees
• An example C implementation
• An Objective-C implementation