Вставка и удаление в бинарном словаре

При сопровождении динамического набора данных может потребоваться встав­лять новые элементы в этот набор, а также удалять из него некоторые ненужные элементы. Поэтому для набора данных, S, может быть предусмотрен следующий обычный перечень операций.

• in ( X, S). Проверка принадлежности элемента X к набору данных S.


Глава 9, Операции со структурами данных



Добавление элемента '" к набору данных S и получение на-
Удаление элемента X из набора данных S и получение набо-

• add ( S, X, SI). бора данных S1.

• del( S, X, SI). ра данных 31.

Определим отношение add.Проще всего вставлять новые данные на нижнем уровне дерева, чтобы новый элемент становился листом дерева в такой позиции, в которой сохраняется упорядочение этого дерева. На рис. 9.6 показано, какие измене­ния происходят в дереве при выполнении ряда операций вставки. Определим опера­цию вставки такого рода как addleaf ( D, X, Dl>.





 


Рис, 9.6. Пример применения операций вставки в би­нарный словарь на уровне листа; эти деревья соот­ветствуют такой последовательности операций вставки: addf Dl, 6, D2>, addf D2, 7, D3), addt 03, 4, D4)

Правила вставки на уровне листа состоят в следующем.

• Результатом вставки элемента X в пустое дерево является дерево t ( nil, X, nil).

• Если X — корень D, то DI = D (вставка дубликатов элементов не выполняется).

• Если корень D больше X, то вставить X в левое поддерево D; если кореньD

меньше X, то вставить X в правое поддерево.

Соответствующая программа приведена в листинге 9.4.

Листинг 9.4. Вставка элемента в бинарный словарь в качестве листа

% addleaf [ Tree, X, NewTree) :

вка элемента X в качестве листа в бикаркк:": словарь Tree% и получение словаря NewTree

addleaft nil, X, t( nil, X, nil)).

addleaf! t( Left, X, Right), X, t( Left, X, Right)).



Часть I. Язык Prolog


addleaft t( Left, Boot, Right), X, t( Leftlr Root, Right)) :-gt Root, X), addleaft Left, X, Leftl) .

addleafl t( Left, Root, Right), X, t (, Left, Root, Rightl)) :-gt ( X, Root) , addleaft Right, У, Rightl) .

Теперь рассмотрим операцию удаления. Задача удаления листа является простой, но обеспечить удаление внутреннего узла гораздо сложнее. Операцию удаления листа можно фактически определить как обратную по отношению к операции вставки на уровне листа, как показано ниже.

delleaf{ D1, X, D2) :-addleaf ( D2, >:, Dl) .

К сожалению, если X — внутренний узел, то эта операция не может применяться в связи с возникновением проблемы, проиллюстрированной на рис. 9.7. Здесь X име­ет два поддерева. Left и Right. После удаления X в дереве появится пустое место и поддеревья Left и Right больше не будут соединены с остальной частью дерева. Эти поддеревья нельзя также непосредственно присоединить к родительскому узлу узла X (к узлу А), поскольку узел А способен присоединить к себе только одно из них.