ในการเขียนโปรแกรมคอมพิวเตอร์เชือกหรือสายคือโครงสร้างข้อมูลที่ประกอบด้วยสตริง ขนาดเล็กกว่า ซึ่งใช้ในการจัดเก็บและจัดการสตริงที่ยาวกว่าหรือข้อความทั้งหมดได้อย่างมีประสิทธิภาพ ตัวอย่างเช่น โปรแกรม แก้ไขข้อความอาจใช้เชือกเพื่อแสดงข้อความที่กำลังแก้ไข เพื่อให้สามารถดำเนินการต่างๆ เช่น การแทรก การลบ และการเข้าถึงแบบสุ่มได้อย่างมีประสิทธิภาพ^{[ 1 ]}

โครงสร้างแบบเชือก (Roep) เป็นโครงสร้าง ต้นไม้ไบนารีชนิดหนึ่งโดยที่แต่ละใบ (โหนดปลาย) จะเก็บสตริงที่มีขนาดและความยาวที่จัดการได้ (หรือเรียกว่าน้ำหนัก ) และแต่ละโหนดที่อยู่สูงขึ้นไปในต้นไม้จะเก็บผลรวมของความยาวของใบทั้งหมดในซับทรี ด้านซ้ายของมัน ดังนั้น โหนดที่มีลูกสองตัวจะแบ่งสตริงทั้งหมดออกเป็นสองส่วน: ซับทรีด้านซ้ายเก็บส่วนแรกของสตริง ซับทรีด้านขวาเก็บส่วนที่สองของสตริง และน้ำหนักของโหนดคือความยาวของส่วนแรก

สำหรับการดำเนินการแบบ rope นั้น สตริงที่เก็บไว้ในโหนดจะถือว่าเป็นอ็อบเจ็กต์คงที่ที่ไม่สามารถเปลี่ยนแปลง ได้ ในกรณีทั่วไปที่ไม่ทำลายข้อมูล ทำให้สามารถใช้ งานฟังก์ชัน copy-on-write ได้ บ้าง โหนดปลายสุดมักจะถูกนำไปใช้เป็นสตริงความยาวคงที่พื้นฐานที่มี ตัว นับการอ้างอิงแนบมาด้วยเพื่อใช้ในการยกเลิกการจัดสรรเมื่อไม่ต้องการใช้งานอีกต่อไป แม้ว่าอาจใช้วิธี การเก็บขยะ แบบอื่นได้เช่นกัน

ในคำจำกัดความต่อไปนี้Nคือความยาวของเชือก หรือก็คือน้ำหนักของโหนดราก ตัวอย่างเหล่านี้ถูกกำหนดขึ้นใน ภาษาการ เขียน โปรแกรม Java

คำจำกัดความ:สร้างสแต็กSและลิสต์Lไล่ลงไปตามแกนซ้ายสุดของต้นไม้จนกว่าจะถึงใบ l' โดยเพิ่มโหนดn แต่ละโหนด ลงในSเพิ่ม l' ลงในLโหนดแม่ของ l' ( p ) อยู่ที่ด้านบนสุดของสแต็ก ทำซ้ำขั้นตอนสำหรับซับทรีด้านขวาของ p

แพ็คเกจorg.wikipedia.example ;นำเข้าjava.util.ArrayDeque ; นำเข้าjava.util.Deque ; นำเข้าjava.util.Iterator ;import jakarta.annotation.NonNull ;คลาสRopeLike { private RopeLike left ; private RopeLike right ;public RopeLike ( RopeLike left , RopeLike right ) { this . left = left ; this . right = right ; }public RopeLike getLeft () { return left ; }public RopeLike getRight () { return right ; } }public final class InOrderRopeIterator implements Iterator < RopeLike > { private final Deque < RopeLike > stack ;public InOrderRopeIterator ( @NonNull RopeLike root ) { stack = new ArrayDeque <> (); RopeLike c = root ; while ( c != null ) { stack . push ( c ); c = c . getLeft (); } }@Override public boolean hasNext ( ) { return stack.size ( ) > 0 ; }@Override public RopeLike next () { RopeLike result = stack.pop ( ) ;ถ้าstack ไม่ว่างเปล่าให้ลบRopeLike parent ออกจากstack แล้วดึงRopeLike right ออกจากparent ถ้าright ไม่เป็นnull ให้เพิ่มropeLike right ลงในstack แล้วดึงRopeLike cleft ออกจากright จนกว่าcleft จะเป็นnull ให้เพิ่มropeLike cleft ลงในstack แล้วดึงcleft ออกจากcleft​​​​​​​​ส่งคืนผลลัพธ์} }

