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

در علوم رایانه یک درخت درخت جستجوی دودویی خود-متوازن, هر درخت جستجوی دودویی گره-محور است که به‌طور خودکار ارتفاعش را (حداکثر تعداد مراحل زیر ریشه) در درج و حذف عنصر دلخواه، کوچک نگه می‌دارد. این ساختارها اجراهای مؤثری برای لیست‌‌های مرتب تغییر ناپذیر به وجود می‌آورد و می‌تواند به عنوان نوع داده انتزاعی چون آرایه انجمنی, صف‌ اولویت دار و مجموعه‌ها، مورد استفاده قرار گیرد.

یک مثال برای درخت نامتوازن که یک مسیر از ریشه به برگ آن به‌طور متوسط دسترسی به ۳٫۲۷ گره را نیاز دارد

همان درخت با ارتفاع متوازن که متوسط زمان دسترسی آن از ریشه به برگ به دسترسی ۳٫۰۰ گره کاهش یافته

نمای کلی

چرخش‌ها در درخت خیلی معمولند که عملیات داخلی خود-متوازن‌کننده، درخت‌ها را متوازن یا تقریباً متوازن نگه دارند.

بیشتر عملیات روی یک درخت جستجوی دودویی (ددج), زمانی مستقیماً متناسب با ارتفاع درخت می‌برند. پس مطلوب است که ارتفاع را کوچک نگه داریم. یک درخت دودویی با ارتفاع h می‌تواند شامل حداکثر 2+2+···+2 = 2−۱ گره باشد. بنابراین برای درختی با n گره و ارتفاع h داریم: $n\leq 2^{h+1}-1$

و این دلالت دارد بر اینکه:

h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor

.

به بیان دیگر حداقل ارتفاع یک درخت با n گره برابر است با log₂(n) با روند کردن رو به پایین داریم: $\lfloor \log _{2}n\rfloor$

هرچند ساده‌ترین الگوریتم برای درج عنصر در ددج، ممکن است یک درخت با ارتفاع n را در حالتهای مشترک نتیجه دهد. برای مثال وقتی عناصر در ترتیب مرتب شدهٔ کلیدها درج می‌شوند، درخت به یک لیست پیوندی با n گره تبدیل می‌شود. اختلاف کارایی این دو موقعیت ممکن است خیلی زیاد باشد. برای مثال برای n=۱٬۰۰۰٬۰۰۰ حداقل ارتفاع برابر است با: $\lfloor \log _{2}(n)\rfloor =19$

.

اگر این آیتم‌های داده شده پیش از زمان شناخته شوند، به‌طور متوسط با اضافه کردن مقادیر در ترتیب تصادفی که یک درخت جستجوی دودویی را نتیجه می‌دهد، می‌توان ارتفاع درخت را همچنان کوچک نگه داشت. هرچند موقعیت‌های بسیاری (همانند الگوریتم‌های برخط) که این تصادفی کردن غیرقابل دوام است. درخت‌های دودویی خود متوازن این مسئله را با اعمال تغییراتی بر روی درخت (همانند چرخش درخت) در زمان‌های کلیدی به منظور نگه داشتن ارتفاع متناسب با log₂(n), حداقل کرده‌اند. اگرچه یک سربار درگیر باشد، ممکن است در مدت زمان اجرای طولانی با اطمینان حاصل کردن از سریع اجرا شدن عملیات بعدی، توجیه شده باشد. نگه داشتن درخت در حداقل مقدار آن $\lfloor \log _{2}(n)\rfloor$

