Свойства бинарного дерева
Мы обсудили введение в бинарное дерево в наборе 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.
Доказательство см. в лемме о рукопожатии и дереве.
В следующей статье о серии деревьев мы обсудим различные типы бинарных деревьев и их свойства.