Бинарное дерево количество узлов

3.3. Бинарные деревья

3.3.1. Определение. Представления бинарных деревьев

Бинарное (двоичное) дерево — особый вид дерева, в котором каждый узел имеет не более двух поддеревьев, причем в случае одного поддерева следует различать левое и правое поддерево. При изображении бинарных деревьев левого и правого сына различают по наклону соединительной линии (влево или вправо). На рис.3.4 показаны два различных бинарных дерева. Интересно отметить, что если рассматривать данные структуры как обычные упорядоченные деревья, то они являются полностью идентичными (в упорядоченном дереве единственный сын всегда первый, т. е. левый потомок). Это говорит о том, что бинарные деревья не являются частным случаем упорядоченого дерева, а представляют собой особый вид деревьев.

Рис.3.5. Два различных бинарных дерева

Приведем формальное рекурсивное определение бинарного дерева [8].

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

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

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

Иногда при записи левое и правое поддерево разделяют запятыми, но чаще пробелом.

Левое или правое поддерево или оба вместе (для листьев) могут быть пустыми, при этом для пустых деревьев часто используется специальное обозначение . Чтобы сократить запись, в ней разрешается опустить правое поддерево, если оно пустое, а для листьев опустить оба пустых поддерева (но нельзя опускать пустое левое поддерево, иначе по такой записи нельзя будет правильно восстановить изображение бинарного дерева!). Так, деревьям, изображенным на рис.3.5, соответствуют различные левые скобочные записи в сокращенной форме:

Бинарные деревья, у которых все узлы, кроме листьев, имеют сторого по два сына, называются строго бинарными. Деревья, изображенные на рис. 3.5, не являются строго бинарными.

3.3.2. Математические свойства бинарных деревьев

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

На любом уровне n бинарное дерево может содержать от 1 до 2 n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. На рис. 3.6 дерево А содержит 8 узлов при высоте 3, в то время как дерево B содержит 5 узлов при высоте 4.

Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (e) и каждый внутренний узел имеет только одного сына. Вырожденное дерево можно считать аналогом линейного связного списка, его высота равна количеству узлов без единицы. Это максимально возможное значение для высоты бинарного дерева. В большинстве алгоритмов, использующих бинарные деревья, вырожденное дерево — наихудший случай при оценке производительности.

Рис.3.6. Бинарные деревья различной плотности

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

Наивысшей степенью плотности обладают полные бинарные деревья, которые имеют 2 k узов на каждом уровне k.

Рис.3.7. Полное и почти полное бинарные деревья

На рис. 3.7, а показано полное бинарное дерево высоты два. Обратим внимание на такие факты.

На нулевом уровне имеется 2 0 узлов, на первом — 2 1 , на втором — 2 2 и т.д. На первых k-1 уровнях количество узлов составляет

1 + 2 + 4 + . + 2 k-1 = 2 k -1

На уровне k количество узлов 2 k , т. е. ровно на один больше.

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

h=log ₂ n, где n — количество листьев

h= log ₂ (N+1)-1, где N —количество узлов полного бинарного дерева.

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

Полные и почти полные бинарные деревья обладают еще одним интересным свойством — если их узлы нумеровать, начиная с единицы, сверху вниз и слева направо, то левому сыну всегда будет соответствовать код, в два раза больше кода его родителя, а правому сыну — код, на единицу больший, чем код код левого сына (рис.3.8). Номер корня всегда равен 1, его левый потомок получает номер 2, правый — номер 3. Левый потомок узла 2 получит номер 4, а правый — 5, левый потомок узла 3 получит номер 6, правый — 7 и т.д. Такая схема нумерации используется при представлении деревьев с помощью массивов. К этой теме мы еще вернемся.

Рис.3.8. Нумерация узлов полного или почти полного бинарного дерева

По такой схеме можно нумеровать и узлы бинарных деревьев, которые не являются почти полными, поскольку в этом случае гарантируется уникальность каждого номера, если в процессе работы к дереву добавляются новые листья. Используя такой способ нумерации, можно реализовать древовидную структуру на основе массива. Такая реализация будет приведена в главе 4.

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

Источник

Полное бинарное дерево

Без рубрики

Мы знаем, что дерево — это нелинейная структура данных. Он не имеет ограничений по количеству детей. Бинарное дерево имеет ограничение, поскольку любой узел дерева имеет не более двух дочерних элементов: левого и правого дочерних элементов.

Введение в полное двоичное дерево

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

Немного терминологии

• Корень— узел, в котором от родителя не исходит ни одно ребро. Пример — узел А
• Дочерний— узел, имеющий некоторое входящее ребро, называется дочерним. Пример — узлы B, H являются дочерними узлами A и D соответственно.
• Одноуровневый— узлы, имеющие одного и того же родителя, являются одноуровневыми. Пример- J, K являются братьями и сестрами, так как у них один и тот же родитель E.
• Степень узла— количество дочерних элементов определенного родителя. Пример. Степень A равна 2, а степень H равна 1. Степень L равна 0.
• Внутренние/внешние узлы. Листовые узлы являются внешними узлами, а нелистовые узлы — внутренними узлами.
• Уровень— количество узлов на пути к целевому узлу. Пример. Уровень узла H равен 3, поскольку узлы A, D и H сами образуют путь.
• Высота— количество ребер для достижения конечного узла, корень находится на высоте 0. Пример — высота узла E равна 2, так как он имеет два ребра от корня.

