29:null 2a:["$","title",null,{"children":"Text-oriented Tree Data Structures | Jo Wood | Observable"}] 2f:Td47,

Trie

A prefix tree for storing and retrieving strings efficiently. Supports insertion, deletion, and search operations, as well as depth- and breadth-first traversals. Words are represented by paths from the root to nodes marked as complete words. For string inputs, symbols and positions are measured in Unicode code points rather than JavaScript UTF-16 code units.

`constructor()`

Creates an empty trie.

`insert(word: string): Trie`

Inserts a word into the trie. Returns the trie to support method chaining.

`remove(word: string): Trie`

Removes a word from the trie if it exists. Intermediate nodes are pruned where possible. Returns the trie to support method chaining.

`has(word: string): boolean`

true if the word exists in the trie; otherwise false.

`startsWith(prefix: string): boolean`

true if any word in the trie starts with the given prefix.

`wordCount(): number`

The number of complete words stored in the trie.

`*[Symbol.iterator](): Iterable<string>`

Returns the stored words in lexicographic order, using `localeCompare()` to order the next symbol at each node. This provides a convenient way of iterating over all stored words in lexicographic order. For example,
for (const word of trie)
or
[...trie].

`*dfs(): Iterable<string>`

Generator that yields all words in depth-first order, which may not be lexicographically sorted.

`*bfs(): Iterable<string>`

Generator that yields all words in breadth-first order (shortest words first).

`clear(): Trie`

Clears all words from the trie. Returns the trie to support method chaining.

`toDot(options?: object): Element`

Generates a GraphViz dot representation of the trie structure. Accepts the following options:

rankDir: Direction of layout (e.g. "LR", "TB"; default: "LR")
scale: Scale factor for rendering (default: 1)
compact: Whether to use compact node layout (default: true)
fillClr: Function to determine node fill colour (default: based on isWord)
labelClr: Function to determine label text colour (default: "black")

30:T46c,

TrieNode

A node in a Trie, representing a single character in a word path. Each node maintains a mapping of child characters to child nodes and a flag indicating whether the node marks the end of a word.

`constructor()`

Creates an unmarked node with no children.

`children: Map<string, TrieNode>`

A map from character to child node. Represents the next possible characters from this point in the trie.

`isWord: boolean`

Indicates whether this node marks the end of a valid word.

`markAsWord(): void`

Marks this node as the end of a complete word.

`unmarkAsWord(): void`

Unmarks this node as the end of a complete word.

31:T1ac2,

SuffixTrie

A suffix trie for indexing all suffixes of a string or sequence. Supports substring lookup and retrieval of all starting positions at which a pattern occurs. Each path from the root represents a prefix of at least one suffix, so every substring of the indexed sequence is represented by some path in the trie.

For string inputs, symbols and positions are measured in Unicode code points rather than JavaScript UTF-16 code units.

When an array is supplied, each element must be a string and positions are array-element indices. Yielded factors are formed by concatenating those strings.

Unlike a compressed suffix tree, this structure stores explicit nodes for individual symbols. Construction takes ${tex`\Theta(n^2)`} time and, because occurrence positions are stored along every suffix path, ${tex`\Theta(n^2)`} space for a sequence of ${tex`n`} symbols. A compressed suffix tree or suffix array would be substantially more space-efficient.

`constructor(seq?: string | string[]): SuffixTrie`

Creates a new suffix trie. If a sequence is provided, all suffixes of that sequence are inserted during construction.

`insertSuffixes(seq: string | string[]): SuffixTrie`

Clears the current index and inserts every suffix of the given sequence into the suffix trie. Returns the suffix trie to support method chaining.

`has(pattern: string | string[]): boolean`

true if the pattern occurs as a substring of the indexed sequence.

`positionsOf(pattern: string | string[]): number[]`

Returns an array containing the starting positions at which the pattern occurs in the indexed sequence. Returns an empty array if the pattern does not occur. For an empty pattern, returns every position from 0 to the sequence length, inclusive.

