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



              

Задача вставления элемента в avl-справочник...



  Задача вставления элемента в 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 может иметь









Содержание  Назад  Вперед