Поиск по дереву с включениями
Очевидно, что дерево поиска, показанное на рис. 1 для множества A, необходимо сначала построить некоторым способом. Выше мы ограничились лишь словесным описанием способа построения. На практике обычно требуется найти элемент, используя дерево поиска, а если его нет – то добавить элемент. В целом, процедура поиска с включениями является процедурой сортировки неупорядоченного множества в ссылочной реализации. Легко увидеть, что обход дерева поиска на рис. 1 слева направо обеспечивает выборку элементов множества в порядке возрастания их ключей. Сейчас наступил момент, когда необходимо специально построить такой объект.
Бинарное дерево
Будем считать, что в элементе item хранится структура следующего вида:
{key, pos, LR},
где key – значение ключа, pos – позиция элемента, поле LR содержит значение L для левой вершины или R для правой вершины.
Текущее состояние бинарного дерева представим структурой
btree{tree{...}, size},
где size определяет число элементов множества, т.е. число вершин дерева. Определим специфические операции для бинарного дерева:
создать бинарное дерево (newbtree);
сдвинуться вверх (upb);
сдвинуться в корень (rootb);
сдвинуться вниз-влево (downl);
сдвинуться вниз-вправо (downr);
вставить элемент слева (insertl);
вставить элемент справа (insertr);
Создать бинарное дерево:
newbtree(btree t){tcreate(t),t.size=0}
Сдвинуться вверх:
atom* upb(btree t){return up(t)}
Сдвинуться в корень:
atom* rootb(btree t){return root(t)}
При движении вниз возникают четыре случая: в поддереве есть две вершины, только левая, только правая, нет ни одной (рис. 3). В первом случае можно сдвинуться вниз в обоих направлениях, во втором – только влево, в третьем – только вправо, в четвертом – вниз сдвинуться нельзя.
Рисунок 3 – Случаи движения вниз
Сдвинуться вниз-влево:
atom* downl(btree t)
{
if down(t) is null then
return null
else if t.current->item->LR is L then
return t.current else up(t)
return null
}
В функциях вставки предполагается, что правильная последовательность добавления вершин в дерево определяется алгоритмом поиска с включениями. Поэтому случаи 1–4 (рис. 3) не проверяются. Если следующего уровня еще нет, то функция addbranch() создаст его и возвратит ненулевой указатель.
Вставить элемент слева:
insertl(btree t, atom* a)
{
if addbranch(t,a) eq 0 then
{
down(t),taddhead(t,a)
}
t.size++, a->item->pos=t.size, a->item->LR=L
}
Вставить элемент справа:
insertr(btree t, atom* a)
{
if addbranch(t,a) eq 0 then
{
down(t),tadd(t,a)
}
t.size++, a->item->pos=t.size, a->item->LR=R
}
Поиск с однократными включениями. Программа имеет следующий вид:
pos search(key, btree t)
{
atom *a
if t.root is null then //вставка в пустое дерево
{
a=new atom, a->item=new type{key,pos,LR }
*(a->item)={key,0,0}
insertl(t,a)
return t.size
}
rootb(t) if key eq t.current->item->key then
return t.current->item->pos //элемент найден
while (t.current->down not null) //спуск вниз
{
if key < t.current->item->key then
{
if downl(t) is null then break
} //нет спуска
else if key > t.current->item->key then
{
if downr(t) is null then break
} //нет спуска
if key eq t.current->item->key then
return t.current->item->pos //элемент найден
}
//элемент не найден, его надо добавить в дерево
a=new atom, a->item=new type{key,pos,LR}
*(a->item)={key,0,0}
if key < t.current->item->key then
insertl(t,a)
else if key > t.current->item->key then
insertr(t,a) return t.size
}
Данная программа последовательно достраивает дерево поиска при добавлении в него новых элементов. После того, как дерево поиска построено, с его помощью можно выполнять поиск элементов множества. При построении такого дерева фактически выполняется сортировка элементов множества. Упорядоченная выборка элементов выполняется при обходе дерева слева направо. Но эта программа не является полноценной программой сортировки при повторяющихся значениях элементов. Поиск с включением повторяющихся элементов. В этом случае необходимо предусмотреть добавление в дерево поиска повторяющихся элементов путем достраивания правого поддерева. Основная трудность состоит в том, что повторяющийся элемент уже не является терминальной вершиной дерева поиска. Программа сортировки имеет следующий вид:
sortbtree(btree t, s(n))
{
for(newpos=1,n,step=1) //перебор массива
{
pos=search(s[newpos-1],t)
if pos not newpos then //найден повторный эл-т
{
key=s[newpos-1]
if downr(t) is null then //нет правого дерева
insertr(t,a)
else //есть правое дерево
{
while (downr(t) not null) //1.проход вниз
{
if t.current->item->key not key then break
}
t.clip=t.current //2.запомнить в буфере
a=new atom, a->item=new type{key,pos,LR}
*(a->item)={key,newpos,R} //повторный эл-т
tadd(t,a) //3.добавить в хвост
tprev(t), tcut(t) //4.удалить предыдущий
atom *b=t.clip->down//сохранить ссылку вниз
insertr(t,t.clip) //5.вставить из буфера
t.current->down=b //восст-ть ссылку вниз
}
}
}
}
На рис. 4 показан пример действий, выполняемых данной программой при вставке повторного элемента со значением 11, который является шестым в последовательности: 11, 10, 15, 19, 13, 11. Номера шагов соответствуют цифрам в комментариях программы.
Рисунок 4 – Вставка повторного элемента в дерево поиска
Из рис. 4 легко увидеть, что программа работает правильно, но не совсем корректно. Как уже говорилось ранее, желательно при изменении объекта так выполнять операции, чтобы на каждом шаге объект оставался в корректном состоянии. Здесь видно, что после вставки на шаге 3 бинарное дерево перестает быть бинарным. Эта некорректность была допущена лишь из желания не усложнять текст программы.