रोप (डेटा संरचना): Difference between revisions

Revision as of 21:44, 2 August 2023

Hello_my_name_is_Simon की डोरी पर बनी एक साधारण रोप।

कंप्यूटर प्रोग्रामिंग में, रोप, या कॉर्ड, छोटी स्ट्रिंग (कंप्यूटर विज्ञान) से बनी एक डेटा स्ट्रक्चर है जिसका उपयोग बहुत लंबी स्ट्रिंग को एफ्फीशियेन्टली स्टोर करने और मैनिपुलेट करने के लिए किया जाता है। उदाहरण के लिए, एक टेक्स्ट एडिटिंग प्रोग्राम एडिट किए जा रहे टेक्स्ट को दर्शाने के लिए एक रोप का उपयोग कर सकता है, ताकि इंसर्शन, डिलीशन और रैंडम एक्सेस जैसे ऑपरेशन एफ्फीशियेन्टली किए जा सकें। ^[1]

विवरण

रोप एक प्रकार का बाइनरी ट्री है जहां प्रत्येक लीफ (अंतिम नोड) एक स्ट्रिंग और लेंथ (जिसे वेट के रूप में भी जाना जाता है) रखती है, और ट्री के आगे प्रत्येक नोड अपने लेफ्ट सबट्री में सभी लीफ की लेंथ का सम रखता है। दो चिल्ड्रन वाला एक नोड इस प्रकार पूरी स्ट्रिंग को दो भागों में डिवाइड करता है: राइट उपट्री स्ट्रिंग के पहले भाग को स्टोर करता है, लेफ्ट उपट्री स्ट्रिंग के दूसरे भाग को स्टोर करता है, और एक नोड का वेट पहले भाग की लेंथ है।

रोप ऑपरेशन के लिए, नोड्स में स्टोर स्ट्रिंग्स को टिपिकल नॉनडिस्ट्रक्टिव केस में निरंतर इम्म्युटेबल ऑब्जेक्ट माना जाता है, जो कुछ कॉपी-ऑन-राइट बिहेवियर की अनुमति देता है। लीफ नोड्स को सामान्यतः स्ट्रिंग (कंप्यूटर विज्ञान) के रूप में कार्यान्वित किया जाता है। बेसिक फिक्स्ड-लेंथ स्ट्रिंग्स के साथ एक रिफरेन्स काउंट के साथ जब आवश्यकता नहीं होती है, तब डीएलोकेशन करने के लिए अटैच किया जाता है, हालांकि अन्य गार्बेज कलेक्शन (कंप्यूटर विज्ञान) विधियों का भी उपयोग किया जा सकता है।

ऑपरेशन

निम्नलिखित परिभाषाओं में, N रोप की लेंथ है।

कलेक्ट लीव्स

डेफिनिशन: एक स्टैक एस और एक सूची एल बनाएं। जब तक आप एक लीफ एल' तक नहीं पहुंच जाते, तब तक ट्री की लेफ्ट-मोस्ट स्पाइन को ट्रैवर्स करें, प्रत्येक नोड एन को एस में जोड़ें। एल में एल जोड़ें। एल का रूट' (पी) ) स्टैक के शीर्ष पर है। पी के राइट सबट्री के लिए प्रोसीजर दोहराएँ।

final class InOrderRopeIterator implements Iterator<RopeLike> {

  private final Deque<RopeLike> stack;

  InOrderRopeIterator(@NonNull RopeLike root) {
    stack = new ArrayDeque<>();
    var c = root;
    while (c != null) {
      stack.push(c);
      c = c.getLeft();
    }
  }

  @Override
  public boolean hasNext() {
    return stack.size() > 0;
  }

  @Override
  public RopeLike next() {
    val result = stack.pop();

    if (!stack.isEmpty()) {
      val parent = stack.pop();
      val right = parent.getRight();
      if (right != null) {
        stack.push(right);
        var cleft = right.getLeft();
        while (cleft != null) {
          stack.push(cleft);
          cleft = cleft.getLeft();
        }
      }
    }

    return result;
  }
}

रीबैलेंस

डेफिनिशन: लीफ के सेट L को इकट्ठा करें और नीचे से ऊपर तक ट्री को रीबिल्ट करें।

  static boolean isBalanced(RopeLike r) {
    val 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)) {
      val 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;
    if (range == 1) {
      return leaves.get(start);
    }
    if (range == 2) {
      return new RopeLikeTree(leaves.get(start), leaves.get(start + 1));
    }
    int mid = start + (range / 2);
    return new RopeLikeTree(merge(leaves, start, mid), merge(leaves, mid, end));
  }

इन्सर्ट

डेफिनिशन: Insert(i, S’): एक नई स्ट्रिंग बनाने के लिए, स्ट्रिंग s में पोजीशन i से स्टार्ट होने वाली स्ट्रिंग

C 1, ..., C i, S', C i + 1, ..., C m

है।

टाइम कम्प्लेक्सिटी:

O(\log N)

है।

यह ऑपरेशन a Split() और दो Concat() ऑपरेशन द्वारा किया जा सकता है। कॉस्ट तीनों का सम है।

  public Rope insert(int idx, CharSequence sequence) {
    if (idx == 0) {
      return prepend(sequence);
    }
    if (idx == length()) {
      return append(sequence);
    }
    val lhs = base.split(idx);
    return new Rope(Ropes.concat(lhs.fst.append(sequence), lhs.snd));
  }

इंडेक्स

डेफिनिशन: Index(i): अक्षर को करैक्टर i पर रीटर्न करें

टाइम कम्प्लेक्सिटी:

O(\log N)

i-वें वर्ण को पुनः प्राप्त करने के लिए, हम रूट नोड से एक रिकर्सिव सर्च स्टार्ट करते हैं:

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

उदाहरण के लिए, करैक्टर को खोजने के लिए i=10 राइट ओर दिखाए गए चित्र 2.1 में, रूट नोड (ए) से स्टार्ट करें, पता लगाएं कि 22, 10 से बड़ा है और एक राइट चाइल्ड है, इसलिए लेफ्ट चाइल्ड (बी) पर जाएं। 9, 10 से कम है, इसलिए 10 में से 9 घटाएं (छोड़कर)। i=1) और राइट चाइल्ड (डी) के पास जाएं। फिर क्योंकि 6, 1 से बड़ा है और एक राइट चाइल्ड है, लेफ्ट चाइल्ड (G) पर जाएँ। 2, 1 से बड़ा है और एक राइट चाइल्ड है, इसलिए फिर से लेफ्ट चाइल्ड (जे) पर जाएं। एन्ड में 2, 1 से बड़ा है लेकिन कोई लेफ्ट चाइल्ड नहीं है, इसलिए छोटी स्ट्रिंग na (यानी n) के इंडेक्स 1 पर वर्ण उत्तर (1-बेस्ड इंडेक्स) है।

