درخت آآ کیست؟ توضیح بده.
یک درخت AA در علوم کامپیوتر، نوعی از درخت جستجوی دودویی خود متوازن است که مورد استفاده آن در ذخیره‌سازی و بازیابی اطلاعات مرتب شده، به صورت بهینه و مناسب است. دلیل نامگذاری درخت AA، کاشفان آن، یعنی Arne Andersson می‌باشد.درخت‌های AA یک نوع درخت سرخ-سیاه(red-black) هستند، که به نوبه خود تعمیمی بر درخت جستجوی دودویی محسوب می‌شوند.برخلاف درختان سرخ-سیاه(red-black)، در درخت AA، گره‌های قرمز فقط می‌توانند به عنوان فرزند سمت راست اضافه شوند. به عبارت دیگر هیچ گره قرمزی نمی‌تواند به عنوان فرزند سمت چپ انتخاب شود.این باعث می‌شود که در شبیه‌سازی یک درخت ۲-۳ به جای یک درخت ۴-۳-۲، در ساده‌سازی عملیات‌های نگهداری بسیار کمک کند.الگوریتم‌های نگهداری برای یک درخت سرخ-سیاه(red-black) به هفت شکل متفاوت زیر، برای متعادل نگه کردن درخت، در نظر گرفته می‌شوند:در صورتی که در یک درخت AA، فقط کافی است که به دو شکل زیر در نظر گرفته شود و علت آن هم این است که تنها لینک‌های سمت راست می‌توانند به رنگ قرمز باشند:دوران‌های متعادل.از آنجایی که درخت‌های سرخ-سیاه به یک بیت از فراداده‌های هر گره (رنگ) برای متعادل ساز ی نیاز دارند، درخت‌های 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 functionSkew: 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 functionSplit: درج کردن.عملیات درج کردن با جستجوی دودویی درخت (به صورت معمولی) و پروسهٔ درج کردن آغاز می‌شود.هنگامی که پشته صدا زده می‌شود (یک پیاده‌سازی بازگشتی از جستجو را متصور باشید)، به سادگی می‌توان صحت درخت را بررسی کرد و در صورت نیاز هر گونه دوران، دوران انجام داد.اگر یک یال افقی به سمت چپ ظاهر شود، عملیات مورب (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 &lt; value(T) then left(T) := insert(X, left(T)) else if X &gt; 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 توصیف شده است، ساده‌ترین است، و اینجا هم شرح داده شده‌است. هر چند پیاده‌سازی‌های عملی ممکن است رویکرد بهینه تری داشته باشند. بعد از هر حذف اولین گام برای حفظ صحت درخت، این است که سطح هر گره‌ای که بچه‌هایش دو سطح پایین ترش باشند یا بچه نداشته باشد کاهش داده شود. این رویکرد به این علت مورد علاقه است که در دید کلی سه گام مجزای قابل فهم دارد:البته اینبار به جای یک گره باید کل سطح را مورب (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 &gt; value(T) then right(T) := delete(X, right(T)) else if X &lt; 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 &lt; level(T) then level(T) := should_be if should_be &lt; level(right(T)) then level(right(T)) := should_be end if end if return T end functionیک مثال خوب از این الگوریتم در این آدرس Andersson paper موجود است.عمل‌کرد.عمل‌کرد یک درخت AA با عمل‌کرد یک درخت سرخ-سیاه معادل است. در حالی که درخت AA دوران‌های بیشتری نسبت به درخت سرخ-سیاه انجام می‌دهد، الگوریتم ساده‌تر سریعتر هم هست، و همه این‌ها منتج به یک عمل‌کرد مشابه می‌شود. یک درخت سرخ-سیاه عمل‌کرد پیوسته تری نسبت به درخت AA دارد، اما درخت AA به علت مسطح بودن، کمی جستجوی سریعتر دارد.