موضوع مقاله: طناب (ساختمان داده) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # طناب (ساختمان داده) | مقدمه: در برنامه نویسی کامپیوتر طناب و یا بند ناف، یک ساختمان داده برای ذخیره‌سازی و ادارهٔ بهینه یک رشته بسیار طولانی است. | ## بخش 1: طناب (ساختمان داده) | به عنوان مثال، یک برنامه ویرایش متن ممکن است از یک طناب برای نمایش متن در حال ویرایش استفاده کند، به‌طوری‌که عملیاتی از قبیل درج، حذف، یا دسترسی تصادفی به‌طور کارامد انجام بشود. هر گره دارای یک "وزن" برابر با طول رشته خود به علاوه تمام وزن‌ها در زیردرخت سمت چپ آن است. زیر درخت سمت راست بخش دوم ذخیره را می‌کند و وزن آن مجموع وزن فرزند سمت چپ و طول رشته خودش است. سطح پایین شامل تمام گره‌های که حاوی یک رشته هستند و سطوح بالاتر دارای گره‌های کمتر و کمتری هستند. طناب با قرار دادن گره‌هایی با رشته‌های کوتاه در سطح پایین و سپس الصاق نیمی از گره‌ها به گره پدر به‌طور تصادفی در سطح بعدی، ساخته شده‌است. گره‌های بدون فرزند (به عنوان مثال، دو گره‌ای که رشته‌های " my_ "و" me_i " ذخیره کرده‌اند) به فرزند راست گره سمت چپ خود تبدیل می‌شوند. ۹ کمتر از ۱۰ است، بنابراین از ۱۰، ۹ را کم کن (قرار بده i = ۱) و به فرزند سمت راست برو. در نهایت ۲ بیشتر از ۱ است، اما دیگر فرزندی در سمت چپ موجود نیست، پس کاراکتر موجود در index 1 از رشته کوتاه "NA"، پاسخ مورد نظر است. به عنوان مثال، برای تقسیم طناب ترسیم شده به دو بخش : از کاراکتر i ام بخواهید که گره v را در سطح پایین قرار بدهد و اتصال بین v و فرزن راست v یا ’v را بردارد. | ## بخش 2: طناب (ساختمان داده) | به گره پدر یعنی u برود و وزن ’v را از از u کم کند و از انجا که گره پدر، فرزند راست u، یعنی ’u را دارد، گره ’u را با اتصال به گره ’v و افزایش وزن ’u بوسیله وزن ’v، اصلاح کند. از انجا که w فرزند راست x هست، پس تغییری ایجاد نمی‌شود سپس به گره پدر x یعنی y برود و وزن y را به وسیله ’w کم کند. (اگر محدودیت متوازن بودن درخت خروجی برداشته شود، عمل الحاق در یک زمان ثابت به سادگی با ایجاد یک گره ریشه و فرزندان چپ = S1 و راست = S2 می‌تواند اجرا شود. تخمین پیچیدگی عملیات دیگر بااین حال نیاز به طناب یا درختان متوازن به عنوان ورودی دارد) توجه داشته باشید که این الحاق مخرب است، که در آن طناب‌های ورودی S1 وS2 بعد از انجام عملیات دیگر وجود ندارند. درزمان مقایسه با الحاق آرایه، باید به خاطر داشته باشید که عملیتات دوم معمولاً غیر مخرب است . پیچیدگی زمانی: (O(log Nاین عملیات با انجام یک عمل تقسیم و دو عمل چسباندن ، انجام می‌شود و زمان انجام این عملیات ، برابر با مجموع زمان انجام سه عمل مذکور می‌باشد . پیچیدگی زمانی: (O(log Nاین عملیات با انجام دو عمل تقسیم و یک عمل چسباندن ، انجام می‌شود . در ابتدا طناب را سه قسمت کنید ،این تقسیم که به ترتیب از کاراکتر i ام وi+j ام انجام می‌شود ، باعث می‌شود که رشته‌ای که می خواهیم حذف کنیم در گره‌ای دیگر ذخیره شود. با شروع یک پیمایش میان ترتیب از گره u ( گره u متعلق به T است )، رشته Ci, … , '' را بدست بیاورید . | ## بخش 3: طناب (ساختمان داده) | مقایسه با آرایه‌های یک پارچه مزایا: طناب‌ها عملیات درج و حذف از متن را خیلی سریع تر از آرایه‌های یکپارچه با پیچیدگی (O(n، انجام می‌دهند . طناب‌ها به حافظه اضافی به مقدار (O(n برای انجام عمل احتیاجی ندارند در صورتی که آرایه‌ها برای عملیات کپی کردن به حافظه اضافی (O(n احتیاج دارند . در صورتی که از نمونه غیر مخرب عملیات‌ها استفاده شود، طناب یک ساختمان داده پایدار محسوب می‌شود . برای نمونهٔ برنامهٔ ویرایش متن، پایدار بودن طناب، از سطوح متعدد خنثی سازی حمایت می‌کند . این استفاده از حافظه، بیشتر برای ذخیره‌سازی گره‌های پدر است و بین مقدار کلی حافظه‌ای که استفاده می‌شود و مدت زمان پردازش بخشی از داده‌ها، تعادل وجود دارد . توجه داشته باشید که رشته‌هایی که بالاتر مثال زدیم، برای ساختارهای مدرن، کاملاً کوچک و غیرواقعی هستند .در کل هزینه زمانی، (O(n است و اما اختیاراً این مقدار را کوچک در نظر می‌گیریم . در جدول زیر، سرعت خام انجام الگوریتم‌ها مقایسه نمی‌شود بلکه مقایسه در مورد خصوصیت‌های الگوریتم‌های پیاده‌سازی رشته و طناب است . رشته‌هایی که بر پایهٔ آرایه‌ها ساخته شده‌اند، هزینه کمتری دارند ( به عنوان مثال ) عملیات‌های تقسیم و چسباندن روی داده‌های کوچک‌تر، سریع تر انجام می‌شوند . اگرچه زمانی که رشته‌های مذکور، برای رشته‌های بزرگ تر به کار می‌روند، پیچیدگی زمانی و استفاده از حافظه برای انجام عملیات‌های چسباندن و حذف کاراکترها، به طرز غیرقابل قبولی زیاد می‌شوند . | ## جمع‌بندی | به‌طور خلاصه طناب‌ها زمانی که داده‌ها بزرگ و اغلب اصلاح شده هستند، مناسب هستند .