कॉनकैट

डेफिनिशन: Concat(S1, S2): दो रोप्स को, S₁ और S₂, एक ही रोप में जोड़ें।

टाइम कम्प्लेक्सिटी:

O(1)

(या

O(\log N)

रुट वेट को कंप्यूट करने का टाइम)

एक नया रूट नोड बनाकर बस एक संयोजन left = S1 और right = S2 किया जा सकता है, जो कांस्टेंट टाइम है। रूट नोड का वेट लेफ्ट चाइल्ड S₁ की लेंथ पर सेट है, जो $O(\log N)$ टाइम लेगा, यदि ट्री बैलेंस्ड है।

चूंकि मोस्ट रोप ऑपरेशन के लिए संतुलित ट्री की आवश्यकता होती है, इसलिए संयोजन के बाद ट्री को री-बैलेंस करने की आवश्यकता हो सकती है।

स्प्लिट

डेफिनिशन: Split (i, S): स्ट्रिंग S को दो नए स्ट्रिंग S₁ और S₂ $S 1 = C 1, ..., C i$ और $S 2 = C i + 1, ..., C m$ में स्प्लिट करें।

टाइम कम्प्लेक्सिटी:

O(\log N)

ऐसे दो केस हैं जिनसे डील करना है:

स्प्लिट पॉइंट एक स्ट्रिंग के एन्ड में है (यानी लीफ नोड के अंतिम अक्षर के बाद)
स्प्लिट पॉइंट एक स्ट्रिंग के मध्य में है।

दूसरा केस दो नए लीफ नोड्स बनाने के लिए स्प्लिट पॉइंट पर स्ट्रिंग को स्प्लिट करके पहले को कम करता है, फिर एक नया नोड बनाता है जो दो कॉम्पोनेन्ट स्ट्रिंग्स का पैरेंट है।

उदाहरण के लिए, फिगर 2.3 में पिक्चर 22-करैक्टर की रोप को लेंथ 11 की दो समान घटक रोप्स में स्प्लिट करने के लिए, निचले स्तर पर नोड K का पता लगाने के लिए 12वें करैक्टर को क्वेरी करें। K और G के बीच के लिंक को हटा दें। G के पैरेंट के पास जाएं और K के वेट को D के वेट से घटा दें। ट्री के ऊपर जाएं और पोजीशन 11 से पहले वर्णों को कवर करने वाले सबट्री के किसी भी सही लिंक को हटा दें, K के वेट को उनके से घटा दें। रूट नोड्स (इस केस में केवल नोड डी और ए)। एन्ड में, नए ओर्फनेड नोड्स K और H को एक साथ जोड़कर और लेफ्ट नोड K की लेंथ के बैलेंस्ड वेट के साथ एक नया पैरेंट P बनाएं।

चूंकि अधिकांश रोप ऑपरेशन के लिए संतुलित ट्री की आवश्यकता होती है, इसलिए ट्री को स्प्लिट होने के बाद फिर से बैलेंस करने की आवश्यकता हो सकती है।

  public Pair<RopeLike, RopeLike> split(int index) {
    if (index < weight) {
      val split = left.split(index);
      return Pair.of(rebalance(split.fst), rebalance(new RopeLikeTree(split.snd, right)));
    } else if (index > weight) {
      val split = right.split(index - weight);
      return Pair.of(rebalance(new RopeLikeTree(left, split.fst)), rebalance(split.snd));
    } else {
      return Pair.of(left, right);
    }
  }

डिलीट

डेफिनिशन: Delete(i, j): सबस्ट्रिंग डिलीट

C i, \dots, C i + j - 1

, s से एक नई स्ट्रिंग

C 1, \dots, C i - 1, C i + j, \dots, C m

बनाने के लिए किया था।

टाइम कम्प्लेक्सिटी:

O(\log N)

.

यह ऑपरेशन दो Split() और एक Concat()ऑपरेशन द्वारा किया जा सकता है। सबसे पहले, रोप को तीन भागों में स्प्लिट करें, क्रमशः i-th और i+j-th करैक्टर से स्प्लिट करें, जो एक अलग नोड में हटाने के लिए स्ट्रिंग को निकालता है। फिर अन्य दो नोड्स को जोड़ें।

  @Override
  public RopeLike delete(int start, int length) {
    val lhs = split(start);
    val rhs = split(start + length);
    return rebalance(new RopeLikeTree(lhs.fst, rhs.snd));
  }

रिपोर्ट

डेफिनिशन: Report(i, j): स्ट्रिंग

C i, \dots, C i + j - 1

को आउटपुट करें।

टाइम कम्प्लेक्सिटी:

O(j+\log N)

स्ट्रिंग $C i, \dots, C i + j - 1$ की रिपोर्ट करने के लिए, वह नोड ढूंढें जिसमें C_i और weight(u) >= j सम्मिलित है, और फिर नोड u से स्टार्ट करके T को ट्रैवर्स करें। आउटपुट $C i, \dots, C i + j - 1$ नोड यू से स्टार्ट करके टी का इन-ऑर्डर ट्रैवर्सल करके।

मोनोलिथिक ऐरे के साथ कमपैरीजन

Performance^{[citation needed]}
Operation	Rope	String
Index^[1]	O(log n)	O(1)
Split^[1]	O(log n)	O(1)
Concatenate (destructive)	O(log n) without rebalancing / O(n) worst case^{[citation needed]}	O(n)
Concatenate (nondestructive)	O(n)^{[citation needed]}	O(n)
Iterate over each character^[1]	O(n)	O(n)
Insert^[2]	O(log n) without rebalancing / O(n) worst case	O(n)
Append^[2]	O(log n) without rebalancing / O(n) worst case	O(1) amortized, O(n) worst case
Delete	O(log n)	O(n)
Report	O(j + log n)	O(j)
Build	O(n)	O(n)

