0
# Trees & Hierarchical Structures
1

2
Tree data structures for prefix matching, spatial queries, fuzzy search, and range operations.
3

4
## Capabilities
5

6
### Trie
7

8
Prefix tree for efficient string prefix operations and autocomplete functionality.
9

10
```typescript { .api }
11
/**
12
 * Prefix tree for string operations
13
 * @param Token Optional token constructor for custom tokenization
14
 */
15
function Trie<T>(Token?: new () => T): Trie<T>;
16

17
interface Trie<T> {
18
  readonly size: number;
19
  
20
  /** Add string/sequence to trie */
21
  add(sequence: Iterable<T>): this;
22
  
23
  /** Remove string/sequence from trie */
24
  delete(sequence: Iterable<T>): boolean;
25
  
26
  /** Check if exact sequence exists */
27
  has(sequence: Iterable<T>): boolean;
28
  
29
  /** Find node for given prefix */
30
  find(prefix: Iterable<T>): TrieNode<T> | null;
31
  
32
  /** Get all sequences with given prefix */
33
  prefixes(prefix: Iterable<T>): Array<Array<T>>;
34
  
35
  /** Remove all sequences */
36
  clear(): void;
37
  
38
  values(): IterableIterator<Array<T>>;
39
  [Symbol.iterator](): IterableIterator<Array<T>>;
40
  
41
  inspect(): any;
42
}
43

44
interface TrieNode<T> {
45
  /** Check if this node represents end of a sequence */
46
  readonly final: boolean;
47
  
48
  /** Get child node for token */
49
  get(token: T): TrieNode<T> | undefined;
50
  
51
  /** Check if child exists for token */
52
  has(token: T): boolean;
53
  
54
  /** Iterate over all sequences from this node */
55
  suffixes(): Array<Array<T>>;
56
}
57
```
58

59
### TrieMap
60

61
Trie with key-value associations for prefix-based lookups.
62

63
```typescript { .api }
64
/**
65
 * Prefix tree with key-value associations
66
 * @param Token Optional token constructor for custom tokenization
67
 */
68
function TrieMap<T, V>(Token?: new () => T): TrieMap<T, V>;
69

70
interface TrieMap<T, V> {
71
  readonly size: number;
72
  
73
  /** Store key-value pair */
74
  set(key: Iterable<T>, value: V): this;
75
  
76
  /** Get value for exact key */
77
  get(key: Iterable<T>): V | undefined;
78
  
79
  /** Check if exact key exists */
80
  has(key: Iterable<T>): boolean;
81
  
82
  /** Remove key-value pair */
83
  delete(key: Iterable<T>): boolean;
84
  
85
  /** Find node for given prefix */
86
  find(prefix: Iterable<T>): TrieMapNode<T, V> | null;
87
  
88
  /** Get all key-value pairs with given prefix */
89
  prefixes(prefix: Iterable<T>): Array<[Array<T>, V]>;
90
  
91
  clear(): void;
92
  
93
  values(): IterableIterator<V>;
94
  keys(): IterableIterator<Array<T>>;
95
  entries(): IterableIterator<[Array<T>, V]>;
96
  [Symbol.iterator](): IterableIterator<[Array<T>, V]>;
97
  
98
  inspect(): any;
99
}
100
```
101

102
### BKTree
103

104
Burkhard-Keller tree for fuzzy string matching with edit distance.
105

106
```typescript { .api }
107
/**
108
 * BK-Tree for fuzzy string matching
109
 * @param distance Distance function (e.g., Levenshtein distance)
110
 */
111
function BKTree(distance: DistanceFunction): BKTree;
112

113
interface BKTree {
114
  readonly size: number;
115
  
116
  /** Add item to tree */
117
  add(item: string): this;
118
  
119
  /** Search for items within tolerance */
120
  search(query: string, tolerance: number): Array<string>;
121
  
122
  /** Remove all items */
123
  clear(): void;
124
  
125
  values(): IterableIterator<string>;
126
  [Symbol.iterator](): IterableIterator<string>;
127
  
128
  inspect(): any;
129
}
130

131
type DistanceFunction = (a: string, b: string) => number;
132
```
133

