درخت جستجوی دودویی خود-متوازن

یک مثال برای درخت نامتوازن که یک مسیر از ریشه به برگ آن بطور متوسط دسترسی به ۳٫۲۷ گره را نیاز دارد
همان درخت با ارتفاع متوازن که متوسط زمان دسترسی آن از ریشه به برگ به دسترسی ۳٫۰۰ گره کاهش یافته
در علوم رایانه یک درخت درخت جستجوی دودویی خود-متوازن , هر درخت جستجوی دودویی گره-محور است که بطور خودکار ارتفاعش را (حداکثر تعداد مراحل زیر ریشه) در درج و حذف عنصر دلخواه، کوچک نگه می‌دارد.
این ساختارها اجراهای موثری برای لیست‌های مرتب تغییر ناپذیر بوجود می‌آورد و می‌تواند به عنوان نوع داده انتزاعی چون آرایه انجمنی, صف اولویت دار و مجموعه‌ها، مورد استفاده قرار گیرد.
نمای کلی
چرخش‌ها در درخت خیلی معمولند که عملیات داخلی خود-متوازن‌کننده، درخت‌ها را متوازن یا تقریبا متوازن نگه دارند.
بیشتر عملیات روی یک درخت جستجوی دودویی (ددج), زمانی مستقیما متناسب با ارتفاع درخت می‌برند. پس مطلوب است که ارتفاع را کوچک نگه داریم. یک درخت دودویی با ارتفاع h می‌تواند شامل حداکثر 2 0 +2 1 +···+2 h = 2 h+1 −۱ گره باشد. بنابراین برای درختی با n گره و ارتفاع h داریم:
و این دلالت دارد بر اینکه: .
به بیان دیگر حداقل ارتفاع یک درخت با n گره برابر است با log 2 (n) با روند کردن رو به پایین داریم:
هرچند ساده‌ترین الگوریتم برای درج عنصر در ددج، ممکن است یک درخت با ارتفاع n را در حالتهای مشترک نتیجه دهد. برای مثال وقتی عناصر در ترتیب مرتب شده کلیدها درج می‌شوند، درخت به یک لیست پیوندی با n گره تبدیل می‌شود. اختلاف کارایی این دو موقعیت ممکن است خیلی زیاد باشد. برای مثال برای n=۱،۰۰۰،۰۰۰ حداقل ارتفاع برابر است با: .
اگر این آیتم‌های داده شده پیش از زمان شناخته شوند، بطور متوسط با اضافه کردن مقادیر در ترتیب تصادفی که یک درخت جستجوی دودویی را نتیجه می‌دهد، می‌توان ارتفاع درخت را همچنان کوچک نگه داشت. هرچند موقعیت‌های بسیاری (همانند الگوریتمهای برخط) که این تصادفی کردن غیرقابل دوام است.
درخت‌های دودویی خود متوازن این مسئله را با اعمال تغییراتی بر روی درخت (همانند چرخش درخت) در زمان‌های کلیدی به منظور نگه داشتن ارتفاع متناسب با log 2 (n), حداقل کرده‌اند.
اگرچه یک سربار درگیر باشد، ممکن است در مدت زمان اجرای طولانی با اطمینان حاصل کردن از سریع اجرا شدن عملیات بعدی، توجیه شده باشد. نگه داشتن درخت در حداقل مقدار آن همیشه دوام پذیر نیست. می‌شود ثابت کرد که هر الگوریتم درج که قبلا همانند آن را انجام دادیم، یک سربار بیش از اندازه خواهد داشت. از این رو بیشتر الگوریتم‌های ددج خود-متوازن، ارتفاع را تا یک ضریبی از کران پایین، ثابت نگه می‌دارند.
در کران بالای مجانبی (O بزرگ) یک ساختار ددج خود متوازن که شامل n عنصر است,
اجازه وارسی، درج و حذف یک عنصر را در بدترین زمان اجرای (O(log n و در پیمایش درخت روی همه عناصر در زمان (O(n می‌دهد.
برای بعضی از اجراها، اینها کرانهای زمان در-عمل هستند. در صورتی‌که برای بقیه، آن‌ها کرانهای مستهلک بیش از یک دنباله از عملیات هستند. این زمانها، بطور مجانبی برای همه سختمان داده‌هایی که کلیدها را فقط در مقایسه دستکاری می‌کنند، بهینه هستند.
پیاده‌سازی
ساختمان داده‌های محبوب که این نوع درخت را شامل می‌شوند، عبارتند از:
درخت ۲-۳
درخت آ آ
درخت ای وی ال
درخت سرخ-سیاه
درخت Scapegoat
درخت اسپلی
داده ساختار تیریپ
برنامه‌های کاربردی
درخت‌های جستجوی دودویی خود-متوازن بطور معمول می‌توانند در ساخت و نگهداری لیست‌های مرتب شده استفاده شوند. مانند صفوف اولویت و همچنین می‌توانند به عنوان آرایه انجمنی مورد استفاده قرار گیرند. جفت‌های دارای مقدار کلیدی، براحتی تنها با یک ترتیب روی کلید، درج می‌شوند.
در این حالت، ددج‌های خود-متوازن، یک سری مزیت و ضرر در مقابل رقیب اصلی خود یعنی جدول درهم‌سازی دارند. یک مزیت ددج‌های خود-متوازن این است که، آن‌ها اجازه شمارش سریع (درواقع بهینه) عناصر را در محل‌های کلیدی می‌دهند که جداول درهم‌سازی این قابلیت را ندارد. یک ضرر این است که الگوریتم‌های وارسی آن، وقتی چند آیتم با کلیدهای مثل هم وجود داشته باشند، پیچیده‌تر می‌شود. ددج خای خود-متوازن بدترین زمان اجرای وارسی بهتری نسبت به جداول درهم‌سازی دارند. (O(log n در مقایسه با (O(n. ولی متوسط زمان اجرای بدتری دارند. (O(log n نسبت به (O(1.
ددج‌های خود-متوازن می‌توانند در اجرای هر الگوریتمی که به یک لیت مرتب شده تغییر پذیر نیاز دارند، برای رسیدن به بدترین زمان اجرای مجانبی بهینه، مورد استفاده قرار گیرند.
بطور مشابه بسیاری الگوریتم‌ها در هندسه‌ی محاسباتی روی ددج خود-متوازن برای حل کردن مشکلاتی همانند مسئله‌ی درج خطی و مسئله‌ی موقعیت نقطه در تغییرات بهره‌گیری می‌کنند.(در حالت اجرای متوسط, ددج خود-متوازن ممکن است نسبت به راه حل‌های دیگر کارایی کمتری داشته باشد. درخت جستجوی دودویی در حالت خاص به احتمال زیاد کند‌تر از مرتب‌سازی ادغامی, مرتب‌سازی سریع یا مرتب‌سازی هرمی است).
ددج‌های خود-متوازن, ساختمان داده‌های قابل انعطافی هستند. به همین خاطر ساده است که بتوانیم آن را برای ثبت اطلاعات یا اجرای عملیات بطور موثر, گسترش دهیم. برای مثال, هرکس می‌تواند تعداد گره‌ها در یک برد معین کلید با آن خواص در زمان (O(log n را بشمارد. این گسترش‌ها می‌تواند برای مثال در بهینه‌سازی درخواست‌های پایگاه داده یا الگوریتم‌های دیگر مانند پردازش لیست مورد استفاده قرار گیرد.
همچنین ببینید
الگوریتم دی-استوت-وارن
درخت تلفیقی
فهرست پرشی
جور کردن