Высота полного бинарного дерева

22. Математические характеристики деревьев

Определим математические характеристики деревьев. Свойство 1.В любом дереве между двумя его узлами существует один и только один путь их соединяющий. Любые два узла дерева имеют ближайшего общего прародителя: узел лежащий на пути от каждого из этих узлов к корню. Ближайший общий прародитель обязательно существует, потому что им является либо корень дерева, либо корень меньшего поддерева, в котором они оба расположены. Свойство 2Дерево, имеющее N узлов, имеет N-1 связей. Это вытекает из того, что каждый узел за исключением самого верхнего имеет связь со своим родителем. Следующие два свойства относятся к бинарным деревьям. Свойство 3Бинарное дерево, имеющее N внутренних узлов, имеет N+1 внешних узлов. Это можно доказать по индукции. Бинарное дерево, не имеющее внутренних узлов, имеет один внешний. Таким образом, свойство выполняется при N=0. Для N>0, бинарное дерево содержит k внутренних узлов в левом и N-k-1 внутренних узлов в правом поддеревьях, для какого-то k между 0 и N-1, так как корень является внутренним узлом. В соответствии с правилами индукции левое поддерево имеет k+1 внешних узлов, а правое N-k. В результате наше дерево имеет N+1 внешних узлов. Свойство 4Внешняя длина пути любого бинарного дерева имеющего N внутренних узлов на 2N больше чем внутреннего пути. Заметим, что бинарное дерево может быть создано следующим образом: начнем с дерева состоящего только из корня. Затем повторим следующее N раз: выберем какой-нибудь внешний узел и заменим его внутренним с двумя внешними. Если внешний узел был на уровне k, то внутренняя длина пути дерева увеличится на k, а внешняя на k+2. В начале процесса внутренняя и внешняя длины пути равны 0 и в течение N-1 шагов длину его внешнего пути увеличивается по сравнению с внутренней на 2. Наконец мы рассмотрим простое свойство «самого лучшего» сорта бинарных деревьев – полных деревьев. Свойство 5Высота полного бинарного дерева имеющего N внутренних узлов приближенно равна . Если высота полного бинарного дерева n, то, по определению полноты, для Nсправедливо условие Отсюда следует, что высота дерева при N внутренних узлов примерно .

23. Обход деревьев

Обход Деревьев

Когда дерево создано, нас интересует, как по нему путешествовать. Эта операция тривиальна для линейных списков по их определению, но для деревьев существует множество различных подходов, главное различие между которыми, это порядок посещения узлов в дереве. Как мы увидим дальше, для различных задач подходит различный порядок обхода. Сосредоточимся пока на обходе бинарных деревьях. Первый метод, который мы рассмотрим, носит название «текущий – первым». Он может быть использован для того, чтобы написать выражение на Error: Reference source not found в форме префикса. Определяется он простым рекурсивным правилом: «посети корень, затем левое поддерево, затем правое поддерево». Здесь приведена реализация этого метода, основанная на стеке: proceduretraverse( t : link );beginStackInit;push(t);repeatt := pop;visit( t );if( t <> z )thenbeginpush( t^.r ); push( t^.l );end;untilstackempty;end; Следуя правилу, мы должны посетить сначала корень, что мы и делаем, положив его сначала на стек, а затем при входе в цикл, снимая его. Затем, мы спасаем правое, а после него левое поддерева на стек, и в начале цикла поднимаем со стека сначала левое поддерево, а обойдя его, принимаемся за правое. Когда стек оказывается пуст, процедура заканчивает свою работу. На рис. 2. демонстрируется порядок посещения элементов в дереве при этом методе.

1. Обход методом «текущий первым».

Второй метод называется «текущий – между» или «симметричное посещение». Как видно из названия его определяет правило: «посети сначала левое поддерево, затем текущий узел, затем правое поддерево». рис. 3. демонстрирует порядок посещения элементов в дереве при этом методе.

1. Обход «симметричным» методом.

Третий метод называется «текущий – последним». Из названия ясно его правило: «посети сначала левое поддерево, затем правое поддерево, затем текущий узел». На рис. 4. изображен порядок посещения элементов дерева при этом методе.

1. Обход методом «текущий последним».

Наконец последний метод это так называемое поуровневое посещение. Реализация этого метода использует FIFO очередь вместо стека, и определяется он простым правилом: «слева направо – сверху вниз». Ниже приведена простая реализация этого метода: proceduretraverse(t:link); beginQueueInitialize;put(t); repeatt:=get;visit(t); if(t<>z)then beginput(t^.r);put(t^.l); end;untilQueueEmpty;end; 24. быстрая сортировка, характеристика производительности быстрой сортировки

Источник

Полное бинарное дерево. Куча. Очередь с приоритетом

Среди деревьев выделяют особый подкласс, называемый бинарными деревьями. Бинарное дерево — корневое дерево, каждая вершина которого имеет не более двух дочерних, чаще всего чётко упорядоченных: левую и правую. Например, это дерево является бинарным:

Среди бинарных деревьев отдельно выделяют полные бинарные деревья, все вершины которых имеют по две дочерних, кроме листьев, которые расположены на одинаковой глубине:

Также полными часто называют бинарные деревья, у которых полностью заполнены все уровни, кроме последнего:

При 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
 
Олимпиадное программирование в Бресте и Беларуси
 
Источник