Основные определения

Бинарные деревья поиска предназначены для быстрого доступа к данным. В идеале дерево является разумно сбалансированным и имеет высоту порядка . Однако при некоторых данных дерево может быть вырожденным. Тогда его высота будет O (n), и доступ к данным существенно замедлится.

Дерево является сбалансированным тогда, и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1 (не путать с идеально сбалансированными деревьями, когда для каждого узла дерева количество узлов в левом и правом поддеревьях отличается не более чем на 1).

Сбалансированные деревья еще называют AVL -деревьями (по фамилиям изобретателей: Адельсон-Вельский, Ландис).

Бинарное дерево поиска

AVL -дерево

3.5.2. Узлы AVL -дерева

AVL -деревья имеют представление, похожее на бинарные деревья поиска. Все операции идентичны, за исключением операций вставки и удаления из дерева.

Для сохранения информации об соотношении высот левого и правого поддеревьев в определение типа узла включается поле - показатель сбалансированности, которое содержит разность высот правого и левого поддеревьев:

struct AVLTREE{
int dann;
int balance;
TREE *pleft;
TREE *pright; };

Если balance ==-1, то узел «перевешивает влево», т.к. высота левого поддерева больше, чем высота правого поддерева. При положительном balance узел «перевешивает вправо». Сбалансированный по высоте узел имеет balance ==0. В AVL -дереве показатель сбалансированности должен быть в диапазоне [-1, 1].