Теоретические положения Деревья. Основные понятия
 Скачать 452 Kb.
|
1.1. Деревья. Основные понятия Дерево – совокупность элементов, называемых узлами (один из которых определен как корень), и отношений, образующих иерархическую структуру узлов. Узлы могут быть элементами любого типа. Формально дерево можно рекуррентно определить следующим образом.
Пустую структуру или дерево без узлов называют также нулевым (пустым) деревом. Путем из узла n1 в узел nk называется последовательность узлов n1, n2, ..., nk, где для всех i, i = 1, 2, ..., k, узел ni является родителем узла ni+1. Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь. Путем нулевой длины будет путь из любого узла к самому себе. Если существует путь из узла а в узел b, то в этом случае узел a называется предком узла b, а узел b – потомком узла a. Число непосредственных потомков (дочерних узлов) внутренней вершины называют ее степенью. Степень дерева определяется максимальной из степеней всех узлов. Предок или потомок узла, не являющийся таковым самого себя, называется истинным предком или истинным потомком соответственно. Только корень дерева не имеет истинного предка. Если узел не имеет истинных потомков, он называется терминальной вершиной или листом, в противном случае – нетерминальной вершиной или внутренним узлом. Поддерево какого-либо дерева можно определить как узел – корень поддерева – вместе со всеми его потомками. Высотой узла называется длина самого длинного пути из этого узла до какого-либо листа. Высота дерева совпадает с высотой корня. Глубина узла x определяется как длина пути от корня до узла x. Ее часто называют просто длиной пути к x. В таком случае корень имеет длину пути 0, его дочерние узлы – длину пути 1 и т.д. Длина пути всего дерева определяется как сумма длин путей всех его узлов. Она называется длиной внутреннего пути. Часто каждому узлу дерева сопоставляется метка, ключ или иначе – значение, которое хранится в узле [1]. Дочерние узлы могут упорядочиваться справа налево. Если порядок дочерних узлов игнорируется, дерево называется неупорядоченным, в противном случае – упорядоченным. Особое значение имеют упорядоченные деревья второй степени. Они называются двоичными или бинарными. Двоичное дерево определяется как конечное множество узлов, пустое, либо состоящее из корня с двумя отдельными двоичными деревьями, которые называются левым и правым поддеревьями этого корня. Деревья степени больше двух называются сильноветвящимися деревьями. Существует несколько способов прохождения (обхода) всех узлов дерева. Три чаще всего используемых способа обхода дерева называются обход в прямом порядке (сверху вниз), обход в обратном порядке (снизу вверх) и обход во внутреннем порядке (симметричный, слева направо). Рекурсивно их можно определить следующим образом.
 Рис. 1. Дерево Т
Можно определить большое количество функций, выполняемых над деревьями. Полагая ключи уникальными, ограничимся следующим списком (в скобках указаны основные параметры, при реализации количество параметров может изменяться) [1]:
Основными операциями являются поиск, включение и удаление. В неупорядоченных несбалансированных деревьях поиск или поиск с включением можно осуществлять, задавшись одним из правил обхода. Без специальных оговорок, удалять в таких деревьях можно только терминальные вершины и вершины, имеющие одного непосредственного потомка (при этом удаляемый узел заменяется своим дочерним узлом). В работе следует использовать одну из следующих стратегий для удаления внутренних узлов: удаляемый узел, имеющий более одного потомка, заменяется либо самым левым, либо самым правым дочерним узлом. 1.2. Реализация деревьев Представление деревьев с помощью массивов Пусть T – дерево с n узлами: 0, 1, ...n-1. Наиболее простым представлением дерева Т является линейный массив А, где каждый элемент А[i] соответствует родителю узла i. Положим, что корню дерева соответствует значение -1. Тогда А[i] = j, если узел j – родитель узла i, и A[i] = -1, если i является корнем (см. рис. 2).  Рис. 2. Реализация дерева в виде массива: а – исходное дерево, б – массив, в котором индексы соответствуют узлам дерева, а элементы – родителям узлов Данное представление использует то свойство деревьев, что каждый узел, отличный от корня, имеет только одного родителя. При таком представлении родителя любого узла можно найти за фиксированное время. Прохождение по любому пути выполняется за время, пропорциональное количеству узлов пути. Если в узлах необходимо хранить ключи, можно использовать другой массив L того же размера, в котором элемент L[i] будет хранить ключ узла i, или объявить элементы массива А структурами, состоящими из целых чисел (номеров узлов) и ключей. Для двоичных деревьев можно использовать иную, более эффективную реализацию в виде массива. Это представление использует один линейный массив A. Значение из корня дерева помещается в нулевой элемент массива, значения из двух дочерних вершин – в соседние элементы и т.д. Если значение из узла N занимает элемент массива A[K], то значение, соответствующее левому дочернему узла этого узла, записано в A[2K], а значение, соответствующее правому дочернему узлу – в A[2K+1]. При таком представлении в массиве могут появиться неиспользуемые значения, которые необходимо каким-либо образом помечать как пустые. Подобная реализация обеспечивает эффективное хранение сбалансированных деревьев, но мало используется ввиду ограничения на размер массива. Представление деревьев с использованием списков дочерних узлов Важным способом реализации дерева является формирование списка дочерних узлов для каждого его узла. Списки можно представлять любым из соответствующих методов, но так как у узлов часто бывает переменное число дочерних узлов, часто используются связные списки.
|