Свойства полного бинарного дерева

• Полное бинарное дерево называется правильным бинарным деревом, все листья которого имеют одинаковую глубину.
• В полном бинарном дереве число узлов на глубине dравно 2 d.
• В полном бинарном дереве с nузлами высота дерева равна log(n+1).
• Все уровни, кроме последнего, полностью заполнены.

Идеальное бинарное дерево против полного бинарного дерева

Двоичное дерево высоты «h», имеющее максимальное количество узлов, является совершенным бинарным деревом.
Для заданной высоты h максимальное количество узлов равно 2 h+1 −1.

Полное бинарное дерево высоты h является правильным бинарным деревом до высоты h-1, и элементы последнего уровня хранятся в порядке слева направо.

Пример 1

Высота данного бинарного дерева равна 2, а максимальное количество узлов в этом дереве равно n= 2 h+1 −1 = 2 2+1 −1 = 2 3 −1 = 7.
Следовательно, мы можем заключить, что это идеальное бинарное дерево.
Теперь для полного бинарного дерева оно заполнено до высоты h-1, т.е. 1, а элементы последнего уровня сохраняются в порядке слева направо. Следовательно, это также полное двоичное дерево. Вот представление элементов при хранении в массиве

Элемент хранится в массиве уровень за уровнем

В массиве все элементы хранятся непрерывно.

Пример 2

Высота данного бинарного дерева равна 2, а максимальное количество узлов, которое должно быть, равно 2 h+1 — 1 = 2 2+1 — 1 = 2 3 — 1 = 7.
Но количество узлов в дереве равно 6. Следовательно, это не идеальное бинарное дерево.
Теперь для полного бинарного дерева оно заполнено до высоты h-1, т.е. 1, и элемент последнего уровня сохраняются в порядке слева направо. Следовательно, это полное бинарное дерево. Сохраните элемент в массиве, и он будет выглядеть так:

Элемент хранится в массиве уровень за уровнем

Пример 3

Высота бинарного дерева равна 2, а максимальное количество узлов, которое может быть, равно 7, но узлов всего 5, поэтому это не идеальное бинарное дерево.
В случае полного бинарного дерева мы видим, что на последнем уровне элементы не заполняются слева направо. Так что это не полное бинарное дерево.

Элемент хранится в массиве уровень за уровнем

Элементы массива не являются непрерывными.

Полное двоичное дерево против полного двоичного дерева:

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

Пример 1

В данном бинарном дереве нет узла, имеющего степень 1, 2 или 0 для каждого узла, следовательно, это полное бинарное дерево.

Для полного бинарного дерева элементы хранятся по уровням, а не с крайней левой стороны на последнем уровне. Следовательно, это не полное бинарное дерево. Представление массива:

Элемент хранится в массиве уровень за уровнем

Пример 2

В данном бинарном дереве нет узла, имеющего степень 1. Каждый узел имеет степень либо 2, либо 0. Следовательно, это полное бинарное дерево.

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

Элемент хранится в массиве уровень за уровнем

Пример 3

В данном бинарном дереве узел B имеет степень 1, что нарушает свойство полного бинарного дерева, следовательно, это не полное бинарное дерево.

Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Следовательно, это полное бинарное дерево. Массивное представление бинарного дерева:

Элемент хранится в массиве уровень за уровнем

Пример 4

В данном бинарном дереве узел C имеет степень 1, что нарушает свойство полного бинарного дерева, следовательно, это не полное бинарное дерево.

Для полного бинарного дерева элементы хранятся по уровням и заполняются с крайней левой стороны последнего уровня. Здесь узел E нарушает условие. Следовательно, это не полное бинарное дерево.

Создание полного бинарного дерева

Мы знаем, что полное бинарное дерево — это дерево, в котором, за исключением последнего уровня (скажем, l ), все остальные уровни имеют ( 2l ) узлов, и узлы выстроены слева направо.
Его можно представить с помощью массива. Если родитель имеет индекс i, то левый дочерний элемент находится в 2i+1, а правый дочерний элемент — в 2i+2.

Полное бинарное дерево и его представление в виде массива

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

Шаг 1: Инициализируйте корень новым узлом, когда дерево пусто.

Шаг 2: Если дерево не пусто, получите передний элемент

Если передний элемент не имеет левого дочернего элемента, установите левый дочерний элемент в новый узел
Если правильный дочерний элемент отсутствует, установите правильный дочерний элемент в качестве нового узла.

Шаг 3: Если у узла есть оба дочерних элемента, извлеките его из очереди.

Шаг 4: Поставьте в очередь новые данные.

Рассмотрим следующий массив:

1. 1-й элемент будет корнем (значение по индексу = 0)

2. Следующий элемент (с индексом = 1) будет левым, а третий элемент (с индексом = 2) будет правым дочерним элементом корня.

B как левый дочерний элемент и D как правый дочерний элемент

3. Четвертый (индекс = 3) и пятый элементы (индекс = 4) будут левым и правым дочерними элементами узла B.

E и F — левый и правый потомки B

4. Следующий элемент (индекс = 5) будет левым дочерним элементом узла D.

G делается левым дочерним элементом узла D

Вот как создается полное бинарное дерево.

Источник