Подразделы

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

Дата и время

05/01/2026 09:12:05

Авторизация

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

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

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

Бинарное дерево поиска (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|добавление](51478.png)

--

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

![width:800px|удаление](51479.png)

--

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

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

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

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

--

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

[Википедия](https://ru.wikipedia.org/wiki/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE)
[Ссылка 2](https://neerc.ifmo.ru/wiki/index.php?title=Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE)

Если к ключам в сплей-дереве выполняется `m` запросов поиска, из них к `i`-му ключу `k_i>0` запросов, то суммарное время работы не превышает `O(m*H(k_1/m,k_2/m,...,k_n/m))`, где `H` — шенноновская энтропия. Математическое ожидание количества действий для поиска `i`-го ключа равно `3*(log_2 m-log_2 k_i)`.

Назад

Подразделы

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

Дата и время

Авторизация

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

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