Подразделы

Другие разделы

Дата и время

01/04/2025 00:33:00

Авторизация

Структуры данных на основе деревьев

Определения Обходы бинарного дерева Двоичное дерево поиска Система непересекающихся множеств Сбалансированные деревья Декартово дерево Декартово дерево по неявному ключу Дерево отрезков

Сбалансированные деревья

Бинарное дерево поиска (BST) называется практически сбалансированным (almost balanced), если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу. Высота такого дерева равна $h=|__ log_2(n)+1 __|$ . Идеально сбалансированным деревом будет только дерево, содержащее $2^h-1$ вершин.

Обеспечение сбалансированности является сложной задачей, поэтому на практике используют более слабые критерии.

АВЛ-дерево — сбалансированное бинарное дерево поиска, в котором поддерживается следующее свойство: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

Максимальная высота АВЛ-дерева

$h <= |__ 1.45*log_2(n+2) __|$

В каждом узле АВЛ-дерева мы храним высоту поддерева или разность в высоте (0,1,-1) и при нарушении разницы высот выполняем балансировку за $O(1)$ .

Добавление: поиск места вставки нового узла $O(h)$ , а при обратном проходе балансировка не более, чем $O(h)$ раз.

width:800px|добавление

Удаление: аналогично.

width:800px|удаление

Красно-чёрным называется бинарное дерево поиска, у которого каждому узлу сопоставлен дополнительный атрибут — цвет и для которого выполняются следующие свойства:

Каждый узел промаркирован красным или чёрным цветом
Корень и конечные узлы (листья) дерева — чёрные (листья, не содержащие данных — чёрные)
У красного узла родительский узел — чёрный, у чёрного узла - любого цвета
Все простые пути из любого узла $x$ до листьев содержат одинаковое количество чёрных узлов (чёрная высота)

Максимальная высота красно-чёрного дерева

$h <= 2*log_2(n)+1$

Расширяющееся дерево (Splay-tree) — это двоичное дерево поиска, которое позволяет находить быстрее те данные, которые использовались недавно. Для этого узлы дерева переупорядочиваются таким образом, чтобы узел с искомым или добавляемым ключом стал корнем дерева.

Википедия Ссылка 2