درخت آآ
یک درخت 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) ساده‌سازی شده است، تا فقط در صورت نیاز اصلاح درخت صورت گیرد، به جای اینکه صدا زننده‌های آن انتخاب کنند که مورب صورت بگیرد یا شکاف.
Skew:
Split:
عملیات درج کردن با جستجوی دودویی درخت (به صورت معمولی) و پروسهٔ درج کردن آغاز می‌شود. هنگامی که پشته صدا زده می‌شود (یک پیاده‌سازی بازگشتی از جستجو را متصور باشید)، به سادگی می‌توان صحت درخت را بررسی کرد و در صورت نیاز هر گونه دوران، دوران انجام داد. اگر یک یال افقی به سمت چپ ظاهر شود، عملیات مورب (skew) انجام می‌گیرد، و اگر دو یال افقی به سمت راست ظاهر شود، عملیات شکاف (split) انجام می‌پذیرد، و احتمالاً افزایش سطح گره ریشه جدید از زیر درخت کنونی. توجه کنید که در کد بالا، برای سطح ریشه T همین اتفاق افتاد. این باعث می‌شود که چک کردن صحت درخت برای اصلاح از برگ‌ها به بالا، اهمیت پیدا کند.
در اکثر درختان دودویی متعادل، حذف کردن یک گره داخلی، قابل تغییر به حذف یک برگ است، که بوسیله جابجایی گره داخلی با، یا نزدیک‌ترین جدش، یا نزدیک‌ترین جانشین اش (نوه اش)، انجام می‌گیرد که به اینکه چه چیزی در درخت است یا به اجراکننده آن وابسته است. بازیابی یک جد، به سادگی دنبال کردن یک یال به سمت چپ و سپس دنبال کردن تمام یال‌های به سمت راست است. به‌طور مشابه، یک جانشین (نوه) با رفتن یک گام به راست و رفتن به چپ، تا جایی که به اشاره گر تهی برسیم، قابل یافتن است. به دلیل خاصیت درخت AA (اینکه تمام گره‌های دارای سطح بیشتر از یک، دو فرزند دارند) گره جد و نوه در سطح یک باشد که حذف آن را بدیهی می‌سازد.
برای دوباره متعادل‌سازی یک درخت چند رویکرد وجود دارد. روشی که توسط Andersson در مقاله‌اش original paper توصیف شده است، ساده‌ترین است، و اینجا هم شرح داده شده‌است. هر چند پیاده‌سازی‌های عملی ممکن است رویکرد بهینه تری داشته باشند. بعد از هر حذف اولین گام برای حفظ صحت درخت، این است که سطح هر گره‌ای که بچه‌هایش دو سطح پایین ترش باشند یا بچه نداشته باشد کاهش داده شود. این رویکرد به این علت مورد علاقه است که در دید کلی سه گام مجزای قابل فهم دارد:
البته اینبار به جای یک گره باید کل سطح را مورب (skew) کنیم یا شکاف (split) دهیم که باعث پیچیدگی کدمان می‌شود.
یک مثال خوب از این الگوریتم در این آدرس Andersson paper موجود است.
عمل‌کرد یک درخت AA با عمل‌کرد یک درخت سرخ-سیاه معادل است. در حالی که درخت AA دوران‌های بیشتری نسبت به درخت سرخ-سیاه انجام می‌دهد، الگوریتم ساده‌تر سریعتر هم هست، و همه این‌ها منتج به یک عمل‌کرد مشابه می‌شود. یک درخت سرخ-سیاه عمل‌کرد پیوسته تری نسبت به درخت AA دارد، اما درخت AA به علت مسطح بودن، کمی جستجوی سریعتر دارد.