Удаление из дерева бинарного поиска

 

При удалении необходимо рассмотреть три случая [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;

…

 

 

Хеширование

 

Мы рассматривали методы поиска. Очевидно, что эффективными из них являются те, которые минимизируют число сравнений ключей друг с другом. В идеале желательно иметь такую организацию таблиц, при которой не было бы ненужных сравнений.

Рассмотрим возможность такой организации. Если каждый ключ должен быть извлечен за один доступ, то положение записи внутри такой таблицы может зависеть только от данного ключа. Оно не может зависеть от расположения других ключей, как это имеет место в дереве [3].

Наиболее эффективным способом организации такой таблицы является массив, где каждая запись хранится по некоторому конкретному смещению по отношению к базовому адресу таблицы. Если ключи записей являются целыми числами, то сами ключи могут использоваться как индексы в массиве. До трех цифр ключа такой подход применим, но если ключ должен состоять из 7 цифр. Как быть в этом случае? Необходим некоторый метод преобразования ключа в какое-либо целое число внутри ограниченного диапазона. В идеале в одно и то же число не должны преобразовываться два различных ключа. К сожалению, такого идеального метода не существует.

Рассмотрим подходы, которые приближаются к идеальному. Вернемся к задаче поиска по ключу, состоящему из 7 цифр. Если использовать массив для записей, то в качестве индекса записи в этом массиве попробуем использовать три последние цифры.

 

Рис. 4.7. Записи, хранящиеся в массиве

 

Такой подход целесообразен, когда в массиве не более 1000 записей. Функция, которая трансформирует ключ в некоторый индекс таблицы, называется хеш-функцией. Если h — хеш-функция, а key — некоторый ключ, то h (key) — значение хеш-функции от ключа key и является индексом, по которому должна быть размещенна запись с ключом key. Если обозначить остаток от деления x на y как mod (x, y), то хеш-функция для вышеприведенного примера есть h (key) = mod (key, 1000). Значения, которые выдает функция h, должны покрывать все множество индексов в таблице.

Этот метод имеет один недостаток. Предположим, что существуют два ключа k 1 и k 2 такие, что h (k 1) = h (k 2). Когда запись с ключом k 1 вводится в таблицу, она вставляется в позицию h (k 1). Но когда хешируется ключ k 2, получаемая позиция является той же позицией, в которой хранится запись с ключом k 1. Ясно, что две записи не могут занимать одну и ту же позицию. Такая ситуация называется коллизией при хешировании или столкновением. В примере, рассмотренном выше, коллизия при хешировании произойдет, если в таблицу будет добавлена запись с ключом 0596396. Далее рассмотрим возможности, как найти выход из такой ситуации. Следует отметить, что хорошей функцией является такая функция, которая минимизирует коллизии и распределяет записи равномерно по всей таблице. Поэтому желательно иметь массив размером больше, чем число реальных записей. Отметим, что определенная хеш – функция используется для заполнения информационной таблицы и по ней же потом идет поиск и, при необходимости, вставка данных.