Поиск
Для поиска элемента используется компонентная функция 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
|