Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Словари для произвольных данных / Двоичные деревья /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Cвязанные двоичные деревья поиска - Программирование от RIN.RU
Cвязанные двоичные деревья поиска



Поиск


Для поиска элемента используется компонентная функция find. Эта функция аналогична функции SearchTree::find за исключением того, что она начинает свой поиск с root->rchild(), фактического корня. Если элемент найден, то окно устанавливается на этом элементе.


template Т BraidedSearchTree::find (T val)
{
BraidedNode *n = root->rchild();
while (n) {
int result = (*cmp) (val, n->val);
if (result < 0)
n = n->lchild();
else if (result > 0)
n = n->rchild();
else {
win=n;
return n->val;
}
}
return NULL;
}


Наименьший элемент в связанном дереве поиска располагается в первой позиции ленты. Компонентная функция findMin перемещает окно на этот наименьший элемент и возвращает указатель на элемент. Если дерево поиска пусто, то возвращается NULL :


template Т BraidedSearchTree::findMin (void)
{
win = root->next ();
return win->val;
}




Включение элементов


Новый элемент должен быть внесен в его правильной позиции как в дерево поиска, так и в ленту. Если новый элемент становится левым потомком, то тем самым он становится предшественником предка в ленте. Если элемент становится правым потомком, то он становится последователем предка в ленте. Реализация функции insert одинакова с функцией SearchTree: : insert за исключением дополнительного включения нового узла в ленту. Однако следует заметить, что в функции insert нет необходимости проверки включения в пустое дерево, поскольку головной узел присутствует всегда. Функция располагает окно над только что внесенным элементом и возвращает указатель нa элемент, если включение произошло успешно.


template T BraidedSearchTree::insert(T val)
{
int result = 1;
BraidedNode *p = root;
BraidedNcde *n = root->rchild();
while (n) {
p = n;
result = (*cmp) (val, p->val);
if (result < 0)
n = p->lchild();
else if (result > 0)
n = p->rchild();
else
return NULL;
}
win = new BraidedNode(val);
if (result < 0) {
p->_lchild = win;
p->prev()->Node::insert(win);
} else {
p->_rchild = win;
p->Node::insert(win);
}
return val;
}




Удаление элементов


Компонентная функция remove удаляет элемент, находящийся в окне и перемещает окно в предыдущую позицию:


template void BraidedSearchTree::remove(void)
{
if (win != root)
remove(win->val, root->_rchild);
}


Элемент val, подлежащий удалению, и указатель n на корень дерева поиска, в котором находится этот элемент, передаются в качестве параметров собственной функции _remove. Эта функция работает подобно своему аналогу с тем же именем в классе SearchTree. Однако при работе со связанным деревом поиска элемент, конечно, должен быть удален как из дерева поиска, так и из ленты:


template
void BraidedSearchTree::remove(T val, TreeNode* &n)
{
int result = (*cmp) (val, n->val);
if (result < 0)
_remove(val, n->_lchild);
else if (result > 0)
_remove(val, n->_rchild);
else { // случай 1
if (n->_lchild == NULL) {
BraidedNode *old = (BraidedNode*)n;
if (win == old)
win = old->prev();
n = old->rchild();
old->Node::remove();
delete old;
}
else if (n->_rchild == NULL) { // случай 2
BraidedNode *old = (BraidedNode*)n;
if (win == old)
win = old->prev();
n = old->lchild();
old->Node::remove();
delete old;
}
else { // случай 3
BraidedNode *m = ( (BraidedNode*)n)->next();
n->val = m->val;
_remove(m->val, n->_rchild);
}
}
}


Заметим, что функция _remove использует ленту для поиска последователя узла n в случае 3, когда подлежащий удалению узел имеет два непустых потомка. Отметим также, что параметр n является ссылкой на тип TreeNode*, а не на тип BraidedNode*. Это происходит потому, что n указывает на ссылку, хранящуюся в предке узла, подлежащего удалению, а эта ссылка имеет тип TreeNode*. Если бы вместо этого параметру n был присвоен тип BraidedNode*, то это была бы ошибочная ссылка на анонимный объект. При этом поле ссылки в узле предка было бы недоступно.


Компонентная функция removeMin удаляет из дерева наименьший элемент и возвращает указатель на него, функция возвращает значение NULL, если дерево пусто. Если окно содержало удаляемый наименьший элемент, то окно перемещается в головную позицию, в ином случае оно остается без изменения:


template T BraidedSearchTree::removeMin(void)
{
Т val = root->next()->val;
if (root != root->next() )
_remove(val, root->_rchild);
return val;
}


<<<  Назад
 1  2  3 


 8  Комментарии к статье  8 8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь