Class BinaryTree<T, N>`Abstract`

Общая основа упорядоченных двоичных деревьев поиска (BinarySearchTree, AVLTree, RedBlackTree): поиск, floor/ceil, диапазоны и обходы. Наследники реализуют только вставку и удаление.

Type Parameters

T
N extends BinaryTreeNode<T> = BinaryTreeNode<T>

Hierarchy (View Summary)

BinaryTree

Implements

Iterable<T>

Index

Constructors

Accessors

Methods

insert delete has get min max floor ceil lower higher range height isEmpty clear inOrder preOrder postOrder levelOrder toArray [iterator]

Constructors

constructor

new BinaryTree<T, N extends BinaryTreeNode<T> = BinaryTreeNode<T>>(
compare?: Comparator<T>,
): BinaryTree<T, N>
Type Parameters
- T
- N extends BinaryTreeNode<T> = BinaryTreeNode<T>
Parameters
- compare: Comparator<T> = defaultCompare
Returns BinaryTree<T, N>
- Defined in BinaryTree.ts:20

Accessors

size

get size(): number
Returns number
- Defined in BinaryTree.ts:130

Methods

`Abstract`insert

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

`Abstract`delete

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

has

has(value: T): boolean
Проверяет, есть ли значение в дереве.
Parameters
- value: T
Returns boolean
- Defined in BinaryTree.ts:31

get

get(value: T): T | undefined
Возвращает хранящийся в дереве элемент, равный value по компаратору. Полезно, когда компаратор сравнивает только часть объекта (например, ключ).
Parameters
- value: T
Returns T | undefined
- Defined in BinaryTree.ts:39

min

min(): T | undefined
Наименьшее значение.

Returns T | undefined
- Defined in BinaryTree.ts:44

max

max(): T | undefined
Наибольшее значение.

Returns T | undefined
- Defined in BinaryTree.ts:51

floor

floor(value: T): T | undefined
Наибольшее значение, не превышающее value.
Parameters
- value: T
Returns T | undefined
- Defined in BinaryTree.ts:58

ceil

ceil(value: T): T | undefined
Наименьшее значение, не меньшее value.
Parameters
- value: T
Returns T | undefined
- Defined in BinaryTree.ts:74

lower

lower(value: T): T | undefined
Наибольшее значение, строго меньшее value (предыдущий элемент).
Parameters
- value: T
Returns T | undefined
- Defined in BinaryTree.ts:90

higher

higher(value: T): T | undefined
Наименьшее значение, строго большее value (следующий элемент).
Parameters
- value: T
Returns T | undefined
- Defined in BinaryTree.ts:105

range

range(low: T, high: T): IterableIterator<T>
Значения из отрезка [low, high] в порядке возрастания. Посещает только нужные поддеревья.
Parameters
- low: T
- high: T
Returns IterableIterator<T>
- Defined in BinaryTree.ts:120

height

height(): number
Высота дерева (пустое дерево — 0).

Returns number
- Defined in BinaryTree.ts:125

isEmpty

isEmpty(): boolean
Returns boolean
- Defined in BinaryTree.ts:134

clear

clear(): void
Returns void
- Defined in BinaryTree.ts:138

inOrder

inOrder(): IterableIterator<T>
Симметричный обход (в отсортированном порядке).

Returns IterableIterator<T>
- Defined in BinaryTree.ts:144

preOrder

preOrder(): IterableIterator<T>
Прямой обход: корень, левое поддерево, правое поддерево.

Returns IterableIterator<T>
- Defined in BinaryTree.ts:159

postOrder

postOrder(): IterableIterator<T>
Обратный обход: левое поддерево, правое поддерево, корень.

Returns IterableIterator<T>
- Defined in BinaryTree.ts:170

levelOrder

levelOrder(): IterableIterator<T>
Обход в ширину (по уровням).

Returns IterableIterator<T>
- Defined in BinaryTree.ts:183

toArray

toArray(): T[]
Все значения в отсортированном порядке.

Returns T[]
- Defined in BinaryTree.ts:195

[iterator]

"[iterator]"(): IterableIterator<T>
Итерация в отсортированном порядке.

Returns IterableIterator<T>
Implementation of Iterable.[iterator]
- Defined in BinaryTree.ts:200