طناب (ساختمان داده) کیست؟ توضیح بده.
در برنامه نویسی کامپیوتر طناب و یا بند ناف، یک ساختمان داده برای ذخیره‌سازی و ادارهٔ بهینه یک رشته بسیار طولانی است. به عنوان مثال، یک برنامه ویرایش متن ممکن است از یک طناب برای نمایش متن در حال ویرایش استفاده کند، به‌طوری‌که عملیاتی از قبیل درج، حذف، یا دسترسی تصادفی به‌طور کارامد انجام بشود.تعریف.طناب یک درخت دودویی است. گرهٔ برگی (و همچنین برخی از گره‌های داخلی تک فرزند) شامل یک رشته کوتاه است. هر گره دارای یک "وزن" برابر با طول رشته خود به علاوه تمام وزن‌ها در زیردرخت سمت چپ آن است. بدین ترتیب یک گره با دو فرزند تمام رشته را به دو قسمت تبدیل می‌کند. زیر درخت سمت چپ اولین بخش از رشته ذخیره می‌کند. زیر درخت سمت راست بخش دوم ذخیره را می‌کند و وزن آن مجموع وزن فرزند سمت چپ و طول رشته خودش است.درخت دودویی شامل سطوح مختلفی از گره‌ها است. سطح پایین شامل تمام گره‌های که حاوی یک رشته هستند و سطوح بالاتر دارای گره‌های کمتر و کمتری هستند. بالاترین سطح از یک گره ریشه تشکیل شده‌است. طناب با قرار دادن گره‌هایی با رشته‌های کوتاه در سطح پایین و سپس الصاق نیمی از گره‌ها به گره پدر به‌طور تصادفی در سطح بعدی، ساخته شده‌است. گره‌های بدون فرزند (به عنوان مثال، دو گره‌ای که رشته‌های " my_ "و" me_i " ذخیره کرده‌اند) به فرزند راست گره سمت چپ خود تبدیل می‌شوند. بدین ترتیب تشکیل زنجیره می‌دهند.عملکرد.راهنما.برای بازیابی کاراکتر "i" ام، یک جستجوی بازگشتی از گره ریشه آغاز می‌کنیم:// Note ": Assumes 1-based indexing"function index(RopeNode node, integer i) if node.weight &lt;i then return index(node.right, i - node.weight) else if exists(node.left) then return index(node.left, i) else return node.string[i] endif endifendبه عنوان مثال، برای پیدا کردن کاراکتر در مکان i = ۱۰ در طناب زیر، از گره ریشه شروع کن، پیدا است که ۲۲ بزرگتر از ۱۰ است و یک فرزند در سمت چپ وجود دارد، بنابراین به فرزند سمت چپ برو. ۹ کمتر از ۱۰ است، بنابراین از ۱۰، ۹ را کم کن (قرار بده i = ۱) و به فرزند سمت راست برو. سپس چون ۷ بزرگتر از ۱ است و یک فرزند سمت چپ وجود دارد، به فرزند سمت چپ برو. ۶ بزرگتر از ۱ است و یک فرزند سمت چپ وجود دارد، پس دوباره به فرزند سمت چپ برو. در نهایت ۲ بیشتر از ۱ است، اما دیگر فرزندی در سمت چپ موجود نیست، پس کاراکتر موجود در index 1 از رشته کوتاه "NA"، پاسخ مورد نظر است.تقسیم." تعریف: " codice_2: تقسیم رشته "S" به دو رشته جدید "S1" و "S2""S1" = "C1", …, "Ci'"S2 = ، …, Cm"دو حالت وجود دارد: حالت اول : کاراکتر "i" ام در پایان آرایه است. همانند تصویر زیر و در حالت دوم، کاراکتر وسط آرایه قرار دارد.به عنوان مثال، برای تقسیم طناب ترسیم شده به دو بخش : از کاراکتر i ام بخواهید که گره v را در سطح پایین قرار بدهد و اتصال بین v و فرزنراست v یا ’v را بردارد. به گره پدر یعنی u برود و وزن ’v را از از u کم کند و از انجا که گره پدر، فرزند راست u، یعنی ’u را دارد، گره ’u را با اتصال به گره ’v و افزایش وزن ’u بوسیله وزن ’v، اصلاح کند. فرزند چپ سابق ’u به فرزند راست ’v تبدیل می‌شود. (تصویر دوم) و با همین روش تا گره پدر u، یعنی W ادامه دهد. وزن ’u را از وزن w کم کند. و سپس فرزند راست w که حالا ’w است را با اتصال به’u بهبود ببخشد. فرزند سابق ’w به فرزند راست ’u تبدیل می‌شود. و وزن ’w را به وسیله وزن ’u افزایش بدهد به گره پدر w یعنی x برود. از انجا که w فرزند راست x هست، پس تغییری ایجاد نمی‌شود سپس به گره پدر x یعنی y برود و وزن y را به وسیله ’w کم کند.چسباندن.این عمل عکس عمل تقسیم است و به‌طور متوسط به مدت زمان "(O(log N" برای تولید یک طناب به همراه یک درخت متوازن احتیاج دارد. (اگر محدودیت متوازن بودن درخت خروجی برداشته شود، عمل الحاق در یک زمان ثابت به سادگی با ایجاد یک گره ریشه و فرزندان "چپ = S1" و "راست = S2" می‌تواند اجرا شود. تخمین پیچیدگی عملیات دیگر بااین حال نیاز به طناب یا درختان متوازن به عنوان ورودی دارد)توجه داشته باشید که این الحاق مخرب است، که در آن طناب‌های ورودی "S1" و"S2" بعد از انجام عملیات دیگر وجود ندارند. درزمان مقایسه با الحاق آرایه، باید به خاطر داشته باشید که عملیتات دوم معمولاً غیر مخرب است .درج."تعریف:" codice_4: درج کردن رشته "’S" در مکان "i" ام از رشته "s" ، برای ایجاد یک رشته جدید :"C1, …, Ci, S’, ، …, Cm".این عملیات با انجام یک عمل codice_5 و دو عمل codice_6 ، انجام می‌شود و زمان انجام این عملیات ، برابر با مجموع زمان انجام سه عمل مذکور می‌باشد .حذف.این عملیات با انجام دو عمل codice_5 و یک عمل codice_6 ، انجام می‌شود . در ابتدا طناب را سه قسمت کنید ،این تقسیم که به ترتیب از کاراکتر "i" ام و"i+j" ام انجام می‌شود ، باعث می‌شود که رشته‌ای که می خواهیم حذف کنیم در گره‌ای دیگر ذخیره شود. سپس دو گره دیگر را به هم بچسبانید .خروجی.برای خروجی رشته "Ci, …, " ، گره "u"، که شامل "Ci" و "وزنu)&gt;= j)" ، را پیدا کنید و سپس از گره "u" شروع به پیمایش "T" بکنید . با شروع یک پیمایش میان ترتیب از گره "u" ( گره "u" متعلق به "T" است )، رشته "Ci, … , " را بدست بیاورید .مقایسه با آرایه‌های یک پارچه.مزایا:معایب:در جدول زیر، سرعت خام انجام الگوریتم‌ها مقایسه نمی‌شود بلکه مقایسه در مورد خصوصیت‌های الگوریتم‌های پیاده‌سازی رشته و طناب است . رشته‌هایی که بر پایهٔ آرایه‌ها ساخته شده‌اند، هزینه کمتری دارند ( به عنوان مثال ) عملیات‌های تقسیم و چسباندن روی داده‌های کوچک‌تر، سریع تر انجام می‌شوند . اگرچه زمانی که رشته‌های مذکور، برای رشته‌های بزرگ تر به کار می‌روند، پیچیدگی زمانی و استفاده از حافظه برای انجام عملیات‌های چسباندن و حذف کاراکترها، به طرز غیرقابل قبولی زیاد می‌شوند . اما طناب‌ها، با صرف نظر از حجم داده‌ها، عملکرد پایدار تری دارند . علاوه بر این پیچیدگی حافظه‌ای رشته‌ها و آرایه‌ها هر دو (O(n است . به‌طور خلاصه طناب‌ها زمانی که داده‌ها بزرگ و اغلب اصلاح شده هستند، مناسب هستند .