Упорядоченные множества и словари

Встроенные Set и Map хранят элементы в порядке вставки и не умеют быстро находить минимум, соседей или диапазон. Структуры из этого раздела хранят элементы отсортированными.

Общий API деревьев

BinarySearchTree, AVLTree и RedBlackTree наследуют BinaryTree и поддерживают одинаковые методы:

import { RedBlackTree } from 'ds-kit-js';

const timestamps = new RedBlackTree([1000, 1500, 2300, 4100]);
timestamps.floor(2000);              // 1500 — последнее событие до 2000
timestamps.ceil(2000);               // 2300 — первое событие после 2000
timestamps.lower(1500);              // 1000 — событие перед 1500
timestamps.higher(1500);             // 2300 — событие после 1500
[...timestamps.range(1200, 3000)];   // [1500, 2300]
Copy

BinarySearchTree

Классическое двоичное дерево поиска без балансировки. Полезно для изучения и как основа для экспериментов. На отсортированных данных вырождается в список с высотой n.

AVLTree

Строго сбалансированное дерево: высоты поддеревьев любого узла отличаются не более чем на 1. Поиск в нём быстрее, чем в красно-чёрном дереве, зато вставки и удаления требуют больше поворотов.

RedBlackTree

Левостороннее красно-чёрное дерево (LLRB) Роберта Седжвика. Высота не превышает 2·log₂ n. Хороший выбор по умолчанию.

SkipList — список с пропусками

Вероятностная структура: многоуровневый связный список, в котором каждый уровень «перепрыгивает» через часть элементов. Даёт O(log n) в среднем и поддерживает insert, delete, has, min, max, range.

import { SkipList } from 'ds-kit-js';

const scores = new SkipList([40, 10, 30]);
scores.insert(20);
[...scores];             // [10, 20, 30, 40]
[...scores.range(15, 35)]; // [20, 30]
Copy

Третьим аргументом конструктора можно передать собственный генератор случайных чисел, чтобы структура списка была воспроизводимой в тестах.

SortedMap — упорядоченный словарь

Словарь на основе красно-чёрного дерева, ключи которого всегда отсортированы. Интерфейс похож на Map (get, set, has, delete, keys, values, entries), плюс навигация по ключам: firstKey/lastKey, floorKey/ceilKey, lowerKey/higherKey и выборка entriesBetween:

import { SortedMap } from 'ds-kit-js';

// Тарифная сетка: найти ставку для суммы
const rates = new SortedMap<number, number>([
  [0, 0.13],
  [2_400_000, 0.15],
  [5_000_000, 0.18],
]);

const bracket = rates.floorKey(3_000_000); // 2_400_000
rates.get(bracket!);                       // 0.15

[...rates.entriesBetween(0, 3_000_000)];   // [[0, 0.13], [2400000, 0.15]]
rates.firstKey(); // 0
rates.lastKey();  // 5000000
Copy