bstrees
    Preparing search index...

    Interface SortedTree<T>Abstract

    A sorted collection of unique values, ordered by a Comparator. BSTree and AVLTree share this API; use this type to accept either of them.

    Values are unique with respect to the comparator: inserting a value equal to a stored one keeps the stored one. Iteration yields values in ascending order.

    Every method that takes a value passes it to the comparator, even when the tree is empty, so a value the comparator rejects (such as NaN with the default comparator) throws whether the tree is empty or not.

    The comparator must not modify the tree it orders: the mutating methods (insert, getOrInsert, delete, clear, popMin and popMax) throw a TypeError when the comparator calls them, and leave the tree unchanged.

    interface SortedTree<T> {
        get height(): number;
        get size(): number;
        "[iterator]"(): TreeIterator<T>;
        ceil(value: T): T | undefined;
        clear(): void;
        delete(value: T): boolean;
        floor(value: T): T | undefined;
        forEach(
            callback: (value: T, index: number, tree: this) => void,
            thisArg?: unknown,
        ): void;
        get(value: T): T | undefined;
        getOrInsert(value: T): T;
        has(value: T): boolean;
        higher(value: T): T | undefined;
        insert(value: T): boolean;
        lower(value: T): T | undefined;
        max(): T | undefined;
        min(): T | undefined;
        popMax(): T | undefined;
        popMin(): T | undefined;
        range(options?: RangeOptions<T>): TreeIterator<T>;
        toArray(): T[];
        values(): TreeIterator<T>;
        valuesReversed(): TreeIterator<T>;
    }

    Type Parameters

    • T

    Hierarchy (View Summary)

    Implements

    • Iterable<T>
    Index
    height size
    [iterator] ceil clear delete floor forEach get getOrInsert has higher insert lower max min popMax popMin range toArray values valuesReversed
    • get height(): number

      The number of edges on the longest path from the root to a leaf: -1 for an empty tree and 0 for a tree with a single value. O(1).

      Returns number

    • get size(): number

      The number of values in the tree. O(1).

      Returns number

    • Returns the least value greater than or equal to value.

      Parameters

      • value: T

      Returns T | undefined

      If the comparator rejects the value.

    • Removes the value equal to value.

      Parameters

      • value: T

      Returns boolean

      true if a value was removed.

      If the comparator rejects the value.

    • Returns the greatest value less than or equal to value.

      Parameters

      • value: T

      Returns T | undefined

      If the comparator rejects the value.

    • Calls callback for every value in ascending order.

      Parameters

      • callback: (value: T, index: number, tree: this) => void
      • OptionalthisArg: unknown

      Returns void

    • Returns the stored value equal to value. Useful when the comparator only looks at a key: pass a probe with that key to get the stored record.

      Parameters

      • value: T

      Returns T | undefined

      const users = new AVLTree<{ id: number; name: string }>((a, b) => a.id - b.id);
      users.insert({ id: 1, name: "Alice" });
      users.get({ id: 1, name: "" })?.name; // "Alice"

      If the comparator rejects the value.

    • Returns the stored value equal to value, inserting value first if there is none.

      Parameters

      • value: T

      Returns T

      const book = new AVLTree<{ price: number; orders: number[] }>(
        (a, b) => a.price - b.price,
      );
      book.getOrInsert({ price: 10, orders: [] }).orders.push(1);
      book.getOrInsert({ price: 10, orders: [] }).orders.push(2);
      book.get({ price: 10, orders: [] })?.orders; // [1, 2]

      If the comparator rejects the value.

    • Checks whether the tree contains a value equal to value.

      Parameters

      • value: T

      Returns boolean

      If the comparator rejects the value.

    • Returns the least value strictly greater than value.

      Parameters

      • value: T

      Returns T | undefined

      If the comparator rejects the value.

    • Inserts value unless an equal value is already stored (that value is kept as is).

      Parameters

      • value: T

      Returns boolean

      true if the value was inserted.

      If the comparator rejects the value.

    • Returns the greatest value strictly less than value.

      Parameters

      • value: T

      Returns T | undefined

      If the comparator rejects the value.

    • Returns the largest value, or undefined if the tree is empty.

      Returns T | undefined

    • Returns the smallest value, or undefined if the tree is empty.

      Returns T | undefined

    • Removes and returns the largest value.

      Returns T | undefined

    • Removes and returns the smallest value.

      Returns T | undefined

    • Iterates over the values within the bounds, in ascending order unless reverse is set. Modifications during the iteration follow the same rules as for SortedTree.values.

      Parameters

      Returns TreeIterator<T>

      const tree = AVLTree.from([1, 2, 3, 4, 5]);
      [...tree.range({ gte: 2, lt: 4 })]; // [2, 3]
      [...tree.range({ gt: 3, reverse: true })]; // [5, 4]

      If both gt and gte (or lt and lte) are set, or if the comparator rejects a bound. When range is called, each bound is compared with itself and, if the tree is not empty, with a stored value, so an invalid bound throws before the iteration starts.

    • Iterates over the values in ascending order.

      The tree may be modified during the iteration: removed values are skipped, values inserted ahead of the iterator are visited and values inserted behind it are not. Unlike with a Set, a value is never visited twice, even if it is deleted and inserted again.

      After the tree changes, the iterator finds its place again by comparing with the last value it returned. While you use the iterator, do not change the fields the comparator reads of that value, even after removing it from the tree.

      Returns TreeIterator<T>

    Settings
    Member Visibility

    On This Page
    Accessors
    Methods