import { ascend } from "./_comparators.ts";import { BinarySearchNode, Direction } from "./binary_search_node.ts";export * from "./_comparators.ts";
export class BinarySearchTree<T> implements Iterable<T> { protected root: BinarySearchNode<T> | null = null; protected _size = 0; constructor( protected compare: (a: T, b: T) => number = ascend, ) {}
static from<T>( collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, ): BinarySearchTree<T>; static from<T>( collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options: { compare?: (a: T, b: T) => number; }, ): BinarySearchTree<T>; static from<T, U, V>( collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options: { compare?: (a: U, b: U) => number; map: (value: T, index: number) => U; thisArg?: V; }, ): BinarySearchTree<U>; static from<T, U, V>( collection: ArrayLike<T> | Iterable<T> | BinarySearchTree<T>, options?: { compare?: (a: U, b: U) => number; map?: (value: T, index: number) => U; thisArg?: V; }, ): BinarySearchTree<U> { let result: BinarySearchTree<U>; let unmappedValues: ArrayLike<T> | Iterable<T> = []; if (collection instanceof BinarySearchTree) { result = new BinarySearchTree( options?.compare ?? (collection as unknown as BinarySearchTree<U>).compare, ); if (options?.compare || options?.map) { unmappedValues = collection; } else { const nodes: BinarySearchNode<U>[] = []; if (collection.root) { result.root = BinarySearchNode.from( collection.root as unknown as BinarySearchNode<U>, ); nodes.push(result.root); } while (nodes.length) { const node: BinarySearchNode<U> = nodes.pop()!; const left: BinarySearchNode<U> | null = node.left ? BinarySearchNode.from(node.left) : null; const right: BinarySearchNode<U> | null = node.right ? BinarySearchNode.from(node.right) : null;
if (left) { left.parent = node; nodes.push(left); } if (right) { right.parent = node; nodes.push(right); } } } } else { result = (options?.compare ? new BinarySearchTree(options.compare) : new BinarySearchTree()) as BinarySearchTree<U>; unmappedValues = collection; } const values: Iterable<U> = options?.map ? Array.from(unmappedValues, options.map, options.thisArg) : unmappedValues as U[]; for (const value of values) result.insert(value); return result; }
get size(): number { return this._size; }
protected findNode(value: T): BinarySearchNode<T> | null { let node: BinarySearchNode<T> | null = this.root; while (node) { const order: number = this.compare(value as T, node.value); if (order === 0) break; const direction: "left" | "right" = order < 0 ? "left" : "right"; node = node[direction]; } return node; }
protected rotateNode(node: BinarySearchNode<T>, direction: Direction) { const replacementDirection: Direction = direction === "left" ? "right" : "left"; if (!node[replacementDirection]) { throw new TypeError( `cannot rotate ${direction} without ${replacementDirection} child`, ); } const replacement: BinarySearchNode<T> = node[replacementDirection]!; node[replacementDirection] = replacement[direction] ?? null; if (replacement[direction]) replacement[direction]!.parent = node; replacement.parent = node.parent; if (node.parent) { const parentDirection: Direction = node === node.parent[direction] ? direction : replacementDirection; node.parent[parentDirection] = replacement; } else { this.root = replacement; } replacement[direction] = node; node.parent = replacement; }
protected insertNode( Node: typeof BinarySearchNode, value: T, ): BinarySearchNode<T> | null { if (!this.root) { this.root = new Node(null, value); this._size++; return this.root; } else { let node: BinarySearchNode<T> = this.root; while (true) { const order: number = this.compare(value, node.value); if (order === 0) break; const direction: Direction = order < 0 ? "left" : "right"; if (node[direction]) { node = node[direction]!; } else { node[direction] = new Node(node, value); this._size++; return node[direction]; } } } return null; }
protected removeNode( node: BinarySearchNode<T>, ): BinarySearchNode<T> | null { const flaggedNode: BinarySearchNode<T> | null = !node.left || !node.right ? node : node.findSuccessorNode()!; const replacementNode: BinarySearchNode<T> | null = flaggedNode.left ?? flaggedNode.right;
if (replacementNode) replacementNode.parent = flaggedNode.parent; if (!flaggedNode.parent) { this.root = replacementNode; } else { flaggedNode.parent[flaggedNode.directionFromParent()!] = replacementNode; } if (flaggedNode !== node) { const swapValue = node.value; node.value = flaggedNode.value; flaggedNode.value = swapValue; }
this._size--; return flaggedNode; }
insert(value: T): boolean { return !!this.insertNode(BinarySearchNode, value); }
remove(value: T): boolean { const node: BinarySearchNode<T> | null = this.findNode(value); if (node) this.removeNode(node); return node !== null; }
find(value: T): T | null { return this.findNode(value)?.value ?? null; }
min(): T | null { return this.root ? this.root.findMinNode().value : null; }
max(): T | null { return this.root ? this.root.findMaxNode().value : null; }
clear() { this.root = null; this._size = 0; }
isEmpty(): boolean { return this.size === 0; }
*lnrValues(): IterableIterator<T> { const nodes: BinarySearchNode<T>[] = []; let node: BinarySearchNode<T> | null = this.root; while (nodes.length || node) { if (node) { nodes.push(node); node = node.left; } else { node = nodes.pop()!; yield node.value; node = node.right; } } }
*rnlValues(): IterableIterator<T> { const nodes: BinarySearchNode<T>[] = []; let node: BinarySearchNode<T> | null = this.root; while (nodes.length || node) { if (node) { nodes.push(node); node = node.right; } else { node = nodes.pop()!; yield node.value; node = node.left; } } }
*nlrValues(): IterableIterator<T> { const nodes: BinarySearchNode<T>[] = []; if (this.root) nodes.push(this.root); while (nodes.length) { const node: BinarySearchNode<T> = nodes.pop()!; yield node.value; if (node.right) nodes.push(node.right); if (node.left) nodes.push(node.left); } }
*lrnValues(): IterableIterator<T> { const nodes: BinarySearchNode<T>[] = []; let node: BinarySearchNode<T> | null = this.root; let lastNodeVisited: BinarySearchNode<T> | null = null; while (nodes.length || node) { if (node) { nodes.push(node); node = node.left; } else { const lastNode: BinarySearchNode<T> = nodes[nodes.length - 1]; if (lastNode.right && lastNode.right !== lastNodeVisited) { node = lastNode.right; } else { yield lastNode.value; lastNodeVisited = nodes.pop()!; } } } }
*lvlValues(): IterableIterator<T> { const children: BinarySearchNode<T>[] = []; let cursor: BinarySearchNode<T> | null = this.root; while (cursor) { yield cursor.value; if (cursor.left) children.push(cursor.left); if (cursor.right) children.push(cursor.right); cursor = children.shift() ?? null; } }
*[Symbol.iterator](): IterableIterator<T> { yield* this.lnrValues(); }}