Краткие теоретические сведения. Представление динамических данных в виде древовидных структур оказывается довольно удобным и эффективным для решения задач быстрого поиска информации

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

Дерево состоит из элементов, называемых узлами (вершинами), которые соединены между собой направленными дугами (рис. 5.1). В случае X ® Y вершина X называется предком (родителем), а Y – потомком (сыном, дочерью).

Дерево имеет единственный узел, не имеющий предков (ссылок на этот узел), который называется корнем. Любой другой узел имеет ровно одного предка, т.е. на каждый узел дерева имеется ровно одна ссылка. Узел, не имеющий сыновей, называется листом (например узел Y).

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

Рис. 5.1