Деревья определения основные свойства

Определение и свойства деревьев.

Деревом называется произвольный связный граф без циклов. Деревья обладают следующими свойствами:

любые две вершины соединены единственной простои цепью

количество ребер на единицу меньше количества вершин

при удалении любого ребра дерево становится не связным графом

при добавлении к дереву любого ребра в дереве появляется ровно один простой цикл.

Фактически дерево можно получить из любого связного графа

Утверждение: любой связный граф содержит остовный подграф который является деревом. Этот подграф называется остовыным деревом.

Специальные виды деревьев

1 Корневые деревья

Определение: Корневое дерево — ориентированное дерево, которое удовлетворяет условиям:

a) Имеется ровно один узел в который не входит не одно

В каждый узел кроме корня входит ровно одно ребро

Из корня имеется путь к любому ребру.

Если имеется путь от вершины vl к вершине v2, тогда вершина vl предок вершины v2, а вершина v2 потомок вершины vl.

Вершина которая не имеет потомков называется концевой вершиной или листом. Не концевую вершину называют внутренней. Если V₁ и V₂ дуга корневого дерева, то V₁— отец, a V₂— сын

Глубина дерева — длина пути из корня. Узлы находящиеся на одной глубине называются ярусами дерева.

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

2 Бинарные деревья

Определение: Бинарное дерево — корневое дерево у каждой вершины которого не более двух сыновей.

В таком дереве любой произвольный узел имеет левого и правого сына. Поддерево корнем которого является левый сын называется левым поддеревом. Поддерево корнем которого является правый сын называется правым поддеревом.

Имеется два способа представления бинарных деревьев:

1. Представление в виде двух массивов: первый массив- левые сыновья, второй — правые.

2. Представление в виде списковой структуры tree_ ptr Tree_mode — запись имеющая структуру:

Element- тип узла; Left: tree_ ptr; Right: tree_ ptr;

3 Полные бинарные деревья

Определение: Полное бинарное дерево — бинарное дерево для которого выполняются условия:

a) Заполнение дерева осуществляется от корня к листьям по уровням.

b) Заполнение уровней осуществляется слева направо.

Полные бинарные деревья представляются в виде одномерного массива: первый элемент массива — корень дерева. Для любого i-того узла элемент с индексом (2i) — левый сын, элемент с индексом (2i+l)- правый сын. Отец узла j — (j/2).

4 Бинарные поисковые деревья

Определение: Бинарное поисковое дерево — дерево поиска,

Все ключи в левом поддереве меньше ключа узла V

В правом поддереве все ключи больше, чем ключ V

В дереве нет одинаковых ключей.

5 Сбалансированные деревья

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

Определение: Дерево называется сбалансированным, если оно бинарное поисковое и высоты двух поддеревьев в каждой из вершин отличаются не более, чем на единицу.

6 Способы обхода узлов в бинарных деревьях

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

Существует три наиболее распространенных способа обхода деревьев:

1. Прямой порядок: корень посещается раньше, чем поддеревья

Порядок обхода: корень — левое поддерево — правое поддерево.

Процедура организуется рекурсивно.

2. Обратный порядок (снизу вверх): корень посещается после поддеревьев.

Порядок обхода: левое поддерево — правое поддерево- корень.

3. Внутренний порядок (слева направо )

Порядок обхода: левое поддерево – корень — правое поддерево.

7 Представление множеств с помощью деревьев

Базовыми операциями над множествами являются:

определение принадлежности элемента множества.

объединение не пересекающихся множеств.

Каждое множество будем представлять в виде корневого дерева. Корень дерева можно использовать для хранения имени множества. Дерево будем представлять в каноническом виде.

Чтобы определить, к какому множеству принадлежит некоторый элемент — находим этот элемент и определяем корень множества, к которому он принадлежит. Этот корень — есть имя искомого множества.

Объединение непересекающихся множеств можем реали­зовать тремя способами:

Источник

1. Бинарные деревья – основные определения, свойства и теоремы Определение

Двоичное дерево — иерархическая структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

Свойства

• оба поддерева — левое и правое — являются двоичными деревьями поиска;
• у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X;
• у всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X;
• данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше;
• информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако это касается реализации, а не природы двоичного дерева поиска.

2. Двоичное дерево поиска. Свойства. Алгоритмы выполнения основных операций Определение

• Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.
• Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
• Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

Основные свойства двоичного дерева поиска совпадают со свойствами обычного двоичного дерева (см. п. 1).

Базовый интерфейс двоичного дерева поиска состоит из трёх операций:

• FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K;
• INSERT(K, V) — добавление в дерево пары (key, value) = (K, V);
• REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key= K;

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE (симметричный), PREFIX_TRAVERSE (прямой) и POSTFIX_TRAVERSE (обратный). Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Алгоритмы основных операций Поиск элемента (find)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

• Если дерево пусто, сообщить, что узел не найден, и остановиться.
• Иначе сравнить K со значением ключа корневого узла X.
  • Если K=X, выдать ссылку на этот узел и остановиться.
  • Если K>X, рекурсивно искать ключ K в правом поддереве Т.
  • Если K

  Источник

  Теория графов

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

1. Для – графа следующие утверждения эквивалентны:
   1. – дерево;
   2. Любые две несовпадающие вершины графа соединяет единственная простая цепь;
   3. – связный граф, и любое ребро есть мост;
   4. – связный граф и древовидный;
   5. – ациклический граф (лес) и древовидный;
   6. – ациклический граф (лес) и субцикличекий;
   7. – связный, субциклический и неполный, ;
   8. – древовидный и субциклический, исключая и ;
(1->2): Если – дерево, то любые две его несовпадающие вершины соединяет единственная простая цепь. От противного. Пусть существуют две цепи (см. рис.). Тогда — простой цикл. (2->3): Если любые две несовпадающие вершины графа соединяет единственная простая цепь, то – связный граф, и любое ребро есть мост. Имеем: (число компонент связности). Далее от противного. Пусть ребро — не мост. Тогда в концы этого ребра связаны цепью. Само ребро в исходном графе – вторая цепь, что противоречит условию. (3->4): Если – связный граф, и любое ребро есть мост, то – связный и древовидный (). Индукция по (числу вершин). Если , то (число ребер). Пусть равенство выполняется для всех графов с числом вершин меньше . Докажем, что оно выполняется и для вершин. Удалим из ребро , являющееся мостом. Получим две компоненты связности и , для которых верно равенство . Т.е. , . Тогда . (4->5): Если – связный и древовидный (), то – ациклический граф (лес) и древовидный (). От противного. Пусть есть цикл с вершинами и ребрами. Остальные вершин связаны с этим циклом ребрами, т.к. граф связный. Следовательно, , что противоречит условию . Остальное без док-ва.

1. Ориентированные деревья

1. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами:
• существует единственный узел, в который не входит ни один другой узел. Он называется корнем ордерева;
• во все остальные узлы входит только по одному узлу;
• каждый узел достижим из корня.
1. Ордерево обладает следующими свойствами:

1. ; 2. если в ордереве отменить ориентацию ребер, то получится обычное дерево; 3. для каждого узла существует единственный путь, ведущий в этот узел из корня; 4. подграф, определяемый множеством узлов, достижимых из узла , является ордеревом с корнем . Это ордерево называется поддеревом узла .

1. Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние отт корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Источник

Читайте также:  Деревья возле линии электропередач