एडवांटेज:

रोप्स मोनोलिथिक स्ट्रिंग ऐरे की कमपैरीजन में बहुत तीव्रता से पाठ को सम्मिलित करने और हटाने में सक्षम बनाती हैं, जिन पर ऑपरेशन में टाइम कम्प्लेक्सिटी O (n) होती है।
रोप्स को ऑपरेट होने पर O(n) एक्स्ट्रा मेमोरी की आवश्यकता नहीं होती है (ऐरे को प्रतिलिपि ऑपरेशन के लिए इसकी आवश्यकता होती है)।
रोप्स को बड़े सन्निहित मेमोरी स्पेस की आवश्यकता नहीं होती है।
यदि ऑपरेशन के केवल नॉन डिस्ट्रक्टिव वरजन का उपयोग किया जाता है, तो रोप एक परसिस्टेंट डेटा स्ट्रक्चर है। टेक्स्ट एडिटिंग प्रोग्राम उदाहरण के लिए, इससे कई पूर्ववत लेवल के लिए इजी समर्थन प्राप्त होता है।

डिसएडवांटेज:

मुख्य रूप से रूट नोड्स को स्टोर करने के लिए ऑपरेट नहीं होने पर अधिक ओवरआल स्पेस का उपयोग है। कुल मेमोरी का कितना हिस्सा ओवरहेड है और डेटा के कितने लंबे पीस को स्ट्रिंग के रूप में संसाधित किया जा रहा है, इसके बीच एक ट्रेड-ऑफ है। ऊपर दिए गए उदाहरण के डाटा में स्ट्रिंग आधुनिक वास्तुकला के लिए अनरीयलिस्टिक रूप से छोटे हैं। ओवरहेड हमेशा O(n) होता है, लेकिन स्थिरांक को आरबिटरेरी ढंग से छोटा किया जा सकता है।
अतिरिक्त स्टोरेज के प्रबंधन के लिए टाइम में वृद्धि
सोर्स कोड की बढ़ी हुई कॉम्पलेक्सिटी; बग का अधिक रिस्क

यह टेबल स्ट्रिंग और रोप इम्प्लीमेंटेशन के एल्गोरिथम ट्रेट की कमपैरीजन करती है, न कि उनकी रॉ स्पीड की। ऐरे-बेस्ड स्ट्रिंग्स का ओवरहेड छोटा होता है, इसलिए (उदाहरण के लिए) छोटे डेटासेट पर कॉन्सटेनेशन और स्प्लिट ऑपरेशन तीव्र होते हैं। हालाँकि, जब लंबी स्ट्रिंग्स के लिए ऐरे-बेस्ड स्ट्रिंग्स का उपयोग किया जाता है, तो करैक्टर को सम्मिलित करने और हटाने के लिए टाइम कम्प्लेक्सिटी और मेमोरी का उपयोग अनएक्सेप्टबली बड़ा हो जाता है। इसके विपरीत, रोप डेटा स्ट्रक्चर में डेटा आकार रीगार्डलेस्स स्टेबल परफॉरमेंस होता है। इसके अतिरिक्त, रोप्स और ऐरे के लिए स्पेस कॉम्पलेक्सिटी O(n) दोनों हैं। संक्षेप में, जब डेटा बड़ा हो और प्रायः मॉडिफाइड हो तो रोप्स बेहतर होती हैं।

यह भी देखें

सीडर (प्रोग्रामिंग भाषा) प्रोग्रामिंग वातावरण, जो अपनी स्थापना के टाइम से ही रोप्स का उपयोग करता था^[1]
एनफिलेड (ज़ानाडु), 1970 के दशक की शुरुआत की एक समान डेटा स्ट्रक्चर
गैप बफ़र , एक डेटा स्ट्रक्चर जो आमतौर पर टेक्स्ट संपादकों में उपयोग की जाती है जो एक ही स्थान के पास क्लस्टर किए गए कुशल सम्मिलन और विलोपन ऑपरेशन की अनुमति देती है
टुकड़ा टेबल, एक अन्य डेटा स्ट्रक्चर जो आमतौर पर पाठ संपादकों में उपयोग की जाती है

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 Boehm, Hans-J; Atkinson, Russ; Plass, Michael (December 1995). "Ropes: an Alternative to Strings" (PDF). Software: Practice and Experience. New York, NY, USA: John Wiley & Sons, Inc. 25 (12): 1315–1330. doi:10.1002/spe.4380251203. Archived from the original on 2020-03-08.
↑ ^2.0 ^2.1 "Rope Implementation Overview". www.sgi.com. Archived from the original on 2017-12-19. Retrieved 2017-03-01.

बाहरी संबंध

"absl::Cord" implementation of ropes within The Abseil library
"C cords" implementation of ropes within the Boehm Garbage Collector library
SGI C++ specification for ropes (supported by STLPort and libstdc++)
Ropes for C#
ropes for Common Lisp
Ropes for Java
String-Like Ropes for Java
Ropes for JavaScript
Ropes for Limbo
ropes for Nim
Ropes for OCaml
pyropes for Python
Ropes for Smalltalk
SwiftRope for Swift
"Ropey" for Rust