134
### KDTree
135

136
k-dimensional tree for efficient spatial queries and nearest neighbor search.
137

138
```typescript { .api }
139
/**
140
 * k-dimensional tree for spatial data
141
 * @param dimensions Number of dimensions
142
 * @param distance Optional distance function
143
 * @param axisAccessor Optional function to access axis values
144
 */
145
function KDTree(
146
  dimensions: number,
147
  distance?: DistanceFunction,
148
  axisAccessor?: AxisAccessor
149
): KDTree;
150

151
interface KDTree {
152
  readonly dimensions: number;
153
  readonly size: number;
154
  
155
  /** Add point to tree */
156
  add(point: Point): this;
157
  
158
  /** Find k nearest neighbors */
159
  nearestNeighbor(query: Point, k?: number): Array<Point>;
160
  
161
  /** Find all points within range */
162
  range(bounds: Bounds): Array<Point>;
163
  
164
  clear(): void;
165
  
166
  values(): IterableIterator<Point>;
167
  [Symbol.iterator](): IterableIterator<Point>;
168
  
169
  inspect(): any;
170
}
171

172
type Point = Array<number> | {[key: string]: number};
173
type Bounds = Array<[number, number]>; // Min-max pairs for each dimension
174
type AxisAccessor = (point: Point, axis: number) => number;
175
```
176

177
### VPTree
178

179
Vantage-point tree for metric space queries and similarity search.
180

181
```typescript { .api }
182
/**
183
 * Vantage-point tree for metric space queries
184
 * @param distance Distance function for items
185
 * @param items Optional initial items to build tree
186
 */
187
function VPTree(distance: DistanceFunction, items?: Array<any>): VPTree;
188

189
interface VPTree {
190
  readonly size: number;
191
  
192
  /** Find k nearest neighbors */
193
  nearestNeighbors(query: any, k: number): Array<any>;
194
  
195
  /** Find all items within radius */
196
  neighbors(query: any, radius: number): Array<any>;
197
  
198
  values(): IterableIterator<any>;
199
  [Symbol.iterator](): IterableIterator<any>;
200
  
201
  inspect(): any;
202
}
203
```
204

205
### StaticIntervalTree
206

207
Static interval tree for efficient range overlap queries.
208

209
```typescript { .api }
210
/**
211
 * Static interval tree for range queries
212
 * @param intervals Array of intervals to build tree from
213
 */
214
function StaticIntervalTree(intervals: Array<Interval>): StaticIntervalTree;
215

216
interface StaticIntervalTree {
217
  readonly size: number;
218
  
219
  /** Find all intervals overlapping with query interval */
220
  search(interval: Interval): Array<Interval>;
221
  
222
  values(): IterableIterator<Interval>;
223
  [Symbol.iterator](): IterableIterator<Interval>;
224
  
225
  inspect(): any;
226
}
227

228
type Interval = [number, number]; // [start, end]
229
```
230

231
## Usage Examples
232

233
### Trie Example
234

235
```typescript
236
import {Trie} from "mnemonist";
237

238
// String trie for autocomplete
239
const dictionary = new Trie();
240
dictionary.add("apple");
241
dictionary.add("application");
242
dictionary.add("apply");
243
dictionary.add("banana");
244

245
console.log(dictionary.has("app")); // false (not complete word)
246
console.log(dictionary.has("apple")); // true
247

248
// Get all words with prefix
249
const suggestions = dictionary.prefixes("app");
250
console.log(suggestions); // [["apple"], ["application"], ["apply"]]
251

252
// Navigate trie structure
253
const appNode = dictionary.find("app");
254
if (appNode) {
255
  console.log(appNode.suffixes()); // All suffixes from "app"
256
}
257
```
258

259
### TrieMap Example
260

261
```typescript
262
import {TrieMap} from "mnemonist";
263

264
// Prefix-based configuration
265
const config = new TrieMap();
266
config.set("server.port", 8080);
267
config.set("server.host", "localhost");
268
config.set("database.url", "mongodb://localhost");
269

270
console.log(config.get("server.port")); // 8080
271

272
// Get all configs with prefix
273
const serverConfigs = config.prefixes("server");
274
// [[["server", "port"], 8080], [["server", "host"], "localhost"]]
275
```
276

