8.1. Сбалансированные АВЛ-деревья поиска
 

Требования к сбалансированности в АВЛ - деревьях менее жесткие, чем в идеально сбалансированных деревьях. АВЛ - деревом называется такое дерево, у которого высота поддеревьев для каждой вершины различается не более чем на 1. Максимальная высота АВЛ -дерева с n вершинами не превосходит 1,44*log₂(n+ 1) - 1,33, т. е. затраты на поиск не превосходят l,45*O(log₂n).

Отличие АВЛ -деревьев от обычных деревьев поиска заключается в том, что при включении и удалении элементов необходимо поддерживать сбалансированность дерева в целом. Для этого в каждый узел дерева добавляется одно вспомогательное поле, содержащее информацию о равновесности поддеревьев (показатель сбалансированности узла). Его значениями могут быть: 0 - высоты правого и левого поддеревьев равны; + 1 — высота правого поддерева больше; - 1 — высота правого поддерева меньше.

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