Хранение в бинарном дереве алфавитного списка

Реализация дерева

Деревья

Каждый элемент дерева называется узлом. Самый верхний узел называется корневым. Конечные нижние узлы называются терминальными или листьями. По вертикали, верхний узел называется родителем отходящих от него нижних, а они называются его дочерними узлами. Узлы, отходящие от одного родителя, называются братьями по отношению друг к другу.

Любой узел вместе с нижележащей частью дерева образует поддерево. Глубина дерева это количество узлов в наиболее длинном пути от корня до листа, то есть количество горизонтальных уровней в нем.

Бинарные деревья имеют не более двух нижележащих ответвлений от каждого вышележащего узла. Каждый узел в бинарном дереве представлен в памяти компьютера блоком из трех частей. Это данные, хранящиеся в узле, и два указателя на нижележащие узлы. Сначала помещается указатель на левый из них, а потом на правый.

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

Если какого-то элемента в дереве нет, то в выделенной для него области памяти стоит отметка об этом.

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

Для этого нам потребуется место в памяти, несколько большее чем для массива исходных записей, так как в структуру блоков дерева входят указатели.

Но зато при поиске какого-либо элемента алгоритм наиболее быстро обеспечивает его отыскание. Сначала сравниваем, зная, на какую букву алфавита начинается искомый элемент, его с корнем. Если элемент по алфавиту расположен до того, который находится в корне, то идем в левое поддерево, а иначе идем в правое. И так до тех пор, пока не найдем.

Добавление нового элемента осуществляется по почти такому же алгоритму. Сначала находим его место в дереве, а потом записываем его туда.

Указатель на дерево содержит адрес его корневого блока.

Если дерево не поместилось, по мере его разрастания, в выделенную область памяти, то указатели в блоках его элементов будут содержать адреса уже в других областях памяти. Таким образом, дерево распространяется по различным областям памяти.