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

При сопровождении динамического набора данных может потребоваться встав­лять новые элементы в этот набор, а также удалять из него некоторые ненужные элементы. Поэтому для набора данных, 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(Leftl_r 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 (к узлу А), поскольку узел А способен присоединить к себе только одно из них.