Class SkipList<T>

Список с пропусками (skip list) — вероятностная альтернатива сбалансированным деревьям. Хранит уникальные значения в отсортированном порядке; insert/delete/has — O(log n) в среднем. Проще в реализации, чем деревья, и хорошо подходит для конкурентных сценариев.

Example

const list = new SkipList([5, 1, 3]);
list.insert(2);
[...list]; // [1, 2, 3, 5]
[...list.range(2, 4)]; // [2, 3]

Type Parameters

Implements

Iterable<T>

Index

Constructors

constructor

new SkipList<T>(
    iterable?: Iterable<T>,
    compare?: Comparator<T>,
    random?: () => number,
): SkipList<T>
Type Parameters
- T
Parameters
- iterable: Iterable<T> = []
- compare: Comparator<T> = defaultCompare
- random: () => number = Math.random
  Источник случайных чисел в [0, 1); можно подменить для детерминированных тестов.
Returns SkipList<T>
- Defined in SkipList.ts:33

Accessors

size

get size(): number
Returns number
- Defined in SkipList.ts:100

Methods

insert

insert(value: T): boolean
Вставляет значение. Дубликаты игнорируются. Возвращает true, если значение добавлено.
Parameters
- value: T
Returns boolean
- Defined in SkipList.ts:41

delete

delete(value: T): boolean
Удаляет значение. Возвращает true, если оно было в списке.
Parameters
- value: T
Returns boolean
- Defined in SkipList.ts:61

has

has(value: T): boolean
Parameters
- value: T
Returns boolean
- Defined in SkipList.ts:74

min

min(): T | undefined
Returns T | undefined
- Defined in SkipList.ts:79

max

max(): T | undefined
Returns T | undefined
- Defined in SkipList.ts:83

range

range(low: T, high: T): IterableIterator<T>
Значения из отрезка [low, high] в порядке возрастания.
Parameters
- low: T
- high: T
Returns IterableIterator<T>
- Defined in SkipList.ts:92

isEmpty

isEmpty(): boolean
Returns boolean
- Defined in SkipList.ts:104

clear

clear(): void
Returns void
- Defined in SkipList.ts:108

toArray

toArray(): T[]
Returns T[]
- Defined in SkipList.ts:114

[iterator]

"[iterator]"(): IterableIterator<T>
Returns IterableIterator<T>
Implementation of Iterable.[iterator]
- Defined in SkipList.ts:118

Class SkipList<T>

Example

Type Parameters

Implements

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns SkipList<T>

Accessors

size

Returns number

Methods

insert

Parameters

Returns boolean

delete

Parameters

Returns boolean

has

Parameters

Returns boolean

min

Returns T | undefined

max

Returns T | undefined

range

Parameters

Returns IterableIterator<T>

isEmpty

Returns boolean

clear

Returns void

toArray

Returns T[]

[iterator]

Returns IterableIterator<T>

Settings

On This Page