همیشه دوام پذیر نیست. می‌شود ثابت کرد که هر الگوریتم درج که قبلاً همانند آن را انجام دادیم، یک سربار بیش از اندازه خواهد داشت. از این رو بیشتر الگوریتم‌های ددج خود-متوازن، ارتفاع را تا یک ضریبی از کران پایین، ثابت نگه می‌دارند. در کران بالای مجانبی (O بزرگ) یک ساختار ددج خود متوازن که شامل n عنصر است, اجازهٔ وارسی، درج و حذف یک عنصر را در بدترین زمان اجرای (O(log n و در پیمایش درخت روی همهٔ عناصر در زمان (O(n می‌دهد. برای بعضی از اجراها، این‌ها کران‌های زمان در-عمل هستند. در صورتی‌که برای بقیه، آن‌ها کران‌های مستهلک بیش از یک دنباله از عملیات هستند. این زمان‌ها، به‌طور مجانبی برای همهٔ سختمان داده‌هایی که کلیدها را فقط در مقایسه دستکاری می‌کنند، بهینه هستند.

پیاده‌سازی

ساختمان داده‌های محبوب که این نوع درخت را شامل می‌شوند، عبارتند از:

برنامه‌های کاربردی

درخت‌های جستجوی دودویی خود-متوازن به‌طور معمول می‌توانند در ساخت و نگهداری لیست‌های مرتب شده‌استفاده شوند. مانند صفوف اولویت و همچنین می‌توانند به عنوان آرایه انجمنی مورد استفاده قرار گیرند. جفت‌های دارای مقدار کلیدی، به راحتی تنها با یک ترتیب روی کلید، درج می‌شوند.

در این حالت، ددج‌های خود-متوازن، یک سری مزیت و ضرر در مقابل رقیب اصلی خود یعنی جدول درهم‌سازی دارند. یک مزیت ددج‌های خود-متوازن این است که، آن‌ها اجازهٔ شمارش سریع (درواقع بهینه) عناصر را در محل‌های کلیدی می‌دهند که جداول درهم‌سازی این قابلیت را ندارد. یک ضرر این است که الگوریتم‌های وارسی آن، وقتی چند آیتم با کلیدهای مثل هم وجود داشته باشند، پیچیده تر می‌شود. ددج خای خود-متوازن بدترین زمان اجرای وارسی بهتری نسبت به جداول درهم‌سازی دارند. (O(log n در مقایسه با (O(n. ولی متوسط زمان اجرای بدتری دارند. (O(log n نسبت به (O(1.

ددج‌های خود-متوازن می‌توانند در اجرای هر الگوریتمی که به یک لیت مرتب شدهٔ تغییر پذیر نیاز دارند، برای رسیدن به بدترین زمان اجرای مجانبی بهینه، مورد استفاده قرار گیرند.

به‌طور مشابه بسیاری الگوریتم‌ها در هندسهٔ محاسباتی روی ددج خود-متوازن برای حل کردن مشکلاتی همانند مسئلهٔ درج خطی و مسئلهٔ موقعیت نقطه در تغییرات بهره‌گیری می‌کنند.(در حالت اجرای متوسط, ددج خود-متوازن ممکن است نسبت به راه حل‌های دیگر کارایی کمتری داشته باشد. درخت جستجوی دودویی در حالت خاص به احتمال زیاد کند تر از مرتب‌سازی ادغامی, مرتب‌سازی سریع یا مرتب‌سازی هرمی است).

ددج‌های خود-متوازن, ساختمان داده‌های قابل انعطافی هستند. به همین خاطر ساده است که بتوانیم آن را برای ثبت اطلاعات یا اجرای عملیات به‌طور مؤثر, گسترش دهیم. برای مثال, هرکس می‌تواند تعداد گره‌ها در یک برد معین کلید با آن خواص در زمان (O(log n را بشمارد. این گسترش‌ها می‌تواند برای مثال در بهینه‌سازی درخواست‌های پایگاه داده یا الگوریتم‌های دیگر مانند پردازش لیست مورد استفاده قرار گیرد.

همچنین ببینید

الگوریتم دی-استوت-وارن

درخت تلفیقی

فهرست پرشی

جور کردن

منابع

.

↑ دانلد کنوت. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.

[knuth-1] دانلد کنوت. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.