[Boehm-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 Boehm, Hans-J; Atkinson, Russ; Plass, Michael (December 1995). "Ropes: an Alternative to Strings" (PDF). Software: Practice and Experience. New York, NY, USA: John Wiley & Sons, Inc. 25 (12): 1315–1330. doi:10.1002/spe.4380251203. Archived from the original on 2020-03-08.

[:0-2] 2.0 ^2.1 "Rope Implementation Overview". www.sgi.com. Archived from the original on 2017-12-19. Retrieved 2017-03-01.

[1]

[2]

@@ Line 1: / Line 1: @@
 {{Short description|Data structure for storing strings}}
-[[File:Vector Rope example.svg|right|x200px|thumb|Hello_my_name_is_Simon की डोरी पर बनी एक साधारण रस्सी।]][[कंप्यूटर प्रोग्रामिंग]] में, रस्सी, या कॉर्ड, छोटी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] से बनी एक [[डेटा संरचना]] है जिसका उपयोग बहुत लंबी स्ट्रिंग को कुशलतापूर्वक संग्रहीत करने और हेरफेर करने के लिए किया जाता है। उदाहरण के लिए, एक [[ पाठ संपादन ]] प्रोग्राम संपादित किए जा रहे टेक्स्ट को दर्शाने के लिए एक रस्सी का उपयोग कर सकता है, ताकि सम्मिलन, विलोपन और रैंडम एक्सेस जैसे ऑपरेशन कुशलतापूर्वक किए जा सकें।<ref name="Boehm">
+[[File:Vector Rope example.svg|right|x200px|thumb|Hello_my_name_is_Simon की डोरी पर बनी एक साधारण रोप।]][[कंप्यूटर प्रोग्रामिंग]] में, रोप, या कॉर्ड, छोटी [[स्ट्रिंग (कंप्यूटर विज्ञान)]] से बनी एक [[डेटा संरचना|डेटा स्ट्रक्चर]] है जिसका उपयोग बहुत लंबी स्ट्रिंग को एफ्फीशियेन्टली स्टोर करने और मैनिपुलेट करने के लिए किया जाता है। उदाहरण के लिए, एक [[ पाठ संपादन |टेक्स्ट एडिटिंग]] प्रोग्राम एडिट किए जा रहे टेक्स्ट को दर्शाने के लिए एक रोप का उपयोग कर सकता है, ताकि इंसर्शन, डिलीशन और रैंडम एक्सेस जैसे ऑपरेशन एफ्फीशियेन्टली किए जा सकें। <ref name="Boehm">
 {{cite journal
   | last = Boehm
@@ Line 22: / Line 22: @@
 ==विवरण==
-रस्सी एक प्रकार का बाइनरी पेड़ है जहां प्रत्येक पत्ती (अंतिम नोड) एक स्ट्रिंग और लंबाई (जिसे वजन के रूप में भी जाना जाता है) रखती है, और पेड़ के आगे प्रत्येक नोड अपने बाएं [[उपवृक्ष]] में सभी पत्तियों की लंबाई का योग रखता है . दो बच्चों वाला एक नोड इस प्रकार पूरी स्ट्रिंग को दो भागों में विभाजित करता है: बायां उपट्री स्ट्रिंग के पहले भाग को संग्रहीत करता है, दायां उपट्री स्ट्रिंग के दूसरे भाग को संग्रहीत करता है, और एक नोड का वजन पहले भाग की लंबाई है।
+रोप एक प्रकार का बाइनरी ट्री है जहां प्रत्येक लीफ (अंतिम नोड) एक स्ट्रिंग और लेंथ (जिसे वेट के रूप में भी जाना जाता है) रखती है, और ट्री के आगे प्रत्येक नोड अपने लेफ्ट [[उपवृक्ष|सबट्री]] में सभी लीफ की लेंथ का सम रखता है। दो चिल्ड्रन वाला एक नोड इस प्रकार पूरी स्ट्रिंग को दो भागों में डिवाइड करता है: राइट उपट्री स्ट्रिंग के पहले भाग को स्टोर करता है, लेफ्ट उपट्री स्ट्रिंग के दूसरे भाग को स्टोर करता है, और एक नोड का वेट पहले भाग की लेंथ है।
-रस्सी संचालन के लिए, नोड्स में संग्रहीत स्ट्रिंग्स को विशिष्ट गैर-विनाशकारी मामले में निरंतर [[अपरिवर्तनीय वस्तु]]एं माना जाता है, जो कुछ [[लिखने पर नकल]] व्यवहार की अनुमति देता है। लीफ नोड्स को आम तौर पर स्ट्रिंग (कंप्यूटर विज्ञान) के रूप में कार्यान्वित किया जाता है | मूल निश्चित-लंबाई स्ट्रिंग्स के साथ एक [[संदर्भ गिनती]] के साथ जब आवश्यकता नहीं होती है, तब आवंटन रद्द करने के लिए संलग्न किया जाता है, हालांकि अन्य [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] विधियों का भी उपयोग किया जा सकता है।
+रोप ऑपरेशन के लिए, नोड्स में स्टोर स्ट्रिंग्स को टिपिकल नॉनडिस्ट्रक्टिव केस में निरंतर इम्म्युटेबल ऑब्जेक्ट माना जाता है, जो कुछ [[लिखने पर नकल|कॉपी-ऑन-राइट]] बिहेवियर की अनुमति देता है। लीफ नोड्स को सामान्यतः स्ट्रिंग (कंप्यूटर विज्ञान) के रूप में कार्यान्वित किया जाता है। बेसिक फिक्स्ड-लेंथ स्ट्रिंग्स के साथ एक [[संदर्भ गिनती|रिफरेन्स काउंट]] के साथ जब आवश्यकता नहीं होती है, तब डीएलोकेशन करने के लिए अटैच किया जाता है, हालांकि अन्य [[कचरा संग्रहण (कंप्यूटर विज्ञान)|गार्बेज कलेक्शन (कंप्यूटर विज्ञान)]] विधियों का भी उपयोग किया जा सकता है।
-==संचालन==
+==ऑपरेशन==
-निम्नलिखित परिभाषाओं में, N रस्सी की लंबाई है।
+निम्नलिखित परिभाषाओं में, N रोप की लेंथ है।
-=== पत्तियाँ एकत्रित करें ===
+=== कलेक्ट लीव्स ===
-: परिभाषा: एक स्टैक एस और एक सूची एल बनाएं। जब तक आप एक पत्ती एल' तक नहीं पहुंच जाते, तब तक पेड़ की सबसे बाईं ओर की रीढ़ को पार करें, प्रत्येक नोड एन को एस में जोड़ें। एल में एल जोड़ें। एल का मूल' (पी) ) स्टैक के शीर्ष पर है। पी के दाएँ उपवृक्ष के लिए प्रक्रिया दोहराएँ।
+: डेफिनिशन: एक स्टैक एस और एक सूची एल बनाएं। जब तक आप एक लीफ एल' तक नहीं पहुंच जाते, तब तक ट्री की लेफ्ट-मोस्ट स्पाइन को ट्रैवर्स करें, प्रत्येक नोड एन को एस में जोड़ें। एल में एल जोड़ें। एल का रूट' (पी) ) स्टैक के शीर्ष पर है। पी के राइट सबट्री के लिए प्रोसीजर दोहराएँ।
 <syntaxhighlight lang="java">
