Сбалансированные деревья (AVL-деревья)

В двоичных упорядоченных деревьях время поиска равно (пропорционально) глубине дерева. Структура и глубина дерева зависит от порядка следования ключей при добавлении.

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

Идеально сбалансированным деревом является дерево, в каждой вершине которого число вершин левого поддерева и правого поддерева различаются не более чем на 1.

Сбалансированное дерево – это дерево, в каждой вершине которого глубина правого поддерева и глубина левого поддерева различаются не более чем на 1.

Идеально сбалансированное дерево всегда сбалансировано.

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

В процессе использования дерева операции поиска в дереве и добавления в дерево выполняются вперемешку. Поэтому для эффективной работы с деревом необходимо поддерживать его баланс при добавлении вершины.

При добавлении вершины дерево может остаться сбалансированным или возникнет дисбаланс. Для устранения дисбаланса существуют четыре схемы балансировки дерева, которые приводят к его балансу. Эти схемы называются поворотами.

LL – поворот (левый-левый);

LR – поворот (левый-правый);

RR – поворот (правый-правый);

RL – поворот (правый-левый).

Дата добавления: 2014-01-15