طناب (ساختمان داده)

یک طناب ساده که بر روی رشته «Hello my name is Simon» ساخته شده‌است.
در برنامه نویسی کامپیوتر طناب و یا بند ناف ، یک ساختمان داده برای ذخیره‌سازی و اداره‌ی بهینه یک رشته بسیار طولانی است. به عنوان مثال، یک برنامه ویرایش متن ممکن است از یک طناب برای نمایش متن در حال ویرایش استفاده کند، به‌طوری‌که عملیاتی از قبیل درج، حذف، یا دسترسی تصادفی به‌طور کارامد انجام بشود.
تعریف
طناب یک درخت دودویی است. گره برگی (و همچنین برخی از گره‌های داخلی تک فرزند) شامل یک رشته کوتاه است. هر گره دارای یک "وزن" برابر با طول رشته خود به علاوه تمام وزن‌ها در زیردرخت سمت چپ آن است. بدین ترتیب یک گره با دو فرزند تمام رشته را به دو قسمت تبدیل می‌کند. زیر درخت سمت چپ اولین بخش از رشته ذخیره می‌کند. زیر درخت سمت راست بخش دوم ذخیره را می‌کند و وزن آن مجموع وزن فرزند سمت چپ و طول رشته خودش است.
درخت دودویی شامل سطوح مختلفی از گره‌ها است. سطح پایین شامل تمام گره‌های که حاوی یک رشته هستند و سطوح بالاتر دارای گره‌های کمتر و کمتری هستند. بالاترین سطح از یک گره ریشه تشکیل شده‌است. طناب با قرار دادن گره‌هایی با رشته‌های کوتاه در سطح پایین و سپس الصاق نیمی از گره‌ها به گره پدر به‌طور تصادفی در سطح بعدی، ساخته شده‌است. گره‌های بدون فرزند (به عنوان مثال، دو گره‌ای که رشته‌های " my_ "و" me_i " ذخیره کرده‌اند) به فرزند راست گره سمت چپ خود تبدیل می‌شوند. بدین ترتیب تشکیل زنجیره می‌دهند.
عملکرد
راهنما
تعریف : (index(i : بازگرداندن کاراکتر به مکان i
پیچیدگی زمان: (O(log N در جایی که N طول طناب است.
برای بازیابی کاراکتر i ام، یک جستجوی بازگشتی از گره ریشه آغاز می‌کنیم:
// Note : Assumes 1-based indexing
function index(RopeNode node, integer i)
if node.weight
= j) ، را پیدا کنید و سپس از گره u شروع به پیمایش T بکنید . با شروع یک پیمایش میان ترتیب از گره u ( گره u متعلق به T است )، رشته C i , … , C i + j − 1 را بدست بیاورید .
مقایسه با آرایه‌های یک پارچه
مزایا:
طناب‌ها عملیات درج و حذف از متن را خیلی سریع‌تر از آرایه‌های یک پارچه با پیچیدگی (O(n ، انجام می‌دهند .
طناب‌ها به حافظه اضافی به مقدار (O(n برای انجام عمل احتیاجی ندارند در صورتی که آرایه‌ها برای عملیات کپی کردن به حافظه اضافی (O(n احتیاج دارند .
طناب‌ها به حافظه‌های اضافی پیوسته بزرگ احتیاجی ندارند .
در صورتی که از نمونه غیر مخرب عملیات‌ها استفاده شود ، طناب یک ساختمان داده پایدار محسوب می‌شود . برای نمونه‌ی برنامه‌ی ویرایش متن ، پایدار بودن طناب ، از سطوح متعدد خنثی سازی حمایت می‌کند .
معایب:
استفاده بیش از حد از حافظه ، در زمانی که هنوز اجرا نشده . این استفاده از حافظه ، بیشتر برای ذخیره‌سازی گره‌های پدر است و بین مقدار کلی حافظه‌ای که استفاده می‌شود و مدت زمان پردازش بخشی از داده‌ها ، تعادل وجود دارد . توجه داشته باشید که رشته‌هایی که بالاتر مثال زدیم ، برای ساختارهای مدرن ، کاملا کوچک و غیرواقعی هستند .در کل هزینه زمانی ، (O(n است واما اختیارا این مقدار را کوچک در نظر می‌گیریم .
افزایش مدت زمان برای مدیریت حافظه اضافی.
افزایش پیچیدگی کدهای منبع . که باعث ایجاد اشکالات زیادی می‌شود .
در جدول زیر ، سرعت خام انجام الگوریتم‌ها مقایسه نمی‌شود بلکه مقایسه در مورد خصوصیت‌های الگوریتم‌های پیاده‌سازی رشته و طناب است . رشته‌هایی که بر پایه‌ی آرایه‌ها ساخته شده‌اند ، هزینه کمتری دارند ( به عنوان مثال ) عملیات‌های تقسیم و چسباندن روی داده‌های کوچک‌تر ، سریع‌تر انجام می‌شوند . اگرچه زمانی که رشته‌های مذکور ، برای رشته‌های بزرگ‌تر به کار می‌روند ، پیچیدگی زمانی و استفاده از حافظه برای انجام عملیات‌های چسباندن و حذف کاراکترها ، به طرز غیر قابل قبولی زیاد می‌شوند . اما طناب‌ها ، با صرف نظر از حجم داده‌ها ، عملکرد پایدار‌تری دارند . علاوه بر این پیچیدگی حافظه‌ای رشته‌ها و آرایه‌ها هر دو (O(n است . به‌طور خلاصه طناب‌ها زمانی که داده‌ها بزرگ و اغلب اصلاح شده هستند ، مناسب هستند .
+ کارایی
عملکرد
طناب
رشته
فهرست
تقسیم
چسباندن (مخرب)
چسباندن (غیر مخرب)
حرکت بر روی هر کارکتر
درج
افزودن
حذف
گزارش
ساختن