@@ Line 75: / Line 75: @@
-=== पुनर्संतुलन ===
+=== रीबैलेंस ===
-: परिभाषा: पत्तियों के समूह L को इकट्ठा करें और नीचे से ऊपर तक पेड़ का पुनर्निर्माण करें।
+: डेफिनिशन: लीफ के सेट L को इकट्ठा करें और नीचे से ऊपर तक ट्री को रीबिल्ट करें।
 <syntaxhighlight lang="java">
@@ Line 114: / Line 114: @@
-=== सम्मिलित करें ===
+=== इन्सर्ट ===
-: परिभाषा: <code>Insert(i, S’)</code>: एक नई स्ट्रिंग बनाने के लिए, स्ट्रिंग एस में स्थिति i से शुरू होने वाली स्ट्रिंग एस' डालें {{math|''C''<sub>1</sub>, ..., ''C<sub>i</sub>'', ''S''', ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}}.
+: डेफिनिशन: <code>Insert(i, S’)</code>: एक नई स्ट्रिंग बनाने के लिए, स्ट्रिंग s में पोजीशन i से स्टार्ट होने वाली स्ट्रिंग {{math|''C''<sub>1</sub>, ..., ''C<sub>i</sub>'', ''S''', ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}}  है।
-: समय जटिलता: {{tmath|O(\log N)}}.
+: टाइम कम्प्लेक्सिटी: {{tmath|O(\log N)}} है।
-यह ऑपरेशन a द्वारा किया जा सकता है <code>Split()</code> और दो <code>Concat()</code> परिचालन. लागत तीनों का योग है.
+यह ऑपरेशन a <code>Split()</code> और दो <code>Concat()</code> ऑपरेशन द्वारा किया जा सकता है। कॉस्ट तीनों का सम है।
 <syntaxhighlight lang="java">
    public Rope insert(int idx, CharSequence sequence) {
@@ Line 134: / Line 134: @@
-=== सूचकांक ===
+=== इंडेक्स ===
-[[File:Vector Rope index.svg|right|x200px|अंगूठा|चित्र 2.1: रस्सी पर सूचकांक लुकअप का उदाहरण।]]: परिभाषा: <code>Index(i)</code>: अक्षर को स्थिति i पर लौटाएँ
+[[File:Vector Rope index.svg|right|x200px|चित्र 2.1: रोप पर इंडेक्स लुकअप का उदाहरण।]]डेफिनिशन: <code>Index(i)</code>: अक्षर को करैक्टर i पर रीटर्न करें
-: समय जटिलता: {{tmath|O(\log N)}}
+: टाइम कम्प्लेक्सिटी: {{tmath|O(\log N)}}
-i-वें वर्ण को पुनः प्राप्त करने के लिए, हम रूट नोड से एक [[ प्रत्यावर्तन ]] खोज शुरू करते हैं:
+i-वें वर्ण को पुनः प्राप्त करने के लिए, हम रूट नोड से एक रिकर्सिव सर्च स्टार्ट करते हैं:
 <syntaxhighlight lang="java">
@@ Line 150: / Line 150: @@
    }
 </syntaxhighlight>
-उदाहरण के लिए, चरित्र को खोजने के लिए {{code|1=i=10}} दाईं ओर दिखाए गए चित्र 2.1 में, रूट नोड (ए) से शुरू करें, पता लगाएं कि 22, 10 से बड़ा है और एक बायां बच्चा है, इसलिए बाएं बच्चे (बी) पर जाएं। 9, 10 से कम है, इसलिए 10 में से 9 घटाएं (छोड़कर)। {{code|1=i=1}}) और दाएं बच्चे के पास जाएं (डी)। फिर क्योंकि 6, 1 से बड़ा है और एक बायाँ बच्चा है, बाएँ बच्चे (G) पर जाएँ। 2, 1 से बड़ा है और एक बायां बच्चा है, इसलिए फिर से बाएं बच्चे पर जाएं (जे)। अंत में 2, 1 से बड़ा है लेकिन कोई बचा हुआ बच्चा नहीं है, इसलिए छोटी स्ट्रिंग na (यानी n) के सूचकांक 1 पर वर्ण उत्तर है। (1-आधारित सूचकांक)
+उदाहरण के लिए, करैक्टर को खोजने के लिए {{code|1=i=10}} राइट ओर दिखाए गए चित्र 2.1 में, रूट नोड (ए) से स्टार्ट करें, पता लगाएं कि 22, 10 से बड़ा है और एक राइट चाइल्ड है, इसलिए लेफ्ट चाइल्ड (बी) पर जाएं। 9, 10 से कम है, इसलिए 10 में से 9 घटाएं (छोड़कर)। {{code|1=i=1}}) और राइट चाइल्ड (डी) के पास जाएं। फिर क्योंकि 6, 1 से बड़ा है और एक राइट चाइल्ड है, लेफ्ट चाइल्ड (G) पर जाएँ। 2, 1 से बड़ा है और एक राइट चाइल्ड है, इसलिए फिर से लेफ्ट चाइल्ड (जे) पर जाएं। एन्ड में 2, 1 से बड़ा है लेकिन कोई लेफ्ट चाइल्ड नहीं है, इसलिए छोटी स्ट्रिंग na (यानी n) के इंडेक्स 1 पर वर्ण उत्तर (1-बेस्ड इंडेक्स) है।
 === कॉनकैट ===
-[[File:Vector Rope concat.svg|right|x200px|अंगूठा|चित्रा 2.2: दो बच्चों की रस्सियों को एक ही रस्सी में जोड़ना।]]: परिभाषा: <code>Concat(S1, S2)</code>: दो रस्सियों को जोड़ें, एस<sub>1</sub> और एस<sub>2</sub>, एक ही रस्सी में।
+[[File:Vector Rope concat.svg|right|x200px|चित्रा 2.2: दो चिल्ड्रन की रोप्स को एक ही रोप में जोड़ना।]]डेफिनिशन: <code>Concat(S1, S2)</code>: दो रोप्स को, S<sub>1</sub> और S<sub>2</sub>, एक ही रोप में जोड़ें।
-: समय जटिलता: {{tmath|O(1)}} (या {{tmath|O(\log N)}} मूल वजन की गणना करने का समय)
+: टाइम कम्प्लेक्सिटी: {{tmath|O(1)}} (या {{tmath|O(\log N)}} रुट वेट को कंप्यूट करने का टाइम)
-एक नया रूट नोड बनाकर बस एक संयोजन किया जा सकता है {{mono|1=left = S1}} और {{mono|1=right = S2}}, जो स्थिर समय है। मूल नोड का वजन बाएं बच्चे एस की लंबाई पर सेट है<sub>1</sub>, जो लगेगा {{tmath|O(\log N)}} समय, यदि पेड़ संतुलित है।
+एक नया रूट नोड बनाकर बस एक संयोजन {{mono|1=left = S1}} और {{mono|1=right = S2}} किया जा सकता है, जो कांस्टेंट टाइम है। रूट नोड का वेट लेफ्ट चाइल्ड S<sub>1</sub> की लेंथ पर सेट है, जो {{tmath|O(\log N)}} टाइम लेगा, यदि ट्री बैलेंस्ड है।
-चूंकि अधिकांश रस्सी संचालन के लिए संतुलित पेड़ों की आवश्यकता होती है, इसलिए संयोजन के बाद पेड़ को फिर से संतुलित करने की आवश्यकता हो सकती है।
+चूंकि मोस्ट रोप ऑपरेशन के लिए संतुलित ट्री की आवश्यकता होती है, इसलिए संयोजन के बाद ट्री को री-बैलेंस करने की आवश्यकता हो सकती है।
-=== विभाजन ===
+=== स्प्लिट ===
-[[File:Vector Rope split.svg|right|x600px|अंगूठे|चित्रा 2.3: रस्सी को आधा में विभाजित करना।]]: परिभाषा: <code>Split (i, S)</code>: स्ट्रिंग S को दो नए स्ट्रिंग S में विभाजित करें<sub>1</sub> और एस<sub>2</sub>, {{math|1=''S''<sub>1</sub> = ''C''<sub>1</sub>, ..., ''C<sub>i</sub>''}} और {{math|1=''S''<sub>2</sub> = ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}}.
+[[File:Vector Rope split.svg|right|x600px|चित्रा 2.3: रोप को आधा में स्प्लिट करना।]]डेफिनिशन: <code>Split (i, S)</code>: स्ट्रिंग S को दो नए स्ट्रिंग S<sub>1</sub> और S<sub>2</sub> {{math|1=''S''<sub>1</sub> = ''C''<sub>1</sub>, ..., ''C<sub>i</sub>''}} और {{math|1=''S''<sub>2</sub> = ''C''<sub>''i'' + 1</sub>, ..., ''C<sub>m</sub>''}} में स्प्लिट करें।
-: समय जटिलता: {{tmath|O(\log N)}}
+: टाइम कम्प्लेक्सिटी: {{tmath|O(\log N)}}
-ऐसे दो मामले हैं जिनसे निपटा जाना चाहिए:
+ऐसे दो केस हैं जिनसे डील करना है:
-# विभाजन बिंदु एक स्ट्रिंग के अंत में है (यानी लीफ नोड के अंतिम अक्षर के बाद)
+# स्प्लिट पॉइंट एक स्ट्रिंग के एन्ड में है (यानी लीफ नोड के अंतिम अक्षर के बाद)
-# विभाजन बिंदु एक स्ट्रिंग के मध्य में है।
+# स्प्लिट पॉइंट एक स्ट्रिंग के मध्य में है।
-दूसरा मामला दो नए लीफ नोड्स बनाने के लिए विभाजन बिंदु पर स्ट्रिंग को विभाजित करके पहले को कम करता है, फिर एक नया नोड बनाता है जो दो घटक स्ट्रिंग्स का जनक है।
+दूसरा केस दो नए लीफ नोड्स बनाने के लिए स्प्लिट पॉइंट पर स्ट्रिंग को स्प्लिट करके पहले को कम करता है, फिर एक नया नोड बनाता है जो दो कॉम्पोनेन्ट स्ट्रिंग्स का पैरेंट है।
-उदाहरण के लिए, चित्र 2.3 में चित्रित 22-वर्ण की रस्सी को लंबाई 11 की दो समान घटक रस्सियों में विभाजित करने के लिए, निचले स्तर पर नोड K का पता लगाने के लिए 12वें वर्ण को क्वेरी करें। K और G के बीच के लिंक को हटा दें। G के पैरेंट के पास जाएं और K के वजन को D के वजन से घटा दें। पेड़ के ऊपर जाएं और स्थिति 11 से पहले वर्णों को कवर करने वाले उपवृक्षों के किसी भी सही लिंक को हटा दें, K के वजन को उनके से घटा दें। मूल नोड्स (इस मामले में केवल नोड डी और ए)। अंत में, नए अनाथ नोड्स K और H को एक साथ जोड़कर और बाएं नोड K की लंबाई के बराबर वजन के साथ एक नया पैरेंट P बनाएं।
+उदाहरण के लिए, फिगर 2.3 में पिक्चर 22-करैक्टर की रोप को लेंथ 11 की दो समान घटक रोप्स में स्प्लिट करने के लिए, निचले स्तर पर नोड K का पता लगाने के लिए 12वें करैक्टर को क्वेरी करें। K और G के बीच के लिंक को हटा दें। G के पैरेंट के पास जाएं और K के वेट को D के वेट से घटा दें। ट्री के ऊपर जाएं और पोजीशन 11 से पहले वर्णों को कवर करने वाले सबट्री के किसी भी सही लिंक को हटा दें, K के वेट को उनके से घटा दें। रूट नोड्स (इस केस में केवल नोड डी और ए)। एन्ड में, नए ओर्फनेड नोड्स K और H को एक साथ जोड़कर और लेफ्ट नोड K की लेंथ के बैलेंस्ड वेट के साथ एक नया पैरेंट P बनाएं।
-चूंकि अधिकांश रस्सी संचालन के लिए संतुलित पेड़ों की आवश्यकता होती है, इसलिए पेड़ को विभाजित होने के बाद फिर से संतुलित करने की आवश्यकता हो सकती है।
+चूंकि अधिकांश रोप ऑपरेशन के लिए संतुलित ट्री की आवश्यकता होती है, इसलिए ट्री को स्प्लिट होने के बाद फिर से बैलेंस करने की आवश्यकता हो सकती है।
 <syntaxhighlight lang="java">
@@ Line 190: / Line 190: @@
-=== हटाएं ===
+=== डिलीट ===
-: परिभाषा: <code>Delete(i, j)</code>: सबस्ट्रिंग हटाएं {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}, s से एक नई स्ट्रिंग बनाने के लिए {{math|''C''<sub>1</sub>, …, ''C''<sub>''i'' − 1</sub>, ''C''<sub>''i'' + ''j''</sub>, …, ''C<sub>m</sub>''}}.
+: डेफिनिशन: <code>Delete(i, j)</code>: सबस्ट्रिंग डिलीट {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}, s से एक नई स्ट्रिंग {{math|''C''<sub>1</sub>, …, ''C''<sub>''i'' − 1</sub>, ''C''<sub>''i'' + ''j''</sub>, …, ''C<sub>m</sub>''}} बनाने के लिए किया था।
-: समय जटिलता: {{tmath|O(\log N)}}.
+: टाइम कम्प्लेक्सिटी: {{tmath|O(\log N)}}.
-यह ऑपरेशन दो द्वारा किया जा सकता है <code>Split()</code> और एक <code>Concat()</code> कार्यवाही। सबसे पहले, रस्सी को तीन भागों में विभाजित करें, क्रमशः i-th और i+j-th वर्ण से विभाजित करें, जो एक अलग नोड में हटाने के लिए स्ट्रिंग को निकालता है। फिर अन्य दो नोड्स को जोड़ें।
+यह ऑपरेशन दो <code>Split()</code> और एक <code>Concat()</code>ऑपरेशन द्वारा किया जा सकता है। सबसे पहले, रोप को तीन भागों में स्प्लिट करें, क्रमशः i-th और i+j-th करैक्टर से स्प्लिट करें, जो एक अलग नोड में हटाने के लिए स्ट्रिंग को निकालता है। फिर अन्य दो नोड्स को जोड़ें।
 <syntaxhighlight lang="java">
@@ Line 207: / Line 207: @@
 === रिपोर्ट ===
-: परिभाषा: <code>Report(i, j)</code>: स्ट्रिंग को आउटपुट करें {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}.
+: डेफिनिशन: <code>Report(i, j)</code>: स्ट्रिंग {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}} को आउटपुट करें।
-: समय जटिलता: {{tmath|O(j + \log N)}}
+: टाइम कम्प्लेक्सिटी: {{tmath|O(j + \log N)}}
-स्ट्रिंग की रिपोर्ट करने के लिए {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}}, वह नोड ढूंढें जिसमें C शामिल है<sub>i</sub>और {{code|1=weight(u) >= j}}, और फिर नोड यू से शुरू करके टी को पार करें। उत्पादन {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}} नोड यू से शुरू करके टी का [[इन-ऑर्डर ट्रैवर्सल]] करके।
+स्ट्रिंग {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}} की रिपोर्ट करने के लिए, वह नोड ढूंढें जिसमें C<sub>i</sub> और {{code|1=weight(u) >= j}} सम्मिलित है, और फिर नोड u से स्टार्ट करके T को ट्रैवर्स करें। आउटपुट {{math|''C<sub>i</sub>'', …, ''C''<sub>''i'' + ''j'' − 1</sub>}} नोड यू से स्टार्ट करके टी का [[इन-ऑर्डर ट्रैवर्सल]] करके।
-==अखंड सरणियों के साथ तुलना==
+==मोनोलिथिक ऐरे के साथ कमपैरीजन==
 {| class="wikitable floatright"
 |+ Performance{{citation needed|date=October 2010}}
@@ Line 241: / Line 241: @@
 | Build || {{okay|O(n)}} || {{okay|O(n)}}
 |}
-लाभ:
+एडवांटेज:
-* रस्सियाँ मोनोलिथिक स्ट्रिंग सरणियों की तुलना में बहुत तेजी से पाठ को सम्मिलित करने और हटाने में सक्षम बनाती हैं, जिन पर संचालन में समय जटिलता ओ (एन) होती है।
+* रोप्स मोनोलिथिक स्ट्रिंग ऐरे की कमपैरीजन में बहुत तीव्रता से पाठ को सम्मिलित करने और हटाने में सक्षम बनाती हैं, जिन पर ऑपरेशन में टाइम कम्प्लेक्सिटी O (n) होती है।
-* रस्सियों को संचालित होने पर O(n) अतिरिक्त मेमोरी की आवश्यकता नहीं होती है (सरणी को प्रतिलिपि संचालन के लिए इसकी आवश्यकता होती है)।
+* रोप्स को ऑपरेट होने पर O(n) एक्स्ट्रा मेमोरी की आवश्यकता नहीं होती है (ऐरे को प्रतिलिपि ऑपरेशन के लिए इसकी आवश्यकता होती है)।
-* रस्सियों को बड़े सन्निहित मेमोरी स्पेस की आवश्यकता नहीं होती है।
+* रोप्स को बड़े सन्निहित मेमोरी स्पेस की आवश्यकता नहीं होती है।
-* यदि संचालन के केवल गैर-विनाशकारी संस्करणों का उपयोग किया जाता है, तो रस्सी एक सतत डेटा संरचना है। पाठ संपादन प्रोग्राम उदाहरण के लिए, इससे कई [[पूर्ववत]] स्तरों के लिए आसान समर्थन प्राप्त होता है।
+* यदि ऑपरेशन के केवल नॉन डिस्ट्रक्टिव वरजन का उपयोग किया जाता है, तो रोप एक परसिस्टेंट डेटा स्ट्रक्चर है। टेक्स्ट एडिटिंग प्रोग्राम उदाहरण के लिए, इससे कई [[पूर्ववत]] लेवल के लिए इजी समर्थन प्राप्त होता है।
-नुकसान:
+डिसएडवांटेज:
-* मुख्य रूप से मूल नोड्स को संग्रहीत करने के लिए संचालित नहीं होने पर अधिक समग्र स्थान का उपयोग। कुल मेमोरी का कितना हिस्सा ओवरहेड है और डेटा के कितने लंबे टुकड़ों को स्ट्रिंग के रूप में संसाधित किया जा रहा है, इसके बीच एक व्यापार-बंद है। ऊपर दिए गए उदाहरण के आंकड़ों में तार आधुनिक वास्तुकला के लिए अवास्तविक रूप से छोटे हैं। ओवरहेड हमेशा O(n) होता है, लेकिन स्थिरांक को मनमाने ढंग से छोटा किया जा सकता है।
+* मुख्य रूप से रूट नोड्स को स्टोर करने के लिए ऑपरेट नहीं होने पर अधिक ओवरआल स्पेस का उपयोग है। कुल मेमोरी का कितना हिस्सा ओवरहेड है और डेटा के कितने लंबे पीस को स्ट्रिंग के रूप में संसाधित किया जा रहा है, इसके बीच एक ट्रेड-ऑफ है। ऊपर दिए गए उदाहरण के डाटा में स्ट्रिंग आधुनिक वास्तुकला के लिए अनरीयलिस्टिक रूप से छोटे हैं। ओवरहेड हमेशा O(n) होता है, लेकिन स्थिरांक को आरबिटरेरी ढंग से छोटा किया जा सकता है।
-* अतिरिक्त भंडारण के प्रबंधन के लिए समय में वृद्धि
+* अतिरिक्त स्टोरेज के प्रबंधन के लिए टाइम में वृद्धि
-* स्रोत कोड की बढ़ी हुई जटिलता; बग का अधिक खतरा
+* सोर्स कोड की बढ़ी हुई कॉम्पलेक्सिटी; बग का अधिक रिस्क
-यह तालिका स्ट्रिंग और रस्सी कार्यान्वयन के एल्गोरिथम लक्षणों की तुलना करती है, न कि उनकी कच्ची गति की। ऐरे-आधारित स्ट्रिंग्स का ओवरहेड छोटा होता है, इसलिए (उदाहरण के लिए) छोटे डेटासेट पर कॉन्सटेनेशन और स्प्लिट ऑपरेशन तेज़ होते हैं। हालाँकि, जब लंबी स्ट्रिंग्स के लिए सरणी-आधारित स्ट्रिंग्स का उपयोग किया जाता है, तो वर्णों को सम्मिलित करने और हटाने के लिए समय जटिलता और मेमोरी का उपयोग अस्वीकार्य रूप से बड़ा हो जाता है। इसके विपरीत, रस्सी डेटा संरचना में डेटा आकार की परवाह किए बिना स्थिर प्रदर्शन होता है। इसके अलावा, रस्सियों और सरणियों के लिए स्थान जटिलता O(n) दोनों हैं। संक्षेप में, जब डेटा बड़ा हो और अक्सर संशोधित हो तो रस्सियाँ बेहतर होती हैं।
+यह टेबल स्ट्रिंग और रोप इम्प्लीमेंटेशन के एल्गोरिथम ट्रेट की कमपैरीजन करती है, न कि उनकी रॉ स्पीड की। ऐरे-बेस्ड स्ट्रिंग्स का ओवरहेड छोटा होता है, इसलिए (उदाहरण के लिए) छोटे डेटासेट पर कॉन्सटेनेशन और स्प्लिट ऑपरेशन तीव्र होते हैं। हालाँकि, जब लंबी स्ट्रिंग्स के लिए ऐरे-बेस्ड स्ट्रिंग्स का उपयोग किया जाता है, तो करैक्टर को सम्मिलित करने और हटाने के लिए टाइम कम्प्लेक्सिटी और मेमोरी का उपयोग अनएक्सेप्टबली बड़ा हो जाता है। इसके विपरीत, रोप डेटा स्ट्रक्चर में डेटा आकार रीगार्डलेस्स स्टेबल परफॉरमेंस होता है। इसके अतिरिक्त, रोप्स और ऐरे के लिए स्पेस कॉम्पलेक्सिटी O(n) दोनों हैं। संक्षेप में, जब डेटा बड़ा हो और प्रायः मॉडिफाइड हो तो रोप्स बेहतर होती हैं।
 ==यह भी देखें==
-* सीडर (प्रोग्रामिंग भाषा) प्रोग्रामिंग वातावरण, जो अपनी स्थापना के समय से ही रस्सियों का उपयोग करता था<ref name="Boehm"/>* एनफिलेड (ज़ानाडु), 1970 के दशक की शुरुआत की एक समान डेटा संरचना
+* सीडर (प्रोग्रामिंग भाषा) प्रोग्रामिंग वातावरण, जो अपनी स्थापना के टाइम से ही रोप्स का उपयोग करता था<ref name="Boehm"/>
-* [[ गैप बफ़र ]], एक डेटा संरचना जो आमतौर पर टेक्स्ट संपादकों में उपयोग की जाती है जो एक ही स्थान के पास क्लस्टर किए गए कुशल सम्मिलन और विलोपन संचालन की अनुमति देती है
+*एनफिलेड (ज़ानाडु), 1970 के दशक की शुरुआत की एक समान डेटा स्ट्रक्चर
-* टुकड़ा तालिका, एक अन्य डेटा संरचना जो आमतौर पर पाठ संपादकों में उपयोग की जाती है
+* [[ गैप बफ़र | गैप बफ़र]] , एक डेटा स्ट्रक्चर जो आमतौर पर टेक्स्ट संपादकों में उपयोग की जाती है जो एक ही स्थान के पास क्लस्टर किए गए कुशल सम्मिलन और विलोपन ऑपरेशन की अनुमति देती है
+* टुकड़ा टेबल, एक अन्य डेटा स्ट्रक्चर जो आमतौर पर पाठ संपादकों में उपयोग की जाती है
 ==संदर्भ==

v t e Strings
String metric	Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Gestalt Pattern Matching Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm
String-searching algorithm	Apostolico–Giancarlo algorithm Boyer–Moore string-search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp algorithm
Multiple string searching	Aho–Corasick Commentz-Walter algorithm
Regular expression	Comparison of regular-expression engines Regular grammar Thompson's construction Nondeterministic finite automaton
Sequence alignment	Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm
Data structure	DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie
Other	Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting

Anonymous

Search

रोप (डेटा संरचना): Difference between revisions

Namespaces

More

Page actions

Revision as of 21:44, 2 August 2023

Contents

विवरण

ऑपरेशन

कलेक्ट लीव्स

रीबैलेंस

इन्सर्ट

इंडेक्स

कॉनकैट

स्प्लिट

डिलीट

रिपोर्ट

मोनोलिथिक ऐरे के साथ कमपैरीजन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

रोप (डेटा संरचना): Difference between revisions

Revision as of 21:44, 2 August 2023

विवरण

ऑपरेशन

कलेक्ट लीव्स

रीबैलेंस

इन्सर्ट

इंडेक्स

कॉनकैट

स्प्लिट

डिलीट

रिपोर्ट

मोनोलिथिक ऐरे के साथ कमपैरीजन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories