deno.land / std@0.166.0 / collections / binary_search_node.ts

binary_search_node.ts
نووسراو ببینە
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license./** This module is browser compatible. */
export type Direction = "left" | "right";
export class BinarySearchNode<T> { left: BinarySearchNode<T> | null; right: BinarySearchNode<T> | null; constructor(public parent: BinarySearchNode<T> | null, public value: T) { this.left = null; this.right = null; }
static from<T>(node: BinarySearchNode<T>): BinarySearchNode<T> { const copy: BinarySearchNode<T> = new BinarySearchNode( node.parent, node.value, ); copy.left = node.left; copy.right = node.right; return copy; }
directionFromParent(): Direction | null { return this.parent === null ? null : this === this.parent.left ? "left" : this === this.parent.right ? "right" : null; }
findMinNode(): BinarySearchNode<T> { let minNode: BinarySearchNode<T> | null = this.left; while (minNode?.left) minNode = minNode.left; return minNode ?? this; }
findMaxNode(): BinarySearchNode<T> { let maxNode: BinarySearchNode<T> | null = this.right; while (maxNode?.right) maxNode = maxNode.right; return maxNode ?? this; }
findSuccessorNode(): BinarySearchNode<T> | null { if (this.right !== null) return this.right.findMinNode(); let parent: BinarySearchNode<T> | null = this.parent; let direction: Direction | null = this.directionFromParent(); while (parent && direction === "right") { direction = parent.directionFromParent(); parent = parent.parent; } return parent; }}
std
Deno standard library
GitHub Repositorydenoland/deno_std
GitHub Stars
2458

Version Info

Tagged at
2 months ago