Вставка в дерево бинарного поиска
Рассмотрим алгоритм организации поиска по некоторому бинарному дереву со вставкой новых записей в такое дерево, если поиск неудачен.
{часть программы}
class item
{
public:
char name;
int k;
item * left; // указатели
item *right;
item(char, item *, item *, int ); // конструктор
~item(); // деструктор
};
class tree
{
public:
tree * g; // указатель на начало прохода дерева
};
…
void main()
{
tree *p= new tree;; // создается объект - дерево
int search=0; // 1 — признак нахождения ключа
item *l,r; // указатели левого и правого полей
item *q,p;
…
q= NULL; // q — указатель на отца, если он существует
p=g; // g — указатель на начало прохождения дерева
while( p!=NULL)
{
if (key==p->k) search=1;
else
{
q:=p;
if( key<p->k ) p=p->left;
else p=p->right;
}
}
if (search==1)
{
cout<<”ключ найден\n”;
return;
}
else
{
сout<<”ключ не найден\n”;
// вставка информации с ключом
item *v=new item(rec,l,r,key);
v->name=rec; // rec - запись
v->k=key;
if (q==nil) // дерево было пусто изначально
*tree==v;
else // дерево не было пусто
{
if( key<q->k)
{
v->left=q->left;
q->left=v;
}
else
{
v->right=q->right;
q->right=v;
}
}
}
…
Отметим, что после того, как будет вставлена некоторая новая запись, данное дерево сохранит то свойство, что при прохождении его в симметричном порядке получится отсортированный массив.
Удаление из дерева бинарного поиска
При удалении необходимо рассмотреть три случая [3]:
1. Если удаляемый узел не имеет сыновей, то он удаляется без дальнейшей настройки дерева (рис. 4.6 (а)).
2. Если удаляемый узел имеет только одно поддерево, то его единственный сын может быть помещен вверх, чтобы занять его место (рис. 7.6 (б)).
3. Если удаляемый узел p имеет два поддерева, то его приемник s в симметричном порядке (или его предшественник в симметричном порядке) должен занять его место. Потомок в симметричном порядке не может иметь левого поддерева (поскольку, если бы он имел его, левый потомок был бы приемником p в симметричном порядке). Таким образом, правый сын элемента s может быть перемещен вверх, чтобы занять место s (рис. 4.6 (в)).
Рис. 4.6. Удаление узлов из дерева бинарного поиска
а — удаление узла с ключом 15;
б — удаление узла с ключом 5;
в — удаление узла с ключом 11
В приводимом ниже алгоритме дерево остается неизменным, если в нем не существует узла с ключом key.
…
p=tree;
q=NULL;
// Поиск узла с ключом key. Установить p так, чтобы оно указывало
// на данный узел, а q — на его отца, если он существует
while( (p!=NULL) && (p->k!=key))
{
q=p;
if( key<p->k) p=p->left;
else p=p->right;
}
if (p==NULL)
{
cout<<”такого ключа нет в дереве. Дерево остается не измененным \n”;
return;
}
// Установить в переменную v узел, который заменит p.
// Удаляемый узел имеет максимум одного сына
if (p->left==NULL) v=p->right;
else (if p->right==NULL) v=p->left;
else // узел p имеет двух сыновей
// Установить в v преемника p в симметричном порядке,
// а в переменную t — отца переменной v
t=p;
v=p->right;
s=v->left; // s — левый сын v
while (s!=NULL)
{
t=v;
v=s;
s=v->left;
}
// В этот момент переменная v является преемником узла p
// в симметричном порядке
if (t!=p)
// p является отцом переменной v, и v=t->left.
// Удалить узел v из его текущей позиции и заменить его на правого сына узла v
t->left=v->right;
// настроить сыновей v так, чтобы они были сыновьями p
v->right=p->right;
v->left=p->left;
// вставить узел v в позицию, которую ранее занимал узел p
if (q==NULL) // узел p был корнем дерева
tree=v;
else if( p==q->left) q->left=v;
else q->right=v;
delete v;
…