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

Опубликовано: 26 Февраля, 2023

Мы обсудили введение в бинарное дерево в наборе 1. В этом посте обсуждаются свойства бинарного дерева.

1) Максимальное количество узлов на уровне l бинарного дерева равно 2 l .
Здесь уровень — это количество узлов на пути от корня к узлу (включая корень и узел). Уровень корня 0.
Это можно доказать по индукции.
Для корня l = 0, количество узлов = 2 0 = 1
Предположим, что максимальное количество узлов на уровне 'l' равно 2 l
Поскольку в двоичном дереве каждый узел имеет не более 2 дочерних элементов, на следующем уровне будет в два раза больше узлов, т. е. 2 * 2 l .

2) Максимальное количество узлов в бинарном дереве высоты 'h' равно 2 h – 1 .
Здесь высота дерева — это максимальное количество узлов на пути от корня до листа. Высота дерева с одним узлом считается равной 1.
Этот результат может быть получен из пункта 2 выше. Дерево имеет максимальное количество узлов, если все уровни имеют максимальное количество узлов. Таким образом, максимальное количество узлов в бинарном дереве высоты h равно 1 + 2 + 4 + .. + 2 h-1 . Это простой геометрический ряд с h членами, а сумма этого ряда равна 2h – 1.
В некоторых книгах высота корня считается равной 0. В этом соглашении приведенная выше формула принимает вид 2 ч + 1 – 1.

3) В двоичном дереве с N узлами минимально возможная высота или минимальное количество уровней составляет Log 2 (N+1).
На каждом уровне должен быть хотя бы один элемент, поэтому высота не может быть больше N. Двоичное дерево высоты «h» может иметь максимум 2 h – 1 узлов (предыдущее свойство). Таким образом, количество узлов будет меньше или равно этому максимальному значению.

N <=  2h - 1
2h >= N+1
log2(2h) >= log2(N+1)           (Taking log both sides)
hlog22 >= log2(N+1)       (h is an integer)
h  >= | log2(N+1) |

Таким образом, минимальная возможная высота | журнал 2 (N+1) |

4) Двоичное дерево с L листьями имеет не менее | Лог 2 л |+ 1 уровень.
Двоичное дерево имеет максимальное количество листьев (и минимальное количество уровней), когда все уровни полностью заполнены. Пусть все листья находятся на уровне l, тогда ниже верно число листьев L.

L   <=  2l-1  [From Point 1]
l =   | Log2L | + 1 
where l is the minimum number of levels.

5) В двоичном дереве, где каждый узел имеет 0 или 2 дочерних элемента, количество листовых узлов всегда на один больше, чем узлов с двумя дочерними элементами .

L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children
Proof:
No. of leaf nodes (L) i.e. total elements present at the bottom of tree = 
2h-1 (h is height of tree)
No. of internal nodes = {total no. of nodes} - {leaf nodes} = 
{ 2h - 1 } - {2h-1} = 2h-1 (2-1) - 1 = 2h-1 - 1
So , L = 2h-1
     T = 2h-1 - 1
Therefore L = T + 1
Hence proved

6) В непустом бинарном дереве, если n — общее количество узлов, а e — общее количество ребер, то e = n-1.

У каждого узла в бинарном дереве есть ровно один родитель, за исключением корневого узла. Итак, если n - это сумма
количество узлов, то n-1 узлов имеют ровно одного родителя. Между любым ребенком и его
родитель. Таким образом, общее количество ребер равно n-1.

Доказательство см. в лемме о рукопожатии и дереве.
В следующей статье о серии деревьев мы обсудим различные типы бинарных деревьев и их свойства.

РЕКОМЕНДУЕМЫЕ СТАТЬИ