Вычисление высоты дерева алгоритм

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

Дай 10 !)

суббота, 30 июля 2011 г.

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

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log₂N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2 К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2 j — 1 узел.
*-Нравится статья? Кликни по рекламе! 🙂

Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов. И применяются для быстрого поиска информации. Например в статье Двоичный (бинарный) поиск элемента в массиве мы искали во встроенной в Python структуре данных, типа list, а могли реализовать бинарное дерево. Двоичные деревья, как и связные списки, являются рекурсивными структурами.
Различные реализации одного и того же бинарного дерева

• полное(расширенное) бинарное дерево — каждый узел, за исключением листьев, имеет по 2 дочерних узла;
• идеальное бинарное дерево — это полное бинарное дерево, в котором все листья находятся на одной высоте;
• сбалансированное бинарное дерево — это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n — общее число узлов;
• вырожденное дерево — дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
• бинарное поисковое дерево (BST) — бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.

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

2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238

Более полную статью, по кодам Хаффмана читай в моей более ранней статье.

Реализация:
До этого, в своих статьях я показывал силу функционального программирования Python.
Теперь, пришло время, показать ООП в действии, создав новую структуру данных Tree, состоящую из других структур, типа Node.
Сразу скажу, что код взят с сайта IBM с минимальными изменениями и дополнениями. С моей точки зрения данный класс является недееспособным с точки зрения добавления элементов,по причине того, что мы сами должны строить дерево, помня структуру у себя в голове, а ведь мы можем и ошибиться. И позже я напишу так, как мне кажется верным, где добавление элемента является рекурсивным проходом по дереву и поиску подходящего места. А пока, разберем, что есть:

class node: def __init__(self, data = None, left = None, right = None): self.data = data self.left = left self.right = right def __str__(self): return 'Node ['+str(self.data)+']' #/* класс, описывающий само дерево */ class Tree: def __init__(self): self.root = None #корень дерева # /* функция для добавления узла в дерево */ def newNode(self, data): return node(data,None,None)

Дальше, все функции расширяют класс Tree.

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

# /* функция для вычисления высоты дерева */ def height(self,node): if node==None: return 0 else: lheight = self.height(node.left) rheight = self.height(node.right) if lheight > rheight: return(lheight+1) else: return(rheight+1)

«Зеркальное» отражение бинарного дерева
Когда два дерева являются зеркальным отражением друг друга, то говорится, что они симметричны. Для получения «зеркальной» копии дерева сначала выполняется проверка на наличие у корня дерева дочерних узлов, и если эти узлы есть, то они меняются местами. Потом эти же действия рекурсивно повторяются для левого и правого дочерних узлов. Если существует только один дочерний узел, тогда можно переходить на один уровень ниже по дереву и продолжать.

# /* функция для зеркального отражения дерева */ def mirrorTree(self, node): if node.left and node.right: node.left,node.right=node.right,node.left self.mirrorTree(node.right) self.mirrorTree(node.left) else: if node.left==None and node.right: return self.mirrorTree(node.right) if node.right==None and node.left: return self.mirrorTree(node.left)

Проверка наличия узла в бинарном дереве
Нужно только учесть, что данная функция не работает для зеркального отображения дерева!

# /* функция для проверки наличия узла */ def lookup(self, node, target): if node == None:return 0 else: if target == node.data: return 1 else: if target < node.data: return self.lookup(node.left, target) else: return self.lookup(node.right, target)

Ширина бинарного дерева
Под шириной дерева понимается максимальное количество узлов, которые расположены на одной высоте. Чтобы определить ширину дерева, достаточно просто добавить счетчик в уже рассмотренный алгоритм для определения высоты дерева.

# /* функция для вычисления ширины дерева */ def getMaxWidth(self,root): maxWdth = 0 i = 1 width = 0 ; h = self.height(root) while( i < h): width = self.getWidth(root, i) if(width >maxWdth): maxWdth = width; i +=1 return maxWdth; def getWidth(self, root, level): if root == None: return 0 if level == 1: return 1 elif level > 1: return self.getWidth(root.left, level-1) + self.getWidth(root.right, level-1)

# /* функция для распечатки элементов на определенном уровне дерева */ def printGivenLevel(self, root, level): if root == None: return if level == 1: print ("%d " % root.data) elif level > 1: self.printGivenLevel(root.left, level-1); self.printGivenLevel(root.right, level-1); # /* функция для распечатки дерева */ def printLevelOrder(self, root): h = self.height(self.root) i=1 while(i<=h): self.printGivenLevel(self.root, i) i +=1

def sameTree(a, b): if a==None and b==None: return 1 elif a and b: return( a.data == b.data and sameTree(a.left, b.left) and sameTree(a.right, b.right) ) return 0

Количество узлов в бинарном дереве
Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.
Хотя с точки зрения производительности и принципов ООП, правильнее встроить счетчик в сам объект.

def size(node): if node==None:return 0; return(size(node.left) + 1 + size(node.right));

Немножко о производительности
Я протестировал наш класс на поиск. К сожалению, данная его реализация проиграла бинарному поиску по списку, описанному ранее. Я тестировал, запуская в 100000 цикле поиска элемента со значением 5 и результат нашего класса
400003 function calls (100003 primitive calls) in 3.481 seconds
против
200003 function calls in 1.791 seconds
Я считаю, что причина в рекурсивном исполнении данного метода + реализации на Python, а не Си)

