Бинарное дерево

Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

Бинарные деревья представляют эффективный способ поиска. Бинарное дерево представляет собой структурированную коллекцию узлов. Деревья являются структурами несколько более сложными, чем списки. Списки представляются обычно, как нечто линейное, в то время как деревья в естественном представлении имеют более одного измерения. Деревья обычно изображают растущими сверху вниз, с корнем наверху. Отдельные ячейки, из которых составляется дерево, называют узлами (или потомками). Узел, имеющий дочерние узлы, называется их родительским узлом. Аналогия с генеалогическим деревом позволяет ввести термины прародитель, предок и потомок. Узел, не имеющий дочерних узлов, называется листом. Хотя узел может иметь более одного дочернего, родительский узел может быть у него только один. Структура данных, в которой узлы имеют более одного родителя, не может считаться деревом. Единственым узлом, не имеющим родителя является корневой узел. В двоичном дереве у узла может быть один, два или ни одного потомка. Дочерний узел, расположенный левее родительского, называется левым потомком (левым дочерним). Дочерний узел правее родителя называют правым потомком. Существенное свойство двоичного дерева - это то, что для каждого данного узла все узлы левее его (т.е. левый дочерний и все его потомки) содержат значения, меньше значения самого узла. Аналогичным образом все узлы правее данного содержат большие либо равные значения.

Левое поддерево произвольной вершины X содержит ключи, не превосходящие key[X] (значение вершины X), правое - не меньшие key[X]. Разные бинарные деревья поиска могут представлять одно и то же множество. Время выполнения (в худшем случае) большинства операций пропорционально высоте дерева.

При представлении с использованием указателей для каждой вершины дерева нужно хранить помимо значения ключа key и дополнительных данных, также и указатели left, right, parent (на левое и правое поддерево, а также родителя). Если ребёнка (или родителя - для корня) нет, соответствующая переменная должна равняться NULL. Ключи в двоичном дереве поиска хранятся с соблюдением свойства упорядоченности: Пусть X - произвольная вершина двоичного дерева поиска. Если вершина Y находится в левом поддереве вершины X, то key[X]> =key[Y]. Если вершина Y находится в правом поддереве вершины X, то key[X]< =key[Y]