`*[Symbol.iterator](): Iterable<string>`

Returns the stored words in lexicographic order, using `localeCompare()` to order the next symbol at each node. This provides a convenient way of iterating over all represented substrings. For example,
for (const factor of suffixTrie)
or
[...suffixTrie].

`*dfs(): Iterable<string>`

Generator that yields all distinct non-empty factors of the indexed sequence in depth-first order. The order depends on the insertion order of child nodes and is not necessarily lexicographic.

`*bfs(): Iterable<string>`

Generator that yields all distinct non-empty factors of the indexed sequence in breadth-first order, so shorter factors are yielded before longer factors.

`*entries(): Iterable<object>`

Generator that yields one object for each distinct non-empty factor represented in the suffix trie. Each object has the following form:

{
  factor: string,
  positions: number[],
  count: number
}

The factor property stores the substring, positions gives all starting positions at which it occurs, and count is the number of occurrences.

`*factors(options?: object): Iterable<string>`

Generator that yields distinct non-empty factors of the indexed sequence, optionally restricted by length. Unlike filtering the result of dfs() or bfs(), traversal is pruned once maxLength is reached so is useful for shorter factors in longer strings.

Accepts the following options:

minLength: Minimum factor length to yield; default: 1
maxLength: Maximum factor length to yield; default: Infinity

`*factorEntries(options?: object): Iterable<object>`

Generator that yields distinct non-empty factors of the indexed sequence together with their occurrence positions and counts, optionally restricted by length. Traversal is pruned once maxLength is reached.

Each yielded object has the following form:

{
  factor: string,
  positions: number[],
  count: number
}

Accepts the following options:

minLength: Minimum factor length to yield; default: 1
maxLength: Maximum factor length to yield; default: Infinity

`clear(): SuffixTrie`

Clears the suffix trie, removing all indexed suffixes and position data. Returns the suffix trie to support method chaining.

`toDot(options?: object): Element`

Generates a GraphViz dot representation of the suffix trie structure. Accepts the following options:

rankDir: Direction of layout, e.g. "LR" or "TB"; default: "LR"
scale: Scale factor for rendering; default: 1
compact: Whether to use compact node layout; default: true
showPositions: Whether to show stored suffix start positions on each node; default: false
fillClr: Function to determine node fill colour; default: based on whether the node stores positions
labelClr: Function to determine label text colour; default: "black"

32:T14c6,

Rope

A mutable, balanced binary tree representing a string as a sequence of leaf-sized chunks. Internal nodes store the UTF-16 length of their left subtrees, allowing character positions to be located without materialising the complete string.

All indices and lengths are measured in JavaScript UTF-16 code units. Operations that modify the rope return the rope to support method chaining.

`constructor(text?: string, options?: {chunkSize?: number})`

Creates a rope containing text, defaulting to the empty string. The text is divided into chunks and arranged as a balanced tree.

chunkSize specifies the maximum initial size of each leaf chunk; it defaults to 1024 and is clamped to a minimum of 16.

`root: RopeNode | null`

The root node of the rope, or null when the rope is empty. This property should normally be treated as read-only.

`length: number`

The total length of the represented string in UTF-16 code units. This is a read-only accessor.

`toString(): string`

Materialises and returns the complete string represented by the rope. This requires traversing all leaf chunks and takes ${tex`O(n)`} time for a string of length ${tex`n`}.

`charAt(i: number): string`

Returns the UTF-16 code unit at index i. Returns the empty string if i is negative or outside the rope.

`substring(a?: number, b?: number): string`

Returns the text between UTF-16 indices a, inclusive, and b, exclusive. The defaults are 0 and length.

Arguments are converted to numbers, truncated to integers and clamped to the rope’s bounds. If a is greater than b, the arguments are exchanged, matching String.prototype.substring().

`concat(other: string | Rope): Rope`

Appends a string or another rope. When another Rope is supplied, its text is copied into new chunks so that subsequent balancing cannot modify the supplied rope. Returns this rope to support method chaining.
Throws: TypeError if other is neither a string nor a Rope.

