Программирование на языке Пролог для искусственного интеллекта

       

Задача вставления



Рисунок 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 может иметь



Содержание раздела