Рис. 1: Связанное двоичное дерево поиска с головным узлом. Связи ленты представлены дугами
Для краткости связанное двоичное дерево поиска будем называть связанным деревом поиска, а охватывающий его связный список - лентой.
Связанное дерево поиска реализуем в виде класса BraidedSearchTree. Этот класс отличается от класса SearchTree из описания двоичных деревьев поиска по трем существенным признакам. Во-первых, объекты класса BraidedSearchTree обладают связным списком (лентой), который для каждого узла устанавливает ссылки на предшественника и последователя. Во-вторых, объекты класса BraidedSearchTree поддерживают окно, которое в любой момент времени располагается над каким-либо элементом в дереве. Окно служит той же цели, что и в классе List(используется класс Node из реализации кольцевого списка): существует целый ряд операций с окном или с элементом в окне. В-третьих, элемент root класса BraidedSearchTree указывает на головной узел - "псевдокорневой узел", правый потомок которого является фактическим корнем связанного дерева поиска. Если посмотреть на ленту, то узел, содержащий наименьший элемент в дереве, следует за головным узлом, а узел, содержащий самый большой элемент, предшествует головному узлу. Следовательно, головной узел соответствует головной позиции, которая располагается одновременно перед первой позицией и после последней (рис. 1).
Класс BraidedNode
Узлы связанного дерева поиска являются объектами класса BraidedNode. Поскольку эти узлы действуют одновременно как узлы дерева и как узлы списка, то шаблон класса BraidedNode составим на основе классов TreeNode и Node:
template class BraidedNode : public Node, public TreeNode { public : BraidedNode (T); BraidedNode *rchild(void); BraidedNode *lchild (void); BraidedNode *next (void); BraidedNode *prev(void); friend class BraidedSearchTree; };
Конструктор класса BraidedNode явно инициализирует базовый класс TreeNode по своему списку инициализации, а базовый класс Node инициализируется неявно, поскольку его конструктор не имеет параметров:
template BraidedNode::BraidedNode (Т val) : TreeNode (val) { }
Компонентные функции rchild, lchild, next и prev устанавливают четыре ссылки для текущего узла - первые два для дерева поиска, а последние два - для ленты:
template BraidedNode *BraidedNode::rchild (void) { return (BraidedNode *)_rchild; }
template BraidedNode *BraidedNode::lchild (void) { return (BraidedNode *) )_lchild; }
template BraidedNode *BraidedNode::next (void) { return (BraidedNode *)_next; }
template BraidedNode *BraidedNode::prev (void) { return (BraidedNode *)_prev; }
Класс BraidedSearchTree
Шаблон класса BraidedSearchTree определяется следующим образом:
template class BraidedSearchTree { private: BraidedNode *root; // головной узел BraidedNode *win; // текущее окно int (*cmp) (T,T); // функция сравнения void _remove(T, TreeNode * &); 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); };
1 2 3
8 8 8
|