Программирование на языке Пролог для искусственного интеллекта
Шрифт:
(a)
10.2. AVL-дерево: приближенно сбалансированное дерево
AVL-дерево — это дерево, обладающее следующими свойствами:
(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.
(2) Оба поддерева являются AVL-деревьями.
Деревья, удовлетворяющие этому определению, могут быть слегка разбалансированными. Однако можно показать, что даже в худшем случае глубина AVL-дерева примерно пропорциональна log n, где n — число вершин дерева. Таким образом гарантируется логарифмический порядок производительности операций
Операции над AVL-деревом работают по существу так же, как и над двоичным справочником. В них только сделаны добавления, связанные с поддержанием приближенной сбалансированности дерева. Если после вставления или удаления дерево перестает быть приближенно сбалансированным, то специальные механизмы возвращают ему требуемую степень сбалансированности. Для того, чтобы эффективно реализовать этот механизм, нам придется сохранять некоторую дополнительную информацию относительно степени сбалансированности дерева. На самом деле, нам нужно знать только разность между глубинами поддеревьев, которая может принимать значения -1, 0 или +1. Тем не менее для простоты мы предпочтем сохранять сами величины глубин поддеревьев, а не разности между ними.
Мы определим отношение вставления элемента как
где оба дерева
где
Рис. 10.8. Задача вставления элемента в AVL-справочник (a) AVL-дерево перед вставлением X, X > А; (b) AVL-дерево после вставления X в R; (с) составные части, из которых следует построить новое дерево.
Начнем со случая, когда X больше А. X необходимо вставить в R, поэтому имеем следующее отношение:
На рис. 10.8 показаны составные части, из которых строится дерево
Какова глубина деревьев L, R, R1 и R2? L и R могут отличаться по глубине не более, чем на 1. На рис. 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь глубину h+1.
Рис. 10.9. Три правила построения нового AVL-дepевa.
В случае, когда X меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево
Рассмотрим три случая:
(1) Среднее дерево
(2)
(3)
На рис. 10.9 видно, как можно построить дерево
Последний аргумент