По книге Laszlo "Вычислительная геометрия и компьютерная графика на С++"
Рис. 1: Связанное двоичное дерево поиска с головным узлом. Связи ленты представлены дугами
Для краткости связанное двоичное дерево поиска будем называть связанным деревом поиска, а охватывающий его связный список — лентой.
Связанное дерево поиска реализуем в виде класса BraidedSearchTree. Этот класс отличается от класса SearchTree из описания двоичных деревьев поиска по трем существенным признакам. Во-первых, объекты класса BraidedSearchTree обладают связным списком (лентой), который для каждого узла устанавливает ссылки на предшественника и последователя. Во-вторых, объекты класса BraidedSearchTree поддерживают окно, которое в любой момент времени располагается над каким-либо элементом в дереве. Окно служит той же цели, что и в классе List(используется класс Node из реализации кольцевого списка): существует целый ряд операций с окном или с элементом в окне. В-третьих, элемент root класса BraidedSearchTree указывает на головной узел — "псевдокорневой узел", правый потомок которого является фактическим корнем связанного дерева поиска. Если посмотреть на ленту, то узел, содержащий наименьший элемент в дереве, следует за головным узлом, а узел, содержащий самый большой элемент, предшествует головному узлу. Следовательно, головной узел соответствует головной позиции, которая располагается одновременно перед первой позицией и после последней (рис. 1).
Класс BraidedNode
Узлы связанного дерева поиска являются объектами класса BraidedNode. Поскольку эти узлы действуют одновременно как узлы дерева и как узлы списка, то шаблон класса BraidedNode составим на основе классов TreeNode и Node:
template<class T>
class BraidedNode : public Node, public TreeNode<T> {
public :
BraidedNode (T);
BraidedNode<T> *rchild(void);
BraidedNode<T> *lchild (void);
BraidedNode<T> *next (void);
BraidedNode<T> *prev(void);
friend class BraidedSearchTree<T>;
};
Конструктор класса BraidedNode явно инициализирует базовый класс TreeNode по своему списку инициализации, а базовый класс Node инициализируется неявно, поскольку его конструктор не имеет параметров:
Компонентные функции rchild, lchild, next и prev устанавливают четыре ссылки для текущего узла — первые два для дерева поиска, а последние два — для ленты:
Шаблон класса BraidedSearchTree определяется следующим образом:
template<class T> class BraidedSearchTree {
private:
BraidedNode<T> *root; // головной узел
BraidedNode<T> *win; // текущее окно
int (*cmp) (T,T); // функция сравнения
void _remove(T, TreeNode<T> * &);
public:
BraidedSearchTree (int(*) (T,T) );
~BraidedSearchTree (void);
Т next (void);
Т prev (void);
void inorder (void(*) (T) );
Т val (void);
bool isFirst (void);
bool isLast (void);
bool is Head (void);
bool isEmpty (void);
Т find (T);
Т findMin (void);
T insert (T);
void remove (void);
T removeMin (void);
};
Конструкторы и деструкторы
Конструктор класса BraidedSearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева, представленного в виде изолированного головного узла:
Элемент данных win описывает окно для дерева — т. е. элемент win указывает на узел, над которым располагается окно. Компонентные функции next и prew перемещают окно на следующую или предыдущую позиции. Если окно находится в головной позиции, то функция next перемещает его на первую позицию, а функция prew — на последнюю позицию. Обе функции возвращают ссылку на элемент в новой позиции окна:
Компонентные функции isFirst, isLast и isHead возвращают значение TRUE (истина), если окно находится в первой, последней или головной позициях соответственно.
Для поиска элемента используется компонентная функция find. Эта функция аналогична функции SearchTree::find за исключением того, что она начинает свой поиск с root->rchild(), фактического корня. Если элемент найден, то окно устанавливается на этом элементе.
template<class Т> Т BraidedSearchTree<T>::find (T val)
{
BraidedNode<T> *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 :
Новый элемент должен быть внесен в его правильной позиции как в дерево поиска, так и в ленту. Если новый элемент становится левым потомком, то тем самым он становится предшественником предка в ленте. Если элемент становится правым потомком, то он становится последователем предка в ленте. Реализация функции insert одинакова с функцией SearchTree: : insert за исключением дополнительного включения нового узла в ленту. Однако следует заметить, что в функции insert нет необходимости проверки включения в пустое дерево, поскольку головной узел присутствует всегда. Функция располагает окно над только что внесенным элементом и возвращает указатель нa элемент, если включение произошло успешно.
template<class T> T BraidedSearchTree<T>::insert(T val)
{
int result = 1;
BraidedNode<T> *p = root;
BraidedNcde<T> *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<T>(val);
if (result < 0) {
p->_lchild = win;
p->prev()->Node::insert(win);
} else {
p->_rchild = win;
p->Node::insert(win);
}
return val;
}
Удаление элементов
Компонентная функция remove удаляет элемент, находящийся в окне и перемещает окно в предыдущую позицию:
Элемент val, подлежащий удалению, и указатель n на корень дерева поиска, в котором находится этот элемент, передаются в качестве параметров собственной функции _remove. Эта функция работает подобно своему аналогу с тем же именем в классе SearchTree. Однако при работе со связанным деревом поиска элемент, конечно, должен быть удален как из дерева поиска, так и из ленты:
template<class T>
void BraidedSearchTree<T>::remove(T val, TreeNode<T>* &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<T> *old = (BraidedNode<T>*)n;
if (win == old)
win = old->prev();
n = old->rchild();
old->Node::remove();
delete old;
}
else if (n->_rchild == NULL) { // случай 2
BraidedNode<T> *old = (BraidedNode<T>*)n;
if (win == old)
win = old->prev();
n = old->lchild();
old->Node::remove();
delete old;
}
else { // случай 3
BraidedNode<T> *m = ( (BraidedNode<T>*)n)->next();
n->val = m->val;
_remove(m->val, n->_rchild);
}
}
}
Заметим, что функция _remove использует ленту для поиска последователя узла n в случае 3, когда подлежащий удалению узел имеет два непустых потомка. Отметим также, что параметр n является ссылкой на тип TreeNode*, а не на тип BraidedNode*. Это происходит потому, что n указывает на ссылку, хранящуюся в предке узла, подлежащего удалению, а эта ссылка имеет тип TreeNode*. Если бы вместо этого параметру n был присвоен тип BraidedNode*, то это была бы ошибочная ссылка на анонимный объект. При этом поле ссылки в узле предка было бы недоступно.
Компонентная функция removeMin удаляет из дерева наименьший элемент и возвращает указатель на него, функция возвращает значение NULL, если дерево пусто. Если окно содержало удаляемый наименьший элемент, то окно перемещается в головную позицию, в ином случае оно остается без изменения:
template<class T> T BraidedSearchTree<T>::removeMin(void)
{
Т val = root->next()->val;
if (root != root->next() )
_remove(val, root->_rchild);
return val;
}
