Skip to main content
Module

std/collections/bs_node.ts

Deno standard library
Go to Latest
File
// Copyright 2018-2022 the Deno authors. All rights reserved. MIT license./** This module is browser compatible. */
export type direction = "left" | "right";
export class BSNode<T> { left: BSNode<T> | null; right: BSNode<T> | null; constructor(public parent: BSNode<T> | null, public value: T) { this.left = null; this.right = null; }
static from<T>(node: BSNode<T>): BSNode<T> { const copy: BSNode<T> = new BSNode(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(): BSNode<T> { let minNode: BSNode<T> | null = this.left; while (minNode?.left) minNode = minNode.left; return minNode ?? this; }
findMaxNode(): BSNode<T> { let maxNode: BSNode<T> | null = this.right; while (maxNode?.right) maxNode = maxNode.right; return maxNode ?? this; }
findSuccessorNode(): BSNode<T> | null { if (this.right !== null) return this.right.findMinNode(); let parent: BSNode<T> | null = this.parent; let direction: direction | null = this.directionFromParent(); while (parent && direction === "right") { direction = parent.directionFromParent(); parent = parent.parent; } return parent; }}