คำจำกัดความ:รวบรวมชุดใบไม้Lและสร้างต้นไม้ขึ้นใหม่จากโคนต้นขึ้นไป

import java.util.List ;static boolean isBalanced ( RopeLike r ) { int depth = r . depth (); if ( depth >= FIBONACCI_SEQUENCE . length - 2 ) { return false ; } return FIBONACCI_SEQUENCE [ depth + 2 ] <= r . weight (); }static RopeLike rebalance ( RopeLike r ) { if ( ! isBalanced ( r )) { List < RopeLike > leaves = Ropes . collectLeaves ( r ); return merge ( leaves , 0 , leaves . size ()); } return r ; }static RopeLike merge ( List < RopeLike > leaves ) { return merge ( leaves , 0 , leaves . size ()); }static RopeLike merge ( List < RopeLike > leaves , int start , int end ) { int range = end - start ; switch ( range ) { case 1 : return leaves . get ( start ); case 2 : return new RopeLikeTree ( leaves . get ( start ), leaves . get ( start + 1 )); default : int mid = start + ( range / 2 ); return new RopeLikeTree ( merge ( leaves , start , mid ), merge ( leaves , mid , end )); } }

คำจำกัดความInsert(i, S’) : แทรกสตริงS'เริ่มต้นที่ตำแหน่งiในสตริงsเพื่อสร้างสตริงใหม่C , ..., C , S' , C , ... , C

ความซับซ้อนเชิงเวลา: ⁠ ⁠${\displaystyle O(\log N)}$ .

การดำเนินการนี้สามารถทำได้โดยการดำเนินการ a Split()และ b สองครั้งConcat()ค่าใช้จ่ายคือผลรวมของการดำเนินการทั้งสามครั้ง

import javafx.util.Pair ;public Rope insert ( int idx , CharSequence sequence ) { if ( idx == 0 ) { return prepend ( sequence ); } else if ( idx == length ()) { return append ( sequence ); } else { Pair < ​​RopeLike , RopeLike > lhs = base . split ( idx ); return new Rope ( Ropes . concat ( lhs . getKey (). append ( sequence ), lhs . getValue ())); } }

คำจำกัดความ:Index(i)ส่งคืนอักขระที่ตำแหน่งi

ความซับซ้อนเชิงเวลา: ⁠ ⁠${\displaystyle O(\log N)}$

ในการดึงอักขระ ตัวที่ iเราจะเริ่มต้น การค้นหา แบบเรียกซ้ำจากโหนดราก:

@Override public int indexOf ( char ch , int startIndex ) { if ( startIndex > weight ) { return right.indexOf ( ch , startIndex - weight ) ; } else { return left.indexOf ( ch , startIndex ) ; } }​​