1. Дж. Макконнелл - Основы современных алгоритмов.
2. Структуры данных: бинарные деревья. Часть 1
3. Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
4. Может быть полезным Обходы бинарных деревьев

Источник

Как найти высоту бинарного дерева ( поиска )

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

То есть алгоритм не привязан к значению ключей узлов рассматриваемого двоичного дерева.

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

Рисунок — стандартное анонимное бинарное дерево ( поиска )

А что, собственно, понимают под высотой бинарного дерева?

Высота двоичного дерева — это количество ветвей между его корнем и наиболее глубоко расположенным листовым узлом ( этот лист лежит на самом нижнем уровне ). Связи между узлами дерева называют ветвями ( реже ребрами ).

Для анонимного двоичного дерева, представленного на рисунке выше, высота будет иметь такое представление ( с точки зрения ветвей ):

Рисунок — анонимное двоичное дерево с высотой, выраженной через ветви

Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $4$:

Рисунок — анонимное бинарное дерево высотой $4$

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

Если бинарное поисковое дерево пустое, то есть не содержит ни одного элемента, то принято его высоту считать равной $-1$:

Если бинарное дерево состоит только из одной вершины, то по определению высота такого дерева равна $0$. Некоторые новички в программировании и структурах данных ошибочно считают, что такое дерево имеет высоту, равную $1$. Но это неправильно. Только $0$.

Рисунок — бинарное дерево высоты $0$

Хочу подытожить некоторую информацию относительно высоты бинарного дерева:

#	Количество вершин в двоичном дереве	Как рассчитывается высота дерева
$1$	$0$ ( пустое дерево )	$-1$
$2$	$1$	$0$
$3$	$>1$	по формуле

➡ Очевидно, что моя задача понять, по какой формуле следует рассчитывать высоту заданного двоичного дерева.

Учитывая, что древовидные структуры крайне удобно обрабатывать рекурсивно, то я буду мыслить в сторону рекурсивной обработки.

В результате долгих размышлений и анализа у меня получилась следующая рекурсивная функция ( каскадная рекурсия ):

➡ Подобные реализации я всегда отношу к разряду сложных, так как «за кулисами» работы рекурсии скрыто куча важнейших мелочей. Правильно и быстро программировать такие функции — достаточно сложная задача, требующая высокой квалификации программиста.

А сейчас я распишу логику этого алгоритма в табличной форме, чтобы улучшить читателям понимание принципа работы рекурсивной функции Height().

Для этого мне потребуется рассмотреть не анонимное двоичное дерево, а «нормальное», у которого узлы имеют конкретные значения ключей. Например, я хочу рассмотреть такое двоичное дерево поиска ( ключами выступают целые числа ):

Рисунок — двоичное дерево поиска ( «красный» путь показывает высоту дерева )

Анализирую логику алгоритма вычисления высоты двоичного дерева в табличной форме ( в данном случае эта форма наиболее наглядная и понятная ):

#	Ключ	Формула	Высота
$1$	$100$	max( Height( $50$ ), Height( $150$ ) ) + $1$	$?$
$2$	$50$	max( Height( $25$ ), Height( $75$ ) ) + $1$	$?$
$3$	$150$	max( Height( $125$ ), Height( $200$ ) ) + $1$	$?$
$4$	$25$	лист	$0$
$5$	$75$	max( Height( $63$ ), Height( $87$ ) ) + $1$	$?$
$6$	$125$	лист	$0$
$7$	$200$	max( Height( $190$ ), Height( NULL ) ) + $1$	$?$
$8$	$63$	лист	$0$
$9$	$87$	max( Height( NULL ), Height( $90$ ) ) + $1$	$?$
$10$	$190$	лист	$0$
$11$	$90$	лист	$0$

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

➡ Напомню, что высота несуществующего двоичного дерева составляет $-1$, то есть Height( NULL ) = $-1$.

#	Ключ	Формула	Высота
$1$	$100$	max( Height( $50$ ), Height( $150$ ) ) + $1$	$4$
$2$	$50$	max( Height( $25$ ), Height( $75$ ) ) + $1$	$3$
$3$	$150$	max( Height( $125$ ), Height( $200$ ) ) + $1$	$2$
$4$	$25$	лист	$0$
$5$	$75$	max( Height( $63$ ), Height( $87$ ) ) + $1$	$2$
$6$	$125$	лист	$0$
$7$	$200$	max( Height( $190$ ), Height( NULL ) ) + $1$	$1$
$8$	$63$	лист	$0$
$9$	$87$	max( Height( NULL ), Height( $90$ ) ) + $1$	$1$
$10$	$190$	лист	$0$
$11$	$90$	лист	$0$

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

Рисунок — бинарное дерево с простановкой высот для каждой вершины

Еще хотелось бы пояснить за вычислительную сложность рассмотренного алгоритма. Очевидно, что в процессе вычисления высоты дерева приходится обойти каждый его узел, следовательно, вычислительная сложность составляет $O( n )$, где $n$ — количество вершин дерева.

Существуют ли более эффективные алгоритмы, чем $O( n )$? Возможно, но я таких не знаю 😎

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

ВНИМАНИЕ

Для заказа программы на двоичное дерево ( поиска ) пишите на мой электронный адрес proglabs@mail.ru

Источник