277
### BKTree Example
278

279
```typescript
280
import {BKTree} from "mnemonist";
281

282
// Levenshtein distance function
283
function levenshtein(a: string, b: string): number {
284
  // Implementation of edit distance
285
  const matrix = [];
286
  for (let i = 0; i <= b.length; i++) {
287
    matrix[i] = [i];
288
  }
289
  for (let j = 0; j <= a.length; j++) {
290
    matrix[0][j] = j;
291
  }
292
  for (let i = 1; i <= b.length; i++) {
293
    for (let j = 1; j <= a.length; j++) {
294
      if (b.charAt(i - 1) === a.charAt(j - 1)) {
295
        matrix[i][j] = matrix[i - 1][j - 1];
296
      } else {
297
        matrix[i][j] = Math.min(
298
          matrix[i - 1][j - 1] + 1,
299
          matrix[i][j - 1] + 1,
300
          matrix[i - 1][j] + 1
301
        );
302
      }
303
    }
304
  }
305
  return matrix[b.length][a.length];
306
}
307

308
// Spell checker
309
const spellChecker = new BKTree(levenshtein);
310
spellChecker.add("javascript");
311
spellChecker.add("python");
312
spellChecker.add("typescript");
313

314
// Find similar words
315
const suggestions = spellChecker.search("javascrip", 2);
316
console.log(suggestions); // ["javascript"] (distance 1)
317
```
318

319
### KDTree Example
320

321
```typescript
322
import {KDTree} from "mnemonist";
323

324
// 2D spatial index
325
const spatialIndex = new KDTree(2);
326
spatialIndex.add([1, 2]);
327
spatialIndex.add([3, 4]);
328
spatialIndex.add([5, 1]);
329
spatialIndex.add([2, 8]);
330

331
// Find nearest neighbors
332
const nearest = spatialIndex.nearestNeighbor([2, 3], 2);
333
console.log(nearest); // Closest 2 points to [2, 3]
334

335
// Range query
336
const inRange = spatialIndex.range([[0, 4], [0, 5]]);
337
console.log(inRange); // Points in rectangle (0,0) to (4,5)
338
```
339

340
### VPTree Example
341

342
```typescript
343
import {VPTree} from "mnemonist";
344

345
// Text similarity search
346
function cosineSimilarity(a: string, b: string): number {
347
  // Implementation of cosine similarity
348
  return /* calculated similarity */;
349
}
350

351
const documents = [
352
  "machine learning algorithms",
353
  "deep learning neural networks", 
354
  "artificial intelligence systems",
355
  "natural language processing"
356
];
357

358
const similarityIndex = new VPTree(cosineSimilarity, documents);
359

360
// Find similar documents
361
const query = "neural network learning";
362
const similar = similarityIndex.nearestNeighbors(query, 2);
363
console.log(similar); // Most similar documents
364
```
365

366
## Performance Characteristics
367

368
| Operation | Trie | BKTree | KDTree | VPTree | IntervalTree |
369
|-----------|------|--------|---------|---------|--------------|
370
| Insert | O(k) | O(log n) | O(log n) | O(n log n) build | N/A (static) |
371
| Search | O(k) | O(log n) avg | O(log n + r) | O(log n) | O(log n + r) |
372
| Prefix Query | O(k + m) | N/A | N/A | N/A | N/A |
373
| Range Query | N/A | O(n) worst | O(log n + r) | O(log n + r) | O(log n + r) |
374
| Space | O(n·k) | O(n) | O(n) | O(n) | O(n) |
375
376
Where:
377
- k = average key/string length
378
- n = number of items
379
- m = number of results
380
- r = number of results in range
381

382
## Choosing the Right Tree
383

384
- **Trie/TrieMap**: For prefix matching, autocomplete, string dictionaries
385
- **BKTree**: For fuzzy string matching, spell checking
386
- **KDTree**: For spatial data, nearest neighbor in k-dimensional space
387
- **VPTree**: For similarity search in metric spaces
388
- **StaticIntervalTree**: For range overlap queries on intervals