ตัวอย่างเช่น ในการหาอักขระที่i=10ตำแหน่ง 1 ในรูปที่ 2.1 ที่แสดงทางด้านขวา ให้เริ่มจากโหนดราก (A) พบว่า 22 มากกว่า 10 และมีโหนดลูกซ้าย ดังนั้นให้ไปที่โหนดลูกซ้าย (B) 9 น้อยกว่า 10 ดังนั้นให้ลบ 9 ออกจาก 10 (เหลือi=1) แล้วไปที่โหนดลูกขวา (D) จากนั้นเนื่องจาก 6 มากกว่า 1 และมีโหนดลูกซ้าย ดังนั้นให้ไปที่โหนดลูกซ้าย (G) 2 มากกว่า 1 และมีโหนดลูกซ้าย ดังนั้นให้ไปที่โหนดลูกซ้ายอีกครั้ง (J) สุดท้าย 2 มากกว่า 1 แต่ไม่มีโหนดลูกซ้าย ดังนั้นอักขระที่ตำแหน่ง 1 ของสตริงสั้น "na" (เช่น "n") คือคำตอบ (ดัชนีเริ่มต้นที่ 1)

คำจำกัดความConcat(S1, S2) : นำเชือกสองเส้นและ S2 มา ต่อ เป็นเชือกเส้นเดียว

ความซับซ้อนเชิงเวลา: ⁠ ⁠${\displaystyle O(1)}$ (หรือ⁠ ⁠${\displaystyle O(\log N)}$เวลาในการคำนวณน้ำหนักราก)

การต่อเชื่อมสามารถทำได้ง่ายๆ โดยการสร้างโหนดรากใหม่ที่มีซ้าย = S1และขวา = S2ซึ่งใช้เวลาคงที่ น้ำหนักของโหนดแม่จะถูกกำหนดให้เท่ากับความยาวของโหนดลูกซ้ายซึ่งจะใช้เวลาหากต้นไม้มีความสมดุล ${\displaystyle O(\log N)}$

เนื่องจากการทำงานโดยใช้เชือกส่วนใหญ่จำเป็นต้องใช้ต้นไม้ที่มีความสมดุล ต้นไม้จึงอาจต้องได้รับการปรับสมดุลอีกครั้งหลังจากการเชื่อมต่อเชือกเสร็จสิ้น

นิยามSplit (i, S) : แยกสตริงSออกเป็นสองสตริงใหม่S และS โดยที่S 1 C 1 ..., C และS = C , ..., C

ความซับซ้อนเชิงเวลา: ⁠ ⁠${\displaystyle O(\log N)}$

มีสองกรณีที่ต้องดำเนินการแก้ไข:

1. จุดแยกจะอยู่ที่ส่วนท้ายของสตริง (เช่น หลังอักขระตัวสุดท้ายของโหนดใบ)
2. จุดแยกอยู่ตรงกลางของเส้นเชือก

กรณีที่สองจะลดรูปไปเป็นกรณีแรกโดยการแยกสตริง ณ จุดแยกเพื่อสร้างโหนดใบใหม่สองโหนด จากนั้นสร้างโหนดใหม่ที่เป็นโหนดแม่ของสตริงส่วนประกอบทั้งสอง

ตัวอย่างเช่น ในการแบ่งเชือก 22 ตัวอักษรที่แสดงในรูปที่ 2.3 ออกเป็นเชือกสองเส้นที่มีความยาวเท่ากันคือ 11 ตัวอักษร ให้สอบถามตัวอักษรที่ 12 เพื่อค้นหาโหนดKที่ระดับล่างสุด ลบลิงก์ระหว่างKและGไปที่โหนดแม่ของGและลบน้ำหนักของKออกจากน้ำหนักของDเดินทางขึ้นไปตามโครงสร้างต้นไม้และลบลิงก์ด้านขวาใดๆ ที่เชื่อมไปยังซับทรีที่ครอบคลุมตัวอักษรที่เกินตำแหน่งที่ 11 โดยลบน้ำหนักของK ออกจากโหนดแม่ของซับทรีเหล่านั้น (เฉพาะโหนดDและAในกรณีนี้) สุดท้าย สร้างโหนดKและH ที่เป็นโหนดกำพร้าขึ้นใหม่ โดยการรวมเข้าด้วยกันและสร้างโหนดแม่ใหม่Pที่มีน้ำหนักเท่ากับความยาวของโหนดด้านซ้าย K

