Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Структуры данных и хэширование / Словари для произвольных данных / Двоичные деревья /
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вязанные двоичные деревья поиска




Связанное двоичное дерево поиска с головным узлом. Связи ленты представлены дугами

Рис. 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  Обсудить в чате

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