`insert(i: number, text: string): Rope`

Inserts text before UTF-16 index i. A negative index is treated as 0, while an index greater than length is treated as length. Inserting an empty string leaves the rope unchanged. Returns this rope to support method chaining.

`delete(a: number, b: number): Rope`

Deletes the half-open range from UTF-16 index a, inclusive, to b, exclusive. The range is clamped to the rope’s bounds. If a is greater than or equal to b, the rope is unchanged. Unlike substring(), reversed arguments are not exchanged. Returns this rope to support method chaining.

`toDot(options?: object): Element`

Generates a GraphViz dot representation of the rope. Leaf nodes show text chunks and their lengths; internal nodes show the UTF-16 length of their left subtrees. Accepts the following options:

rankDir: Direction of layout, e.g. "LR" or "TB"; default: "LR"
scale: Scale factor for rendering; default: 1
compact: Whether to use compact node layout; default: true
fillClr: Function mapping a RopeNode to its fill colour; defaults to light blue for leaves and white for internal nodes
labelClr: Function mapping a RopeNode to its label colour; default: () => "black"
maxLeafChars: Maximum number of characters shown in a leaf label before truncation; default: 24

33:T5a6,

RopeNode

A node used internally by a Rope. A leaf node stores a string chunk in text. An internal node has text === null and links to left and right subtrees. Its structural properties should be treated as read-only because changing them directly can invalidate the rope’s lengths and balance.

`text: string | null`

The text stored by a leaf node, or null for an internal node.

`left: RopeNode | null`

The node’s left child, or null when it has no left child.

`right: RopeNode | null`

The node’s right child, or null when it has no right child.

`weight: number`

For an internal node, the total UTF-16 length of its left subtree. Leaf nodes have a weight of 0.

`height: number`

The height of the subtree rooted at this node. A leaf has height 1. This value is maintained internally while the rope is rebalanced.