เนื่องจากการทำงานโดยใช้เชือกส่วนใหญ่จำเป็นต้องใช้ต้นไม้ที่มีความสมดุล ต้นไม้จึงอาจต้องได้รับการปรับสมดุลใหม่หลังจากผ่าแล้ว

import javafx.util.Pair ;public Pair < ​​RopeLike , RopeLike > split ( int index ) { if ( index < weight ) { Pair < ​​RopeLike , RopeLike > split = left . split ( index ); return Pair . of ( rebalance ( split . getKey ()), rebalance ( new RopeLikeTree ( split . getValue (), right ))); } else if ( index > weight ) { Pair < ​​RopeLike , RopeLike > split = right . split ( index - weight ); return Pair . of ( rebalance ( new RopeLikeTree ( left , split . getKey ())), rebalance ( split . getValue ())); } else { return Pair . of ( left , right ); } }

คำจำกัดความRemove(i, j) : ลบสตริงย่อยC , …, C , ออกจากsเพื่อสร้างสตริงใหม่C , …, C , C , …, C .

ความซับซ้อนเชิงเวลา: ⁠ ⁠${\displaystyle O(\log N)}$ .

การดำเนินการนี้สามารถทำได้โดยการดำเนินการสองขั้นSplit()ตอน ขั้นConcat()ตอนแรก แบ่งเชือกออกเป็นสามส่วน โดยแบ่งตาม อักขระตัวที่ iและ ตัวที่ i+jตามลำดับ ซึ่งจะแยกสตริงที่ต้องการลบออกไปยังโหนดแยกต่างหาก จากนั้นจึงนำโหนดอีกสองโหนดมาต่อกัน

import javafx.util.Pair ;@Override public RopeLike remove ( int start , int length ) { Pair < RopeLike , RopeLike > lhs = split ( start ) ; Pair < RopeLike , RopeLike > rhs = split ( start + length ); return rebalance ( new RopeLikeTree ( lhs.getKey ( ) , rhs.getValue ( ) )); }

คำจำกัดความ:Report(i, j)แสดงผลสตริงC , …, C ออก มา

ความซับซ้อนเชิงเวลา: ⁠ ⁠${\displaystyle O(j+\log N)}$

ในการรายงานสตริงC , …, C ให้หาโหนดuที่มีC และweight(u) >= j… จากนั้นท่องไปในTโดยเริ่มจากโหนดuแสดงผลC , …, C โดยการท่อง ไป ในT ตามลำดับโดยเริ่มจากโหนดu

ข้อดี:

• เชือกช่วยให้การแทรกและการลบข้อความเร็วกว่าอาร์เรย์สตริงแบบดั้งเดิมมาก ซึ่งการดำเนินการดังกล่าวมีความซับซ้อนของเวลาเป็น O(n)
• เชือกไม่ต้องการหน่วยความจำเพิ่มเติม O(n) เมื่อดำเนินการ (อาร์เรย์ต้องการหน่วยความจำเพิ่มเติมสำหรับการดำเนินการคัดลอก)
• เชือกไม่จำเป็นต้องใช้พื้นที่หน่วยความจำต่อเนื่องขนาดใหญ่
• หากใช้เฉพาะการดำเนินการแบบไม่ทำลายข้อมูลเท่านั้น เชือกจะเป็นโครงสร้างข้อมูลถาวรสำหรับตัวอย่างโปรแกรมแก้ไขข้อความ สิ่งนี้ทำให้รองรับการยกเลิกการกระทำได้ หลาย ระดับ อย่างง่ายดาย

ข้อเสีย:

