ds-kit-js - v1.1.0
    Preparing search index...

    Class BinarySearchTree<T>

    Несбалансированное двоичное дерево поиска (BST). Операции — O(h), где h — высота дерева: O(log n) в среднем на случайных данных, O(n) в худшем случае (например, при вставке отсортированной последовательности). Для гарантированного O(log n) используйте AVLTree или RedBlackTree.

    const tree = new BinarySearchTree([8, 3, 10, 1, 6]);
    tree.has(6); // true
    [...tree]; // [1, 3, 6, 8, 10]
    tree.floor(7); // 6

    const byAge = new BinarySearchTree<{ name: string; age: number }>([], (a, b) => a.age - b.age);

    Type Parameters

    • T

    Hierarchy (View Summary)

    Index
    constructor
    size
    insert delete has get min max floor ceil lower higher range height isEmpty clear inOrder preOrder postOrder levelOrder toArray [iterator]
    • get size(): number

      Returns number

    • Вставляет значение. Дубликаты игнорируются. Возвращает true, если значение добавлено.

      Parameters

      • value: T

      Returns boolean

    • Удаляет значение. Возвращает true, если оно было в дереве.

      Parameters

      • value: T

      Returns boolean

    • Проверяет, есть ли значение в дереве.

      Parameters

      • value: T

      Returns boolean

    • Возвращает хранящийся в дереве элемент, равный value по компаратору. Полезно, когда компаратор сравнивает только часть объекта (например, ключ).

      Parameters

      • value: T

      Returns T | undefined

    • Наибольшее значение, не превышающее value.

      Parameters

      • value: T

      Returns T | undefined

    • Наименьшее значение, не меньшее value.

      Parameters

      • value: T

      Returns T | undefined

    • Наибольшее значение, строго меньшее value (предыдущий элемент).

      Parameters

      • value: T

      Returns T | undefined

    • Наименьшее значение, строго большее value (следующий элемент).

      Parameters

      • value: T

      Returns T | undefined

    • Значения из отрезка [low, high] в порядке возрастания. Посещает только нужные поддеревья.

      Parameters

      • low: T
      • high: T

      Returns IterableIterator<T>

    • Симметричный обход (в отсортированном порядке).

      Returns IterableIterator<T>

    • Прямой обход: корень, левое поддерево, правое поддерево.

      Returns IterableIterator<T>

    • Обратный обход: левое поддерево, правое поддерево, корень.

      Returns IterableIterator<T>

    • Итерация в отсортированном порядке.

      Returns IterableIterator<T>

    Settings
    Member Visibility

    On This Page
    Constructors
    Accessors
    Methods