Вставление нового элемента в 2-3 справочник. Дерево
Вставление нового элемента в 2-3 справочник. Дерево
растет сначала вширь, а затем уже вглубь.
Включение нового элемента в 2-3 справочник мы запрограммируем как отношение
доб23( Дер, X, НовДер)
где дерево НовДер получено введением элемента Х в дерево Дер. Основную работу мы поручим двум дополнительным отношениям, которые мы назовем встав. Первое из них имеет три аргумента:
встав( Дер, X, НовДер).
Здесь НовДер - результат вставления элемента Х в Дер. Деревья Дер и НовДер имеют одну и ту же глубину. Разумеется, не всегда возможно сохранить ту же глубину дерева. Поэтому существует еще одно отношение с пятью аргументами специально для этого случая:
встав( Дер, X, НДа, Mб, НДб).
Имеется в виду, что при вставления Х в Дер дерево Дер разбивается на два дерева НДа и НДб, имеющих ту же глубину, что и Дер. Мб - это минимальный элемент из НДб. Пример показан на рис. 10.4.