Главная страница
Навигация по странице:

  • 1.2. Реализация деревьев

  • Теоретические положения Деревья. Основные понятия


    Скачать 452 Kb.
    НазваниеТеоретические положения Деревья. Основные понятия
    Дата02.10.2018
    Размер452 Kb.
    Формат файлаdoc
    Имя файлаЗадания Рє лабораторным.doc
    ТипДокументы
    #52263
    страница1 из 3
      1   2   3

    1. Теоретические положения


    1.1. Деревья. Основные понятия
    Дерево – совокупность элементов, называемых узлами (один из которых определен как корень), и отношений, образующих иерархическую структуру узлов. Узлы могут быть элементами любого типа. Формально дерево можно рекуррентно определить следующим образом.

    1. Один узел является деревом. Этот же узел является корнем этого дерева.

    2. Пусть n – узел, а T1, T2, ..., Tk – деревья с корнями n1, n2, ..., nk соответственно. Можно построить новое дерево, сделав n родителем узлов n1, n2, ..., nk. В этом дереве n будет корнем, а T1, T2, ..., Tk – поддеревьями этого корня. Узлы n1, n2, ..., nk называются дочерними узлами узла n. Узлы, находящиеся на одном уровне (в частности, узлы n1, n2, ..., nk), называют соседними (в некоторых источниках – братьями или сестрами).

    Пустую структуру или дерево без узлов называют также нулевым (пустым) деревом. Путем из узла n1 в узел nk называется последовательность узлов n1, n2, ..., nk, где для всех i, i = 1, 2, ..., k, узел ni является родителем узла ni+1. Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь. Путем нулевой длины будет путь из любого узла к самому себе. Если существует путь из узла а в узел b, то в этом случае узел a называется предком узла b, а узел b – потомком узла a. Число непосредственных потомков (дочерних узлов) внутренней вершины называют ее степенью. Степень дерева определяется максимальной из степеней всех узлов. Предок или потомок узла, не являющийся таковым самого себя, называется истинным предком или истинным потомком соответственно. Только корень дерева не имеет истинного предка. Если узел не имеет истинных потомков, он называется терминальной вершиной или листом, в противном случае – нетерминальной вершиной или внутренним узлом. Поддерево какого-либо дерева можно определить как узел – корень поддерева – вместе со всеми его потомками. Высотой узла называется длина самого длинного пути из этого узла до какого-либо листа. Высота дерева совпадает с высотой корня. Глубина узла x определяется как длина пути от корня до узла x. Ее часто называют просто длиной пути к x. В таком случае корень имеет длину пути 0, его дочерние узлы – длину пути 1 и т.д. Длина пути всего дерева определяется как сумма длин путей всех его узлов. Она называется длиной внутреннего пути. Часто каждому узлу дерева сопоставляется метка, ключ или иначе – значение, которое хранится в узле [1]. Дочерние узлы могут упорядочиваться справа налево. Если порядок дочерних узлов игнорируется, дерево называется неупорядоченным, в противном случае – упорядоченным. Особое значение имеют упорядоченные деревья второй степени. Они называются двоичными или бинарными. Двоичное дерево определяется как конечное множество узлов, пустое, либо состоящее из корня с двумя отдельными двоичными деревьями, которые называются левым и правым поддеревьями этого корня. Деревья степени больше двух называются сильноветвящимися деревьями.

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

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

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

    • Далее, пусть Т – дерево с корнем n и поддеревьями Т1, Т2, ..., Тk (см. рис. 1). Для различных способов обхода выполняется следующее:




    Рис. 1. Дерево Т

    1. При прохождении в прямом порядке узлов дерева Т сначала посещается корень n, затем – в прямом порядке – узлы поддерева Т1, далее аналогично все узлы поддерева Т2. Последними в прямом порядке посещаются узлы поддерева Тk.

    2. При симметричном обходе узлов дерева Т сначала посещаются в симметричном порядке все узлы поддерева Т1, далее корень n, затем последовательно в симметричном порядке все узлы поддеревьев
      Т2, ..., Тk.

    3. Во время обхода в обратном порядке сначала последовательно посещаются в обратном порядке все узлы поддеревьев Т1, Т2, ..., Тk, последним посещается корень n.

    Можно определить большое количество функций, выполняемых над деревьями. Полагая ключи уникальными, ограничимся следующим списком (в скобках указаны основные параметры, при реализации количество параметров может изменяться) [1]:

    1. Root(). Возвращает узел, являющийся корнем дерева.

    2. GetLabel(n). Возвращает ключ узла n.

    3. SetLabel(n, m). Устанавливает ключ m узла n.

    4. Search(m). Осуществляет поиск в дереве узла с ключом m. Возвращает искомый узел или нулевой узел, если поиск окончился неудачей.

    5. Add(m, n). Добавляет узел с ключом m в дерево как дочернюю вершину узла n, если в результате выполнения операции степень дерева не изменится и непосредственно перед ее выполнением функция Search(m) возвратила нулевой узел.

    6. Delete(m). Удаляет узел с ключом m.

    7. Parent(n). Возвращает родителя узла n. Если n является корнем, возвращается нулевой узел.

    8. LeftMostChild(n). Возвращает самый левый дочерний узел узла n. Если n является листом, возвращается нулевой узел.

    9. RightSibling(n). Возвращает правого соседа узла n и нулевой узел, если такового не существует. Для этого находится родитель p узла n и все дочерние узлы p, затем среди этих потомков находится узел, расположенный непосредственно справа от узла n.

    10. MakeNull(). Делает дерево пустым.

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

    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[2K], а значение, соответствующее правому дочернему узлу – в A[2K+1]. При таком представлении в массиве могут появиться неиспользуемые значения, которые необходимо каким-либо образом помечать как пустые. Подобная реализация обеспечивает эффективное хранение сбалансированных деревьев, но мало используется ввиду ограничения на размер массива.

    Представление деревьев с использованием списков дочерних узлов

    Важным способом реализации дерева является формирование списка дочерних узлов для каждого его узла. Списки можно представлять любым из соответствующих методов, но так как у узлов часто бывает переменное число дочерних узлов, часто используются связные списки.

    0




    1




    2




    3




    4




    5




    6




    7




    8




    9



      1   2   3


    написать администратору сайта