• มีการใช้พื้นที่โดยรวมมากขึ้นเมื่อไม่ได้ใช้งาน โดยส่วนใหญ่ใช้เพื่อจัดเก็บโหนดหลัก มีความสมดุลระหว่างปริมาณหน่วยความจำทั้งหมดที่ใช้เป็นค่าใช้จ่ายส่วนเกินกับความยาวของข้อมูลที่ประมวลผลเป็นสตริง สตริงในตัวอย่างข้างต้นนั้นสั้นเกินจริงสำหรับสถาปัตยกรรมสมัยใหม่ ค่าใช้จ่ายส่วนเกินจะเป็น O(n) เสมอ แต่ค่าคงที่สามารถกำหนดให้มีขนาดเล็กได้ตามต้องการ
• เพิ่มเวลาในการจัดการพื้นที่จัดเก็บเพิ่มเติม
• ความซับซ้อนของซอร์สโค้ดที่เพิ่มขึ้น ส่งผลให้ความเสี่ยงต่อข้อผิดพลาดสูงขึ้น

ตารางนี้เปรียบเทียบ คุณลักษณะ ทางอัลกอริทึมของการใช้งานสตริงและเชือก ไม่ใช่ความเร็วที่แท้จริงสตริงแบบอาร์เรย์มีค่าใช้จ่ายน้อยกว่า ดังนั้น (ตัวอย่างเช่น) การดำเนินการเชื่อมต่อและการแยกจึงเร็วกว่าในชุดข้อมูลขนาดเล็ก อย่างไรก็ตาม เมื่อใช้สตริงแบบอาร์เรย์กับสตริงที่ยาวขึ้น ความซับซ้อนของเวลาและการใช้หน่วยความจำสำหรับการแทรกและการลบอักขระจะมากเกินไปจนยอมรับไม่ได้ ในทางตรงกันข้าม โครงสร้างข้อมูลเชือกมีประสิทธิภาพที่เสถียรโดยไม่ขึ้นอยู่กับขนาดของข้อมูล นอกจากนี้ ความซับซ้อนของพื้นที่สำหรับเชือกและอาร์เรย์ต่างก็เป็น O(n) โดยสรุปแล้ว เชือกจึงเหมาะสมกว่าเมื่อข้อมูลมีขนาดใหญ่และมีการแก้ไขบ่อย

• สภาพ แวดล้อมการเขียนโปรแกรม Cedarซึ่งใช้เชือก "เกือบตั้งแต่เริ่มแรก" ^{[ 1 ]}
• Model T enfiladeเป็นโครงสร้างข้อมูลที่คล้ายคลึงกันจากช่วงต้นทศวรรษ 1970
• บัฟเฟอร์ช่องว่าง (Gap buffer ) คือโครงสร้างข้อมูลที่ใช้กันทั่วไปในโปรแกรมแก้ไขข้อความ ซึ่งช่วยให้การแทรกและการลบข้อมูลที่อยู่ใกล้กันเป็นไปอย่างมีประสิทธิภาพ
• ตารางชิ้นส่วน (Piece table ) เป็นอีกหนึ่งโครงสร้างข้อมูลที่นิยมใช้ในโปรแกรมแก้ไขข้อความ

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับRope (โครงสร้างข้อมูล )

• การใช้งานเชือก "absl::Cord" ภายในไลบรารี Abseil
• การนำเชือกแบบ "C cords" มาใช้ภายในไลบรารี Boehm Garbage Collector
• ข้อกำหนด SGI C++ สำหรับ ropes (รองรับโดย STLPort และlibstdc++ )
• เชือกสำหรับC#
• เชือกสำหรับภาษาลิสปาร์กทั่วไป
• เชือกสำหรับชวา
• เชือกที่มีลักษณะคล้ายเส้นด้ายสำหรับภาษาจาวา
• เชือกสำหรับ JavaScript
• เชือกสำหรับเล่นลิมโบ้
• เชือกสำหรับนิม
• เชือกสำหรับOCaml
• ไพโรปส์สำหรับPython
• เชือกสำหรับการสนทนาเล็กๆ น้อยๆ
• สวิฟท์โรปสำหรับสวิฟท์
• "เชือก"สำหรับสนิม
• เชือกสำหรับปาลูกดอก
• Rope & SumTreeใน Zed Editor