/** * Binary search tree object. * * This is a self-balancing (AVL) binary search tree that behaves as a * multiset: duplicate values are allowed, and removing a value removes * exactly one node holding it. Balancing keeps insert, remove, min, and * max at O(log n) regardless of insertion order, including monotonic or * duplicate-heavy sequences that would otherwise degenerate a plain BST * into a linked list. */ export declare class BinarySearchTree { private root; /** * Inserts the given value. * @param value numeric value. */ insert(value: number): void; /** * Removes the given value. * @param value numeric value. * @return value removed. */ remove(value: number): boolean; /** * Min value. * @return min value. */ min(): number; /** * Max value. * @return max value. */ max(): number; /** * Height of the given node, or 0 for an empty subtree. * @param node tree node. * @return height. */ private static height; /** * Recomputes and stores the height of the given node from its children. * @param node tree node. */ private static updateHeight; /** * Balance factor of the given node (left height minus right height). * @param node tree node. * @return balance factor. */ private static balanceFactor; /** * Rotates the given node right, and returns the new subtree root. * @param node tree node. * @return new subtree root. */ private static rotateRight; /** * Rotates the given node left, and returns the new subtree root. * @param node tree node. * @return new subtree root. */ private static rotateLeft; /** * Updates the given node's height, and rebalances it with single or * double rotations if it has become unbalanced. * @param node tree node. * @return new, balanced subtree root. */ private static rebalance; /** * Recursively inserts the given value under the given subtree root, and * returns the new, balanced subtree root. * @param node subtree root. * @param value numeric value. * @return new subtree root. */ private static insertNode; /** * Recursively removes one node holding the given value from under the * given subtree root, and returns the new, balanced subtree root along * with whether a node was removed. * @param node subtree root. * @param value numeric value. * @return remove result. */ private static removeNode; /** * Min node under the given subtree root. * @param node subtree root. * @return min node. */ private static minNode; /** * Max node under the given subtree root. * @param node subtree root. * @return max node. */ private static maxNode; }