موضوع مقاله: درخت جستجوی دودویی خودمتوازن | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت جستجوی دودویی خودمتوازن | مقدمه: این ساختارها اجراهای مؤثری برای لیست‌های مرتب تغییرناپذیر به وجود می‌آورد و می‌تواند به عنوان نوع داده انتزاعی چون آرایه انجمنی، صف اولویت دار و مجموعه‌ها، مورد استفاده قرار گیرد. | ## بخش 1: درخت جستجوی دودویی خودمتوازن | بیشتر عملیات روی یک درخت جستجوی دودویی (ددج), زمانی مستقیماً متناسب با ارتفاع درخت می‌برند. یک درخت دودویی با ارتفاع h می‌تواند شامل حداکثر 20+21+···+2h = 2h+1−۱ گره باشد؛ بنابراین برای درختی با n گره و ارتفاع h داریم: و این دلالت دارد بر اینکه: . به بیان دیگر حداقل ارتفاع یک درخت با n گره برابر است با log2(n) با روند کردن رو به پایین داریم: هرچند ساده‌ترین الگوریتم برای درج عنصر در ددج، ممکن است یک درخت با ارتفاع n را در حالتهای مشترک نتیجه دهد. برای مثال وقتی عناصر در ترتیب مرتب شدهٔ کلیدها درج می‌شوند، درخت به یک لیست پیوندی با n گره تبدیل می‌شود. اگر این آیتم‌های داده شده پیش از زمان شناخته شوند، به‌طور متوسط با اضافه کردن مقادیر در ترتیب تصادفی که یک درخت جستجوی دودویی را نتیجه می‌دهد، می‌توان ارتفاع درخت را همچنان کوچک نگه داشت. هرچند موقعیت‌های بسیاری (همانند الگوریتم‌های برخط) که این تصادفی کردن غیرقابل دوام است. درخت‌های دودویی خود متوازن این مسئله را با اعمال تغییراتی بر روی درخت (همانند چرخش درخت) در زمان‌های کلیدی به منظور نگه داشتن ارتفاع متناسب با log2(n), حداقل کرده‌اند. اگرچه یک سربار درگیر باشد، ممکن است در مدت زمان اجرای طولانی با اطمینان حاصل کردن از سریع اجرا شدن عملیات بعدی، توجیه شده باشد. | ## بخش 2: درخت جستجوی دودویی خودمتوازن | می‌شود ثابت کرد که هر الگوریتم درج که قبلاً همانند آن را انجام دادیم، یک سربار بیش از اندازه خواهد داشت. از این رو بیشتر الگوریتم‌های ددج خود-متوازن، ارتفاع را تا یک ضریبی از کران پایین، ثابت نگه می‌دارند. در کران بالای مجانبی (O بزرگ) یک ساختار ددج خود متوازن که شامل n عنصر است، اجازهٔ وارسی، درج و حذف یک عنصر را در بدترین زمان اجرای (O(log n و در پیمایش درخت روی همهٔ عناصر در زمان (O(n می‌دهد. این زمان‌ها، به‌طور مجانبی برای همهٔ سختمان داده‌هایی که کلیدها را فقط در مقایسه دستکاری می‌کنند، بهینه هستند. پیاده‌سازی ساختمان داده‌های محبوب که این نوع درخت را شامل می‌شوند، عبارتند از: درخت ۲-۳ درخت آ آ درخت ای وی ال درخت سرخ-سیاه درخت Scapegoat درخت اسپلی داده ساختار تیریپ برنامه‌های کاربردی درخت‌های جستجوی دودویی خود-متوازن به‌طور معمول می‌توانند در ساخت و نگهداری لیست‌های مرتب شده‌استفاده شوند. مانند صفوف اولویت و همچنین می‌توانند به عنوان آرایه انجمنی مورد استفاده قرار گیرند. در این حالت، ددج‌های خود-متوازن، یک سری مزیت و ضرر در مقابل رقیب اصلی خود یعنی جدول درهم‌سازی دارند. یک مزیت ددج‌های خود-متوازن این است که، آن‌ها اجازهٔ شمارش سریع (درواقع بهینه) عناصر را در محل‌های کلیدی می‌دهند که جداول درهم‌سازی این قابلیت را ندارد. | ## بخش 3: درخت جستجوی دودویی خودمتوازن | یک ضرر این است که الگوریتم‌های وارسی آن، وقتی چند آیتم با کلیدهای مثل هم وجود داشته باشند، پیچیده‌تر می‌شود. ددج‌های خود-متوازن می‌توانند در اجرای هر الگوریتمی که به یک لیت مرتب شدهٔ تغییرپذیر نیاز دارند، برای رسیدن به بدترین زمان اجرای مجانبی بهینه، مورد استفاده قرار گیرند. به‌طور مشابه بسیاری الگوریتم‌ها در هندسهٔ محاسباتی روی ددج خود-متوازن برای حل کردن مشکلاتی همانند مسئلهٔ درج خطی و مسئلهٔ موقعیت نقطه در تغییرات بهره‌گیری می‌کنند. (در حالت اجرای متوسط، ددج خود-متوازن ممکن است نسبت به راه حل‌های دیگر کارایی کمتری داشته باشد. درخت جستجوی دودویی در حالت خاص به احتمال زیاد کندتر از مرتب‌سازی ادغامی، مرتب‌سازی سریع یا مرتب‌سازی هرمی است). به همین خاطر ساده است که بتوانیم آن را برای ثبت اطلاعات یا اجرای عملیات به‌طور مؤثر، گسترش دهیم. برای مثال، هرکس می‌تواند تعداد گره‌ها در یک برد معین کلید با آن خواص در زمان (O(log n را بشمارد. | ## جمع‌بندی | این گسترش‌ها می‌تواند برای مثال در بهینه‌سازی درخواست‌های پایگاه داده یا الگوریتم‌های دیگر مانند پردازش لیست مورد استفاده قرار گیرد.