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

    Class AVLTree<T>

    Самобалансирующееся AVL-дерево: высоты поддеревьев любого узла отличаются не более чем на 1. insert/delete/has — гарантированно O(log n). Даёт чуть более быстрый поиск, чем RedBlackTree, за счёт более частых поворотов.

    const tree = new AVLTree([1, 2, 3, 4, 5, 6, 7]);
    tree.height(); // 3 — несмотря на отсортированную вставку

    Type Parameters

    • T

    Hierarchy (View Summary)

    Index
    constructor
    size
    insert delete height has get min max floor ceil lower higher range 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