сохранять некоторую дополнительную информацию относительно степени сбалансированности дерева. На самом деле, нам нужно знать только разность между глубинами поддеревьев, которая может принимать значения -1, 0 или +1. Тем не менее для простоты мы предпочтем сохранять сами величины глубин поддеревьев, а не разности между ними.
Мы определим отношение вставления элемента как
доб_avl( Дер, X, НовДер)
где оба дерева Дер и НовДер - это AVL-деревья, причем НовДер получено из Дер вставлением элемента X. AVL-деревья будем представлять как термы вида
д( Лев, А, Прав)/Глуб
где А - корень, Лев и Прав - поддеревья, а Глуб -
Рис. 10. 8. Задача вставления элемента в AVL-справочник
(a) AVL-дерево перед вставлением Х, Х > А;
(b) AVL-дерево после вставления Х в R;
(с) составные части, из которых следует построить новое дерево.
глубина дерева. Пустое дерево изображается как nil/0. Теперь рассмотрим вставление элемента Х в непустой AVL-справочник
Дер = д( L, A, R)/H
Начнем со случая, когда Х больше А. Х необходимо вставить в R, поэтому имеем следующее отношение:
доб_аv1( R, X, д( R1, В, R2)/Hb)
На рис. 10.8 показаны составные части, из которых строится дерево НовДер:
L, А, R1, В, R2
Какова глубина деревьев L, R, R1 и R2? L и R могут отличаться по глубине не более, чем на 1. На рис. 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь
Рис. 10. 9. Три правила построения нового AVL-дepевa.
глубину h +1.
В случае, когда Х меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево НовДер, используя три дерева (назовем их Дер1, Дер2 и Дер3) и два отдельных элемента А и В. Теперь рассмотрим вопрос: как соединить между собой эти пять составных частей, чтобы дерево НовДер было AVL-справочником? Ясно, что они должны располагаться внутри НовДер в следующем порядке (слева направо):
Дер1, А, Дер2, В, Дер3
Рассмотрим три случая:
(1) Среднее дерево Дер2 глубже остальных двух деревьев.
(2) Дер1 имеет глубину не меньше, чем Дер2 и Дер3.
(3) Дер3 имеет глубину не меньше, чем Дер2 и Дер1.
На рис. 10.9 видно, как можно построить дерево НовДер в каждом из этих трех случаев. Например, в случае 1 среднее дерево Дер2 следует разбить на два части, а затем включить их в состав НовДер. Три правила, показанные на pис.10.9, нетрудно запасать на Прологе в виде отношения
соединить( Дер, А, Дер2, В, Дер3, НовДер)
Последний аргумент НовДер - это AVL-дерево, построенное из пяти составных частей, пяти первых аргументов. Правило 1, например, принимает вид:
