Исключение вершин из бинарных деревьев
Эта задача является обратной для задачи поиска с включениями. Кроме того, эта задача сложнее. В упорядоченных бинарных деревьях просто исключить терминальную вершину. Но удаление нетерминальной вершины может потребовать восстановления нарушенной упорядоченности в дереве поиска. Рассмотрим, какие случаи возникают при удалении вершины:
вершины с указанным ключом нет. Дерево не изменяется;
вершина с указанным ключом является терминальной, т.е. не имеет потомков. Вершина просто исключается из дерева (рис. 5);
Рисунок 5 – Исключение терминальной вершины
вершина с указанным ключом имеет одного потомка. Эта вершина просто заменяется потомком. Если есть повторяющиеся ключи, то удаленная вершина заменяется правым потомком – это следующее повторение ключа (рис. 6);
Рисунок 6 – Исключение вершины с одним потомком
вершина с указанным ключом имеет двух потомков. Удаляемый элемент нужно заменить или на самый правый элемент его левого поддерева, или на самый левый элемент его правого поддерева. Если есть повторяющиеся ключи, то следующее повторение – это самый левый элемент его правого поддерева. Его удаление позволит по очереди удалить подряд все повторения данного ключа (рис. 7).
Рисунок 7 – Исключение вершины с двумя потомками
Программа удаления из бинарного дерева имеет вид:
atom* delbtree(btree t, key)
{
pos=locate(key,t) //случай 1
if pos is 0 then
return null //определим потомков
if downl(t) is null then
L=0 else {L=1,upb(t)}
if downr(t) is null then
R=0
else {R=1,upb(t)} //случай 2
if L=0 & R=0 then
{
t.clip=t.current,
tcut(t),
t.size--,
return t.clip
} //случай 3, левый потомок
if L=1 & R=0 then
{
t.clip=t.current //запомнить удаляемый
atom *b=t.clip->down->down //ссылка вниз
pos=t.clip->down->item->pos // позиция
tcut(t),
t.size--,
insertl(t,t.clip->down),
t.size—-,
t.current->down=b //восстановить ссылку вниз
t.current->item->pos=pos //восстановить позицию
} //свести случай 4 с повторением к случаю 3 правому
if L=1 & R=1 then
{
if downr(t)->item->key eq key then
L=0
} //случай 3, правый потомок
if L=0 & R=1 then
{
t.clip=t.current
atom *b=t.clip->down->down
pos=t.clip->down->item->pos
tcut(t),
t.size--,
insertr(t,t.clip->down),
t.size—
t.current->down=b
t.current->item->pos=pos
} //случай 4 два потомка
if L=1 & R=1 then
{
t.clip=t.current //запомнить удаляемый
downr(t) //правое поддерево
while (downl(t) not null)
continue //проход вниз
atom *left=t.current tcut(t) //удалить самый левый в правом поддереве
while (upb(t) not t.clip)
continue //в удаляемый
LR=t.current->item->LR //левый или правый
tadd(t,left),
tprev(t),
tcut(t) //заменить
t.current->item->LR=LR //сделать потомком
t.current->down=t.clip->down //ссылка вниз
t.current->down->up=t.current //ссылка вверх
t.current->down->next->up=t.current//ссылка вверх
t.size—
}
return t.clip
}
Замечания о процедуре удаления. Процедуры построения бинарного упорядоченного дерева search() и sortbtree() увеличивают размер дерева с помощью операций insertl() и insertr(). Позиция каждого элемента исходного множества сохраняется в самом элементе дерева в его поле pos. Вообще говоря, этого можно было и не делать, а хранить только значение ключа (поле key). Сохраняя поле pos, мы полагаем, что оно имеет смысл индекса, по которому, например, нужно обращаться к соответствующей записи в БД, если рассматривать множество элементов как множество записей БД. Тогда при обходе полученного дерева поиска, например, слева направо, будут выбраны соответствующие записи в порядке возрастания их ключевых полей. Удаление элемента означает не только уменьшение размера дерева, но и уменьшение на единицу позиций всех элементов множества после уда- ленного элемента, если он реально исключается из множества. Но тогда нужно найти все эти элементы и уменьшить на единицу значение их позиции в поле pos. Это можно сделать специальной процедурой, в которой при просмотре дерева модифицируются соответствующие поля у всех элементов, значение в поле pos у которых превышает значение позиции удаленного поля. Такая процедура должна выполняться после каждого обращения к delbtree(), если необходимо попеременно добавлять элементы при помощи search() и удалять при помощи delbtree(). С другой стороны, обычно в БД при удалении записей их только помечают как удаленные. Тогда в дереве типа btree нужно хранить два раз- мера: size – размер дерева и size-dbase – число записей в БД. Операции insertl() и insertr() должны увеличивать size и size-dbase и запоминать в поле pos нового элемента size-dbase вместо size. Операция delbtree() должна уменьшать только значение size. Тогда после реорганизации БД, когда из нее физически удаляются записи, помеченные ранее как удаленные, необходимо применить дополнительную процедуру реорганизации и к дереву. Например, она может состоять из процедуры полного удаления дерева и создания его заново по реорганизованной БД.