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