یک ساختار درختی درهم عبارت است از ساختاری خود متعادل‌کننده برای جستجوی باینری (Binary) داده‌ها که برخوردار از قابلیت‌های جدیدی می‌باشد و دسترسی به اطلاعات جدیدا دسترسی یافته را سهولت می‌بخشد
| ساختار درختي درهم (Splay Tree) |
یک ساختار درختی درهم عبارت است از ساختاری خود متعادل‌کننده برای جستجوی باینری داده‌ها که برخوردار از قابلیت‌های جدیدی می‌باشد که دسترسی به اطلاعات جدیدا دسترسی یافته را سهولت می‌بخشد.
این ساختار کارهایی مبنایی نظیر Iinsertion، Look-up و حذف زمان صرف شده در 
را به اجرا در می‌آورد.
«ساختارهای درختی درهم» بهتر از «ساختارهای درختی»، جستجوی اطلاعات دیگر اعمال غیریکنواخت متوالی در زمان نامشخص بودن «الگوی توالی» به اجرا در می آورند. این ساختار را «دانیل اسلیتور» و «رابرت تارجان» ابداع كردند.
تمام کارهای معمول درون یک ساختار درختی جستجوی باینری با یک عمل مبنایی تلفیق می‌شوند که Splaying نام دارد یعنی این‌که یک مؤلفه‌ي معین، درخت را طوری آرایش مجدد می‌دهد که درون ریشه‌ي ساختار قرار بگیرد.
یک راه انجام این‌کار این است که نخست یک جستجو در ساختار درختی برای اطلاعات خواسته شده صورت می‌پذیرد و شکلی از دوران صورت مي‌گيرد تا آن مؤلفه به بالای ساختار آورده شود.
متناوبا یک الگوریتم از پایین به بالا می‌تواند با جستجو تلفیق شده و ساختار درختی را مجددا سازمان‌دهی کند.
مزايا
«بازده مناسب» این ساختار درختی بستگی دارد به ویژگی خود متعادل کنندگی و در واقع خود بهبوددهندگی آن. بدین‌صورت که نودهایی که بیش‌ترین میزان دسترسی را دارند به ریشه نزدیک‌تر می‌شوند تا با سرعت بیش‌تری بتوان به آن‌ها دست یافت.
این مزیتی است برای تمام نرم‌افزارهایی که با این ساختار ارتباط می‌بایند و به‌خصوص حافظه‌ي Cach کم‌تری مصرف می‌کند.
اما باید توجه داشت برای مواردی که دسترسی به‌صورت «یکپارچه» نمی‌باشد بازده سازه‌ي درختی درهم خیلی «کارامدتر» است.
ساختارهای درختی درهم هم‌چنین از مزیت «ساختار ساده‌تر» نسبت به ساختارهای جستجوی باینری خود متعادل‌کننده‌ي دیگر نظیر: Red-Black یا AVL برخوردارند و «کارامدتر» هستند.
این ساختارها بی‌نیاز از Book Keeping Data می‌باشند از این‌رو «حافظه‌ي کم‌تری» را اشغال می‌كنند. اما سازه‌های دیگر از ویژگی «جبران بدترین زمان ممکن» برخوردارند و در عمل برای «دسترسی یکنواخت» کارامدتر هستند.
به عکس دیگر انواع ساختارهای درختی خود متعادل‌کننده، این ساختارها با نودهای دربردارنده‌ي «کلیدهای هویت» خوب کار می‌کنند. حتی با کلیدهای هویت، بازده به‌صورت هرزرفته خواهد بود. همه‌ي فعالیت‌های ساختار درختی با نظم نودهای هویت درون ساختار کار می کنند که یک ویژگی مشابه با الگوریتم‌های ترتیب‌دهی پایدار می‌باشد.
می‌توان «نسخه‌ای ماندگار» از ساختار درست کرد که پس از ارتقا بتوان از آن به نسخه‌های قبلی و بعدی دست پیدا کرد.
معايب
از بدترین مسائل مربوط به الگوریتم ساختار درختی درهم می‌توان به دسترسی متوالی مؤلفه‌های ساختار به ترتیب مرتب شده اشاره نمود. این ویژگی سبب «عدم تعادل ساختاری» می‌شود
علت آن است كه سبب می‌شود در هر نوبت عمل 
به‌میزان n تعداد دسترسی صورت پذیرد.
دسترسی مجدد منجر به فعال شدن عملی می‌شود که به تعداد 
زمان می‌برد تا ساختار را مجددا به تعادل برساند.
«تأخیر فراوانی» در اثر این پروسه صورت می‌پذیرد. اما پژوهش‌های انجام شده نشان داده‌اند که «متعادل‌سازی تصادفی» ساختار درختی می‌تواند جلوی اثر «عدم تعادل» را بگیرد که حاصل آن بازدهی برابر با بازده الگوریتم‌های خود متعادل می‌باشد.
|
با عرض سلام و خسته نباشید (به مناسبت پایان امتحانات!!) به کاربران گرامی !
دوستان عزیز ،
شما می توانید در قسمت زنگ تفریح با ارائه نظرات خود و پیشنهاد موضوعات جدید و جالب برای قسمت زنگ تفریح ، در قسمت "نظر شما" ، ضمن مشارکت در فعالیت های رشد ما را در این بخش یاری کنید.
منتظر نظرات شما هستیم !
پیشاپیش از همکاری صمیمانه ی شما سپاس گذاریم !
موفق باشید ! |