Конспект установочных лекций по комплексному курсу Информатика, Теория информации


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-деревьях число вершин растет также экспоненциально с высотой дерева.




Начало  Назад  Вперед