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


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






Двоичные деревья


Двоичные деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. Коллекция может быть пустой и в этом случае мы имеем пустое двоичное дерево. Если коллекция непуста, то она подразделяется на три раздельных семейства узлов: корневой узел n (или просто корень), двоичное дерево, называемое левым поддеревом для n, и двоичное дерево, называемое правым поддеревом для n. На рис. 1а узел, обозначенный буквой А, является корневым, узел В называется левым потомком А и является корнем левого поддерева А, узел С называется правым потомком А и является корнем правого поддерева А.


Двоичное дерево с показанными внешними узллами (а) и без них (б)

Рис. 1: Двоичное дерево с показанными внешними узллами (а) и без них (б)




Двоичное дерево на рис. 1а состоит из четырех внутренних узлов (обозначенных на рис. кружками) и пяти внешних (конечных) узлов (обозначены квадратами). Размер двоичного дерева определяется числом содержащихся в нем внутренних узлов. Внешние узлы соответствуют пустым двоичным деревьям. Например, левый потомок узла В - непустой (содержит узел D), тогда как правый потомок узла В - пустое дерево. В некоторых случаях внешние узлы обозначаются каким-либо образом, в других - на них совсем не ссылаются и они считаются пустыми двоичными деревьями (на рис. 16 внешние узлы не показаны).


Основанная на генеалогии метафора дает удобный способ обозначения узлов внутри двоичного дерева. Узел р является родителем (или предком) узла n, если n - потомок узла р. Два узла являются братьями, если они принадлежат одному и тому же родителю. Для двух заданных узлов n1 и nk таких, что узел nk принадлежит поддереву с корнем в узле n1, говорят, что узел nk является потомком узла n1, а узел n1 - предком узла nk. Существует уникальный путь от узла n1 вниз к каждому из потомков nk, a именно: последовательность узлов n1 и n2,... nk такая, что узел ni является родителем узла ni+1 для i = 1, 2,..., k-1. Длина пути равна числу ребер (k-1), содержащихся в нем. Например, на рис. 1а уникальный путь от узла А к узлу D состоит из последовательности А, В, D и имеет длину 2.


Глубина узла n определяется рекурсивно:
{ 0     если n - корневой узел
глубина (n) = {
{ 1 + глубина (родителя (n))     в противном случае



Глубина узла равна длине уникального пути от корня к узлу. На рис. 1а узел А имеет глубину 0, а узел D имеет глубину, равную 2.


Высота узла n также определяется рекурсивно:
{ 0     если n - внешний узел
высота (n) = {
{ 1 + max( высота(лев(n)), высота(прав(n)) )     в противном случае



где через лев(n) обозначен левый потомок узла n и через прав(n) - правый потомок узла n. Высота узла n равна длине самого длинного пути от узла n вниз до внешнего узла поддерева n. Высота двоичного дерева определяется как высота его корневого узла. Например, двоичное дерево на рис. 1а имеет высоту 3, а узел D имеет высоту 1.


При реализации двоичных деревьев, основанной на точечном представлении, узлы являются объектами класса TreeNode.


template class TreeNode {
protected:
TreeNode *_lchild;
TreeNode *_rchild;
Т val;
public:
TreeNode(T);
virtual ~TreeNode(void);
friend class SearchTree; // возможные пополнения
friend class BraidedSearchTree; // структуры
};


Элементы данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.


Конструктор класса формирует двоичное дерево единичного размера - единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:


template TreeNode::TreeNode(T v) :
val(v), _lchild(NULL), _rchild (NULL)
{
}


Деструктор ~TreeNode рекурсивно удаляет оба потомка текущего узла (если они существуют) перед уничтожением самого текущего узла:


template TreeNode::~TreeNode(void)
{
if (_lchild) delete _lchild;
if (_rchild) delete _rchild;
}




Двоичные деревья поиска


Основное назначение двоичных деревьев заключается в повышении эффективности поиска. При поиске выполняются такие операции, как нахождение заданного элемента из набора различных элементов, определение наибольшего или наименьшего элемента в наборе, фиксация факта, что набор содержит заданный элемент. Для эффективного поиска внутри двоичного дерева его элементы должны быть организованы соответствующим образом. Например, двоичное дерево будет называться двоичным деревом поиска, если его элементы расположены так, что для каждого элемента n все элементы в левом поддереве n будут меньше, чем n, а все элементы в правом поддереве - будут больше, чем n. На рис. 2 изображены три двоичных дерева поиска, каждое из которых содержит один и тот же набор целочисленных элементов.


Три двоичных дерева поиска с одним и тем же набором элементов

Рис. 2: Три двоичных дерева поиска с одним и тем же набором элементов




В общем случае существует огромное число двоичных деревьев поиска (различной формы) для любого заданного набора элементов.


Предполагается, что элементы располагаются в линейном порядке и, следовательно, любые два элемента можно сравнить между собой. Примерами линейного порядка могут служить ряды целых или вещественных чисел в порядке возрастания, а также слов или строк символов, расположенных в лексикографическом (алфавитном, или словарном) порядке. Поиск осуществляется путем обращения к функции сравнения для сопоставления любых двух элементов относительно их линейного порядка. В нашей версии деревьев поиска действие функции сравнения ограничено только явно определенными объектами деревьев поиска.


Также очень полезны функции для обращения к элементам дерева поиска и воздействия на них. Такие функции обращения могут быть полезны для вывода на печать, редактирования и доступа к элементу или воздействия на него каким-либо иным образом. Функции обращения не принадлежат деревьям поиска, к элементам одного и того же дерева поиска могут быть применены различные функции обращения.


Вперед  >>>
 1  2  3  4 


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

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