الگوریتم دی–استوت–وارن
الگوریتم دی–استوت–وارن (به انگلیسی: 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 دو مزیت اصلی برای آن ذکر می‌کند: "در موقعیت‌هایی که یک درخت جستجوی دودویی کامل در ابتدای مراحل تولید میشود که این درخت با دسترسی به وارسی تکه‌های گوناگون برای بقیه مراحل پردازش دنبال میشود" و بعدی اینکه "از لحاظ آموزشی در مباحث ساختمان داده و ریاضیات گسسته،پیشرفت خوبی در زمینه ی درخت های خودمتوازن برای چرخش درخت های دودویی ارائه میدهد. "
منابع[ویرایش]
- Wikipedia contributors, «Day–Stout–Warren algorithm», Wikipedia, The Free Encyclopedia,https://en.wikipedia.org/wiki/Day–Stout–Warren_algorithm