34:[] 2d:{"id":"b4ec1d716ae5c2e1","slug":"data-structures-text-tree","title":"Text-oriented Tree Data Structures","thumbnail":"10b65c7841955d7fa50b5ba28c4250f9345b6e5dcc0340134ce4a579bd12b3ce","access_level":"public","create_time":"$D2025-08-10T06:23:10.037Z","update_time":"$D2026-09-22T12:45:40.528Z","view_time":null,"first_public_time":"$D2026-09-22T14:24:07.893Z","has_unpublished_edits":null,"fork":{"id":"eaea325974f14571","slug":"data-structures-search-tree","title":"Search-oriented Tree Data Structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"stars":0,"starred":false,"owner":{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024"},"version":667,"publish_version":667,"role":null,"authored":false,"authors":[{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null}],"members":[{"type":"team","id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":"starter_2024","role":"editor"},{"type":"individual","id":"e2432cc13dc447d3","login":"jwolondon","name":"Jo Wood","avatar_url":"https://avatars-next.observableusercontent.com/27f72cecd1ac20853a533421fab228ce5f611cbc0986c1e420f7d3b1eb49ef50","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"cf3a41cde0560514","slug":"data-structures","title":"data structures","owner":{"id":"9461f58b209074d5","login":"jwolondon","name":"Jo Wood"}},"type":"notebook","body":{"title":"Text-oriented Tree Data Structures","cells":[{"id":0,"value":"# Text-oriented Tree Data Structures","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":465,"value":"These tree structures support particular operations on text and other symbol sequences. A trie provides efficient prefix lookup across a collection of strings, a suffix trie supports substring queries within a sequence, and a rope supports editing large strings. Their benefits depend on the workload: each trades structural memory for faster specialised operations, so simple strings or arrays may remain preferable for smaller datasets.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":60,"value":"## 1. Trie","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":327,"value":"A Trie (or 'prefix tree') is used for storing and querying strings efficiently, especially for prefix search and autocomplete tasks where we might be querying by a string prefix.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":337,"value":"info(\n md`Confusingly the word 'trie' (originally shortened from 'retrieval') is often pronounced 'tree'. Some therefore disambiguate from discussion of trees by pronouncing Trie to sound like 'try'.`\n)","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":339,"value":"A trie represents each stored word as a path of symbols from the root. Paths can share common prefixes, while the final node of each complete word is specially marked (in blue below). This makes it possible to test for complete words and retrieve words sharing a prefix efficiently. Tokenising a passage into words is a separate preprocessing step, as shown in the example below.\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":245,"value":"import { Trie } from \"observable:@jwolondon/adts-and-data-structures\"","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"const myString = \"A cat sat on the three thin mats and made an anxious miaow\";\n\ndisplay(\n myString\n .toLowerCase()\n .split(/\\s+/)\n .reduce((trie, word) => trie.insert(word), new Trie())\n .toDot({scale: 0.8})\n);","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"For string inputs, this implementation treats each Unicode code point as one trie symbol. A perceived single character or grapheme cluster may contain multiple code points. For example, the decomposed form `e\\u0301` (e followed by an acute accent) is displayed as **é** but is represented by two trie nodes.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":62,"value":"$2f","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":64,"value":"$30","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":479,"value":"## 2. Suffix Trie","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":523,"value":"A suffix trie represents a sequence one symbol at a time. Every path from the root represents a prefix of at least one suffix and therefore a factor of the indexed sequence.\n\nTo ensure that every suffix ends at a leaf, a unique terminal symbol not otherwise present in the sequence is commonly appended—often **`$`**.\n\nFor example, appending `$` to `banana` produces six terminated non-empty suffixes, together with `$`, which represents the empty suffix of the original string:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":489,"value":"import {SuffixTrie} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":486,"value":"new SuffixTrie(\"banana$\").toDot()","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":484,"value":"$31","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":527,"value":"

SuffixTrieNode

\n\n

`children: Map<string, SuffixTrieNode>`

A map from each following symbol to its child node.

\n\n

`positions: number[]`

\n The starting positions of occurrences represented by the path ending\n at this node. String positions are Unicode code-point indices.\n

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":467,"value":"## 3. Rope","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":472,"value":"A [rope](https://en.wikipedia.org/wiki/Rope_%28data_structure%29) is a balanced binary tree for representing very large strings. Text is stored in chunks at the leaves, while internal nodes store structural information that allows the tree to locate character positions efficiently. Splitting, joining, inserting and deleting can modify only part of the tree rather than copying the entire string.\n\nFor a rope containing ${tex`c`} chunks, navigating to a position and performing structural splits or joins takes ${tex`\\log c`} time. Processing inserted or returned text also takes time proportional to the amount of text involved. Materialising the complete result with `toString()` still takes ${tex`O(n)`} time, so ropes are most useful when very large strings are edited repeatedly but converted to conventional strings less frequently.\n\nHere's an example, noting it is to illustrate the data structure only — there would be no need to use a Rope for such a small string in practice:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":476,"value":"import {Rope} from \"observable:@jwolondon/adts-and-data-structures\";","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":528,"value":"const myRope = new Rope(\"The quick brown fox\", {chunkSize: 16})\n .insert(16, \"agile \")\n .concat(\" jumps.\");\n\ndisplay(myRope.toDot());\ndisplay(myRope.toString())","pinned":true,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":529,"value":"$32","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":530,"value":"$33","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"---\n\n## Appendices","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":15,"value":"_For API doc and page styling:_","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":524,"value":"import {defaultStyle} from \"observable:@jwolondon/utilities-cdt-2026\";\nimport {info} from \"observable:@jwolondon/schema-cdt-2026\"","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"import { apiStyle } from \"observable:@jwolondon/data-structure-docs\"","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":525,"value":"defaultStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"apiStyle()","pinned":false,"hidden":false,"mode":"ts","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"2","titling":"auto"}} 2e:"$2d:body"