Количество бинарных деревьев определенной высоты

Эрик Липперт — Генерация всех бинарных деревьев

Раньше я описывал небольшой алгоритм, который делал небольшие операции на бинарными деревьями. Я хотел протестировать его. Я попробовал несколько небольших тестов и они прошли, но я не был доволен. Я был почти уверен, но возможно какая-то непонятная топология бинарного дерева могла привести к ошибке. Я сообразил, что существует конечное количество бинарных деревьев данного размера. Я решил попробовать их все.

Прежде, чем начать я нуждаюсь в удобной записи бинарного дерева. Вот вершина моего дерева:

class Node
public Node Left < get ; private set ; >
public Node Right < get ; private set ; >
public Node(Node left, Node right)
this .Left = left;
this .Right = right;
>
>

* This source code was highlighted with Source Code Highlighter .

Всё очень просто: левый узел, правый узел и всё. Обратите внимание, что для большей понятности этой статьи я убрал из вершины данные, которые обычно хранятся в бинарном дереве. Давайте предположим, что это обычные числа. Я буду представлять дерево в виде компактной строки. Пустую ссылку в дереве обозначим x. Непустую вершину в моём «дереве без значений» будем обозначать ( ). Рассмотрим дерево:
1
/ \
x 2
/ \
x x

Вершина 2 имеет два нулевых потомка и будет обозначена (xx). Вершина 1 имеет пустого левого потомка, а правым потомком является вершина 2. Таким образом дерево обозначится, как (x(xx)). Какой же в этом смысл? Мы можем написать небольшой рекурсивный код, который строит такие строки:

public static string BinaryTreeString(Node node)
var sb = new StringBuilder ();
Action f = null ;
f = n =>
if (n == null )
sb.Append( «x» );
else
sb.Append( «(» );
f(n.Left);
f(n.Right);
sb.Append( «)» );
>
>;
f(node);
return sb.ToString();
>

* This source code was highlighted with Source Code Highlighter .

Как же пронумеровать все возможные бинарные деревья данного размера? Мы сделаем это рекурсивно.

Существует ровно одно дерево из 0 вершин. Оно обозначается x. Это база.

Теперь выберем номер. Например, четыре. Мы хотим пронумеровать все деревья из четырёх непустых вершин. Предположим, что мы уже пронумеровали все вершины из трёх, двух и одной вершины. Обозначим множество бинарных деревьев из n вершин как B(n). Положим, что мы создаём все возможные комбинации B(x) и B(y), имея ввиду, что B(x) соответствуют левому потомку корня, а B(y) – правому потомку корня. Я буду записывать B(x)B(y). В этой записи деревья с четырьмя непустыми вершинами могут быть разбиты на четыре множества: B(0)B(3), B(1)B(2), B(2)B(1), B(3)(0).

Это достаточно просто обобщить: мы можем пронумеровать все деревья с k вершинами, перебирая каждый раз k случаев, в которых мы рассматриваем задачи более мелкого размера. Замечательное рекурсивное решение. Рассмотрим код:

static IEnumerable AllBinaryTrees( int size)
if (size == 0)
return new Node[] < null >;
return from i in Enumerable.Range(0, size)
from left in AllBinaryTrees(i)
from right in AllBinaryTrees(size — 1 — i)
select new Node(left, right);
>

* This source code was highlighted with Source Code Highlighter .

Заметим, что LINQ делает алгоритм более похожим на его описание, чем эквивалентная программа с большим количеством циклов.

И действительно, если мы запустим:

foreach ( var t in AllBinaryTrees(4))
Console .WriteLine(BinaryTreeString(t));

* This source code was highlighted with Source Code Highlighter .

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

Сколько таких деревьев? Похоже их может быть довольно много.

Количество бинарных деревьев из n вершин называется числом Каталана, которое обладает множеством интересных свойств. N-ое число Каталана считается по формуле (2n)! / (n+1)!n!, которая растёт экспоненциально. (В Википедии предложено несколько доказательств, что это форма числа Каталана.) Число бинарных деревьев данного размера

0 1
1 1
2 2
4 14
8 1430
12 208012
16 35357670

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

Я озадачу Вас: положим мы забыли о бинарных деревьях и на текущий момент рассмотрим произвольные деревья. Произвольное дерево может иметь 0, 1 или любое конечное количество потомков. Пусть непустое произвольное дерево запишется списком потомков в скобках. Таким образом <>>> – это дерево

Т.к. вершины 2, 3 и 5 не имеют потомков, то они будут записываться как <>. Какой смысл? Обратите внимание на порядок. <>>> и ><>> – это разные деревья с похожей структурой.

Моя первая задача: чего больше произвольных деревьев из n вершин или бинарных деревьев из n вершин.
Моя вторая задача: можете ли вы разработать механизм нумерации произвольных деревьев?

Источник

Количество бинарных деревьев определенной высоты

На этом шаге мы рассмотрим число бинарных деревьев .

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

Обозначим t n — число различных бинарных деревьев, содержащих n вершин. Под различными деревьями мы понимаем в том числе учет свойства вершины быть левым или правым потомком. Таким образом, симметричные деревья, изоморфные с точки зрения теории графов, являются различными. Например, вырожденные деревья, представляющие собой цепи левых и правых потомков — различны с нашей точки зрения, хотя и изоморфны. Имеет место формула:

которую можно объяснить следующим образом.

Пусть t k обозначает количество возможных левых поддеревьев, содержащих k вершин, t n-k-1 — количество соответствующих правых поддеревьев, содержащих n-k-1 вершину ( k вершин в левом поддереве и одна вершина — корень). Левое поддерево может быть пустым, разумеется, существует только один вариант пустого дерева, т. е. t 0 =1 . При этом в правом поддереве n-1 вершина и имеется t n способ построить такое дерево. Общее количество способов построить дерево, сохраняя заданное соотношение количеств вершин в левом и правом поддеревьях k и n-k-1 , равно t k t n-k-1 . Суммируя по всем возможным значениям k , получаем количество t n деревьев с n вершинами.

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

t1 = t0 = 1, t2 = t1t0 + t0t1 = 2, t3 = t0t2 + t1t1 + t2t0 = 5 и т.д.

В частности, t 4 = 14, t 5 = 42, t 6 = 132, t 7 = 429 . Таким способом можно вычислить количество бинарных деревьев с любым числом вершин, но сложность и громоздкость вычислений возрастают с ростом n . Хотелось бы получить результат в виде явной зависимости t n от параметра n без использования значений t n-i .

Для этого используется производящая функция членов последовательности , где z — некая формальная переменная. Отыскивается она следующим образом. Вместо суммы для t n запишем сумму для t n+1 :

Правая часть принимает классический вид свертки двух последовательностей (в данном случае — это свертка последовательности с самой собой) и ее производящая функция равна Т 1 (z) в соответствии с теорией z -преобразований . Левая часть задает член последовательности , сдвинутой относительно последовательности на одну позицию и ее производящая функция по правилам z -преобразований может быть определена как . Получили уравнение:

для определения неизвестной функции T(z) , которое имеет решение:

Разложение его в ряд по степеням z в районе точки z = 0 имеет вид:

На следующем шаге мы рассмотрим число вырожденных деревьев .

Источник

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

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

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

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

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

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

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

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

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

Следовательно, рассматриваемое анонимное бинарное дерево ( поиска ) имеет высоту, равную $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

Источник