Конспект установочных лекций по комплексному курсу Информатика, Теория информации
AVL-деревья
Отсортированное двоичное дерево есть двоичное дерево типа tree m, в котором все вершины в левом поддереве не больше, а в правом поддереве не меньше корня и все поддеревья также отсортированы. Тогда обход дерева в порядке следования вершин (левое поддерево, корень, правое поддерево) дает упорядоченную последовательность. Логическая функция проверяющая отсортированность двоичного дерева, имеет вид:
fct sortiert= (tree m t) bool:
if isempty(t) then true
else sortiert(left(t))Ù
sortiert(right(t))Ù
allnodes(left(t), (m x) bool: x£root(t))Ù
allnodes(right(t), (m x) bool: root(t)£x)
fi
При этом вызов allnodes(t, p) предписания allnodes проверяет, все ли вершины в дереве t выполняют предикат p.
fct allnodes= (tree m t, fct(m) bool p) bool:
if isempty(t) then true
else allnodes(left(t), p)Ù
allnodes(right(t), p)Ù
p(root(t))
fi
AVL-дерево
есть отсортированное двоичное дерево, в котором во всех его поддеревьях высоты левого и правого поддеревьев отличаются не более, чем на единицу. Такое дерево называется также сбалансированным. Булевское предписание, проверяющее сбалансированность дерева, имеет вид:
fct isbal=(tree m t) bool:
if isempty(t) then true
else isbal(left(t)Ùisbal(right(t))Ù
·
1£hi(left(t))-hi(right(t))£1
fi
AVL-деревья являются компромиссом между полными и произвольными деревьями. AVL-дерево b высоты hi(b) содержит по меньшей мере 2(hi(b)/3)-2 вершин. Это можно показать индукцией по высоте деревьев. В AVL-деревьях число вершин растет также экспоненциально с высотой дерева.
