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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک مثال برای درخت نامتوازن که یک مسیر از ریشه به برگ آن بطور متوسط دسترسی به ۳٫۲۷ گره را نیاز دارد
همان درخت با ارتفاع متوازن که متوسط زمان دسترسی آن از ریشه به برگ به دسترسی ۳٫۰۰ گره کاهش یافته

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

نمای کلی[ویرایش]

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

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

به بیان دیگر حداقل ارتفاع یک درخت با n گره برابر است با log2(n) با روند کردن رو به پایین داریم:  \lfloor \log_2 n\rfloor

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

اگر این آیتم‌های داده شده پیش از زمان شناخته شوند، بطور متوسط با اضافه کردن مقادیر در ترتیب تصادفی که یک درخت جستجوی دودویی را نتیجه می‌دهد، می‌توان ارتفاع درخت را همچنان کوچک نگه داشت. هرچند موقعیت‌های بسیاری (همانند الگوریتمهای برخط) که این تصادفی کردن غیرقابل دوام است. درخت‌های دودویی خود متوازن این مسئله را با اعمال تغییراتی برروی درخت (همانند چرخش درخت) در زمانهای کلیدی بمنظور نگه داشتن ارتفاع متناسب با log2(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 را بشمارد. این گسترش ها میتواند برای مثال در بهینه سازی درخواست های پایگاه داده یا الگوریتم های دیگر مانند پردازش لیست مورد استفاده قرار گیرد.

همچنین ببینید[ویرایش]

منابع[ویرایش]

.[۱]

  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.