Корневое дерево бинарное дерево

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

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

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

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

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

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

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

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

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

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-индексации вершин по уровням, приведённой выше, существуют простые формулы перехода между вершинами. Для вершины с индексом \(v\) формулы для спуска влево, спуска вправо, и подъёма вверх выглядят следующим образом:

\[l = 2v \\ r = 2v + 1 \\ p = \left\lfloor \right\rfloor\]

В связи с этим полные бинарные деревья чаще всего хранят не в виде списка смежности, а в виде простого массива, где \(tree[v]\) — некоторое значение, присвоенное вершине с индексом \(v\). Для обхода дерева используются формулы, приведённые выше.

Стоит отметить, что высота (количество уровней) полного бинарного дерева из \(N\) вершин равна \(\log N\). Это свойство часто используется для оценки сложности различных алгоритмов.

Куча

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

Классическая куча поддерживает следующие операции:

• Добавить элемент (Сложность: \(O(\log N)\))
• Найти максимум (Сложность: \(O(1)\))
• Извлечь максимальный элемент (Сложность: \(O(\log N)\))

Элементы в куче хранятся в виде полного бинарного дерева. Главное его свойство (инвариант кучи) формулируется следующим образом:

Элемент в каждой вершине больше либо равен элементов во всех дочерних вершинах.

Из этого свойства следует, что минимальный элемент всегда будет находиться в корне дерева.

При добавлении в кучу нового элемента, ему присваивается первый доступный индекс. То есть, бинарное дерево заполняется по уровням слева направо. После добавления элемента возможно, что инвариант кучи перестанет выполняться, так как новый элемент будет больше своего прямого предка. В таких случаях просто меняем элемент местами с прямым предком. Если инвариант кучи всё ещё не выполняется, меняем его местами с новым предком, и так далее, пока куча не нормализуется. Такая операция называется проталкиванием вверх.

При извлечении максимального элемента воспользуемся следующей хитростью: переместим последний элемент в куче (крайний правый на последнем уровне) в корень дерева на место удалённого максимума. Это почти наверняка нарушит инвариант, так как новый “максимум” будет меньше элементов в дочерних вершинах. Сравним два дочерних элемента, выберем из них больший, и поменяем его местами с текущим “максимумом”. Повторяем эту операцию, пока инвариант не восстановится. Это называется проталкиванием вниз.

Реализация

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
 
struct heap  vectorint> tree; heap()  tree.push_back(0); //Мы собираемся работать в 1-индексации, поэтому //просто поместим в tree[0] произвольное значение. > void push(int x)  tree.push_back(x); sift_up(tree.size() - 1); > int max()  if (tree.size() > 1)  return tree[1]; > else  //Ошибка: попытка найти максимум в пустой куче > > void pop()  if (tree.size() > 1)  tree[1] = tree.back(); tree.pop_back(); sift_down(1); > else  //Ошибка: попытка извлечь максимум из пустой кучи > > //Проталкивание вверх. void sift_up(int v)  if (v == 1)  return; //Больше некуда подниматься. > if (tree[v / 2]  tree[v])  swap(tree[v], tree[v / 2]); sift_up(v / 2); > > //Проталкивание вниз void sift_down(int v)  if (v * 2 >= tree.size())  return; //Больше некуда спускаться. > //Индекс большего дочернего элемента int max_idx; if (v * 2 + 1 == tree.size())  //Если можно спуститься только влево max_idx = v * 2; > else if (tree[v * 2] >= tree[v * 2 + 1])  max_idx = v * 2; > else  max_idx = v * 2 + 1; > if (tree[v]  tree[max_idx])  swap(tree[v], tree[max_idx]); sift_down(max_idx); > > bool empty()  return tree.size() == 1; > >; 
 
Понятие очереди с приоритетом
 
Вы можете услышать, как вместо термина “куча” используется термин “очередь с приоритетом”. На практике они взаимозаменимы, хотя разница в значении всё-таки присутствует.
 
Очередь с приоритетом - абстракная структура данных, позволяющая поддерживать множество элементов, находить и извлекать минимум из него, тогда как куча - конкретная структура данных, основанная на полном бинарном дереве. Любая куча является очередью с приоритетом, но не любая очередь с приоритетом (в теории) является кучей (на практике почти что любая). Вы можете реализовать поддержку множества с извлечением максимума с помощью простого массива, она будет иметь сложность операций \(O(N)\), но всё равно являться очередью с приоритетом.
 
(Если вы знакомы с объектно-ориентированным программированием, то очередь с приоритетом - интерфейс, а куча - класс, реализующий его.)
 
Очередь с приоритетом в стандартной библиотеке C++
 
В стандартной библиотеке C++ присутствует реализация кучи, поддерживающая все операции, приведённые выше. Это класс std::priority_queue . Для работы с ним используются следующие методы:
 
bool empty(); unsigned int size(); T top(); //"Верхний" элемент. По умолчанию - максимум. void push(T x); //Добавить элемент в очередь. void pop(); //Извлечь элемент. 
 
По умолчанию используется куча для поиска максимума. Для использования кучи для поиска минимума нужно использовать тип std::priority_queue, greater> .
 
brestprog
 
Олимпиадное программирование в Бресте и Беларуси
 
Источник