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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم Day-Stout-Warren یا به اختصار (DSW) یک روش موثر برای متوازن کردن درخت جستجوی دودویی است، که در آن ارتفاع درخت را تا (O(log n کاهش می‌دهد، در حالی که n تعداد کل رأس‌ها ست. بر خلاف یک درخت جستجوی دودویی خود-متوازن این کار را تدریجاً در هر کدام از مراحل انجام نمی‌دهد، بلکه در دوره‌های معین عملیات را انجام می‌دهد، به نحوی که هزینه کل می‌تواند به تمام مراحل انجام شده سرشکن شود. این الگوریتم توسط Quentin F. Stout و Bette Warren در مقاله‌ای با عنوان Tree Rebalancing in Optimal Time and Space [۱] در سال ۱۹۸۶ طراحی شد که براساس یک تحقیق انجام شده توسط Colin Day در سال ۱۹۷۶ بود.
زمان اجرا این الگوریتم خطی ست (یعنی از مرتبه (O(nاست). الگوریتم اصلی طراحی شده توسط Day، متراکم ترین درخت ممکن را تولید می‌کند: تمام سطرهای درخت کامل هستند به جز سطر آخر.ولی این اصلاح توسط Stout/Warren یک درخت دودویی کامل تولید می‌کند. به عبارت دیگر یک درخت که در آن پایین ترین سطح از سمت چپ به راست کاملاً پر شده است. این یک تبدیل خوب است در صورتی که معلوم باشد درج دیگری در درخت انجام نمی‌شود.
اخیر ا مقاله‌ای در سال ۲۰۰۲ که توسط Timothy J. Rolfe تالیف شده است که بعد از مدت زیادی توجهات را به الگوریتم DSW جلب کرده است. نام گذاری بر اساس عنوان یک بخش از "6.7.1: The DSW Algorithm" در کتاب Data Structures and Algorithms in C++ (انتشارات PWS در صفحات ۱۷۳-۱۷۵) نوشته شدهٔ Adam Drozdek، انجام شده است. Rolfe دو مزیت اصلی برای آن ذکر می‌کند: "در موقعیت‌هایی که یک درخت جستجوی دودویی کامل در ابتدای مراحل تولید میشود که این درخت با دسترسی به وارسی تکه‌های گوناگون برای بقیه مراحل پردازش دنبال می‌شود" و بعدی اینکه "از لحاظ آموزشی در مباحث ساختمان داده و ریاضیات گسسته،پیشرفت خوبی در زمینه ی درخت های خودمتوزان برای چرخش درخت های دودویی ارائه میدهد. "


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