درخت آآ

یک درخت AA در علوم کامپیوتر، نوعی از درخت جستجوی دودویی خود متوازن است که مورد استفاده آن در ذخیره‌سازی و بازیابی اطلاعات مرتب شده، به صورت بهینه و مناسب است. دلیل نامگذاری درخت AA، کاشفان آن، یعنی Arne Andersson می‌باشد.
درخت‌های AA یک نوع درخت سرخ-سیاه(red-black) هستند، که به نوبه خود تعمیمی بر درخت جستجوی دودویی محسوب می‌شوند.
برخلاف درختان سرخ-سیاه(red-black)، در درخت AA، گره‌های قرمز فقط می‌توانند به عنوان فرزند سمت راست اضافه شوند. به عبارت دیگر هیچ گره قرمزی نمی‌تواند به عنوان فرزند سمت چپ انتخاب شود.
این باعث می‌شود که در شبیه‌سازی یک درخت ۲-۳ به جای یک درخت ۴-۳-۲، در ساده‌سازی عملیات‌های نگهداری بسیار کمک کند.
الگوریتم‌های نگهداری برای یک درخت سرخ-سیاه(red-black) به هفت شکل متفاوت زیر، برای متعادل نگه کردن درخت، در نظر گرفته می‌شوند:
پرونده:Red Black Shape Cases.svg
در صورتی که در یک درخت AA، فقط کافی است که به دو شکل زیر در نظر گرفته شود و علت آن هم این است که تنها لینک‌های سمت راست می‌توانند به رنگ قرمز باشند:
پرونده:AA Tree Shape Cases.svg
دوران‌های متعادل
از آنجایی که درخت‌های سرخ-سیاه به یک بیت از فراداده‌های هر گره (رنگ) برای متعادل ساز ی نیاز دارند، درخت‌های AA به پیچیدگی محاسباتی log N بیت از فراداده‌های هر گره نیاز دارد، به صورت یک عدد طبیعی به نام «سطح».
یک درخت AA دارای ویژگی‌های زیر است:
سطح هر برگ برابر یک است.
سطح هر فرزند سمت چپ دقیقا یکی کمتر از والد خود است.
سطح هر فرزند سمت راست، برابر یا یکی کمتر از والد خود است.
سطح هر نوه سمت راست، اکیدا کمتر از جد خود است.
هر گره از سطح بیشتر از یک دو فرزند دارد.
لینکی (یال) که در آن سطح یک فرزند با سطح والد خود برابر باشد را لینک (یال) افقی می‌نامند و مشابه آن لینک قرمز در درخت سرخ-سیاه است. تک یال‌های افقی به سمت راست مجاز ولی یال‌های متوالی غیرمجاز هستند. این‌ها محدودیت‌های بیشتری (در درخت 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: پرونده:AA Tree Skew2.svg
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: پرونده:AA Tree Split2.svg
درج کردن
عملیات درج کردن با جستجوی دودویی درخت (به صورت معمولی) و پروسه درج کردن آغاز می‌شود.
هنگامی که پشته صدا زده می‌شود (یک پیاده‌سازی بازگشتی از جستجو را متصور باشید)، به سادگی می‌توان صحت درخت را بررسی کرد و در صورت نیاز هر گونه دوران، دوران انجام داد.
اگر یک یال افقی به سمت چپ ظاهر شود، عملیات مورب (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
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 در مقاله‌اش توصیف شده است، ساده‌ترین است، و اینجا هم شرح داده شده‌است. هر چند پیاده‌سازی‌های عملی ممکن است رویکرد بهینه‌تری داشته باشند. بعد از هر حذف اولین گام برای حفظ صحت درخت، این است که سطح هر گره‌ای که بچه‌هایش دو سطح پایین ترش باشند یا بچه نداشته باشد کاهش داده شود. این رویکرد به این علت مورد علاقه است که در دید کلی سه گام مجزای قابل فهم دارد:
اگر مناسب است، سطح را کاهش بده
سطح را مورب (skew) کن
سطح را شکاف (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 were 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
یک مثال خوب از این الگوریتم در این آدرس موجود است.
عمل‌کرد
عمل‌کرد یک درخت AA با عمل‌کرد یک درخت سرخ-سیاه معادل است. در حالی که درخت AA دوران‌های بیشتری نسبت به درخت سرخ-سیاه انجام می‌دهد، الگوریتم ساده‌تر سریعتر هم هست، و همه این‌ها منتج به یک عمل‌کرد مشابه می‌شود. یک درخت سرخ-سیاه عمل‌کرد پیوسته‌تری نسبت به درخت AA دارد، اما درخت AA به علت مسطح بودن، کمی جستجوی سریعتر دارد.
مطالب مشابه
درخت سرخ-سیاه
درخت بی
درخت ای‌وی‌ال
درخت قربانی