Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Упорядоченные ориентированные и отсориентированные деревья
Ниже дается взгляд на деревья как на графы, при чем данные представляются в корне и листьях поддеревьев в качестве меток вершин, а функции доступа (селекторы) представляются ребрами.
Неориентированное дерево с этой точки зрения есть неориентированный связный ациклический граф. Два неориентированных дизъюнктивных дерева могут быть объединены путем добавления ребра между любыми двумя вершинами, по одной из каждого дерева, в единое неориентированное дерево.
Ориентированное дерево есть направленный связный ациклический граф, который содержит одну вершину, называемую корнем, такую, что каждая вершина графа может быть достигнута, исходя из корня, единственным путем. Корень дерева определен однозначно. Лист дерева в представлении дерева в виде графа является вершиной без наследников.
Упорядоченное дерево в графовом представлении есть ориентированное дерево, на поддеревьях которого задан порядок следования. Упорядоченные деревья с точки зрения вычислительной структуры могут быть описаны следующим объявлением типа:
sort ordtree = ordtree(m root, seq ordtree subtrees).
Число непосредственных поддеревьев соответствует длине последовательности в дереве в приведенном выше представлении типа. Это число называется степенью ветвимости дерева. Считается, что z—максимальная степень ветвимости какого-либо дерева, если оно само и все его поддеревья имеют степень ветвимости не превосходящую z.
Двоичное дерево является частным случаем упорядоченного дерева. Двоичные деревья имеют максимальную степень ветвимости 2. В дальнейшем, если речь идет об ориентированных деревьях, будет употреблено просто «деревья».
Максимальное число вершин в путях по дереву называется высотой дерева. Высота пустого дерева, таким образом, равна нулю, а высота одноэлементного дерева есть 1. Высота hi(b) дерева b определяется самым длинным путем в дереве. Дерево называется полным, если все его поддеревья имеют одинаковую степень ветвимости и все пути доступа от корня к его листьям имеют одинаковые длины.
Пусть #b есть число вершин в дереве, а m—максимальная степень ветвимости. Для непустого, полного дерева справедливо
hi(b)-1£logmb.
В соответствии с этим в полном дереве число его вершин растет экспоненциально с высотой дерева.
Если на вершинах дерева задан линейный порядок, то ориентированное дерево называется отсортированным, если прохождение по порядку следования вершин дает возрастающую последовательность их содержимого.
