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

    Class RedBlackTree<T>

    Красно-чёрное дерево (левостороннее, LLRB по Седжвику). Высота не превышает 2·log₂(n), insert/delete/has — O(log n). По сравнению с AVLTree делает меньше поворотов при изменениях.

    const tree = new RedBlackTree<string>();
    tree.insert('banana');
    tree.insert('apple');
    [...tree.range('a', 'b')]; // ['apple']

    Type Parameters

    • T

    Hierarchy (View Summary)

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

      Returns number

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

      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>

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

      Parameters

      • value: T

      Returns boolean

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

      Parameters

      • value: T

      Returns boolean

    Settings
    Member Visibility

    On This Page
    Constructors
    Accessors
    Methods