Эрик Липперт — Генерация всех бинарных деревьев
Раньше я описывал небольшой алгоритм, который делал небольшие операции на бинарными деревьями. Я хотел протестировать его. Я попробовал несколько небольших тестов и они прошли, но я не был доволен. Я был почти уверен, но возможно какая-то непонятная топология бинарного дерева могла привести к ошибке. Я сообразил, что существует конечное количество бинарных деревьев данного размера. Я решил попробовать их все.
Прежде, чем начать я нуждаюсь в удобной записи бинарного дерева. Вот вершина моего дерева:
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 вершинами равно C(n), где C(n) – это n-ое число Каталана. Я заинтересовался чего больше: произвольных деревьев из n вершин или бинарных деревьев из n вершин. Ответ может вас удивить, он не лежит на поверхности.
Распространённый ответ на этот вопрос я получу сразу: «Разумеется, произвольных деревьев больше, т.к. бинарное дерево – это частный случай произвольного дерева». Можете ли вы сказать, почему это неверно? Бинарных деревьев больше, чем произвольных деревьев! Существует два бинарных дерева из двух вершин: одно с левым потомком ребёнком корня, а другое – с правым потомком корня. Но есть только одно произвольное дерево с двумя вершинами, в нём нет разницы между «левым» и «правым» потомком.
Как оказалось, ответ на мой вопрос (кроме вырожденных случаев деревьев из нуля вершин и одной вершины) заключается в том, что бинарных деревьев из n вершин всегда больше, чем произвольных деревьев из n вершин.
Если вы исследуете эту задачу, то заметите интересный факт: число произвольных деревьев из n вершин равно С(n-1). Существует 14 бинарных деревьев из 4 вершин и 14 произвольных деревьев из 5 вершин. Существует 1430 бинарных деревьев из 8 вершин и 1430 произвольных деревьев из 9 вершин. Чудно!
Очевидно, что это не может быть совпадением. Должно быть взаимнооднозначное соответствие между бинарными деревьями размера n и произвольными деревьями размера n+1. И в самом деле, в существовании соответствия легко убедиться, если посмотреть на картинки. Слева находится изображение первых 5 бинарных деревьев размера 4, а рядом – пять соответствующих произвольных деревьев размера 5.
Чтобы сделать соответствие более понятным посмотрим на изображение справа. Для перехода из бинарного дерева в соответствующее произвольное дерево нужно повернуть бинарное дерево на 45 градусов против часовой стрелки, добавить сверху корень, а затем исправить все горизонтальные линии так, чтобы они указывали на родителей.
Или, с точки зрения структур данных, можно представить каждую вершину в произвольном дереве, как ссылку на первого ребёнка и ссылку на следующего брата. Получилось в точности бинарное дерево, только вместо надписей на вершинах «первый ребёнок» и «следующий брат» нужно написать «левый потомок» и «правый потомок». Есть только одно отличие между бинарным деревом и произвольным деревом в этой системе – правый потомок корня всегда пуст, т.к. корень не имеет братьев. Теперь вы ведете, что отличие между бинарным деревом и произвольным деревом состоит в именах полей в структуре данных, а значит мы показали взаимнооднозначное соответствие между ними.
Таким образом, мы получили решение второй части моей задачи. У нас есть механизм, который пронумеровывает все бинарные деревья и взаимнооднозначное соответствие между бинарными деревьями и произвольными деревьями. Все что осталось сделать – получить механизм превращения бинарного дерева в соответствующее произвольное дерево. Оставим это в качестве упражнения, но ради интереса приведём здесь механизм, который превращает бинарное дерево в строковое представление соответствующего произвольного дерева, использую компактный синтаксис для произвольного дерева, о котором я говорил в прошлый раз.
public static string TreeString(Node node)
// Получение строкового представления произвольного дерева
// по бинарному дереву.
var sb = new StringBuilder ();
Action f = null ;
f = n =>
sb.Append( » for (Node child = n.Left; child != null ; child = child.Right)
f(child);
sb.Append( «>» );
>;
f( new Node(node, null ));
return sb.ToString();
>
* This source code was highlighted with Source Code Highlighter .
Для получения всех деревьев размера 5, мы переберём все бинарные деревья размера 4 и выведем соответствующие произвольные деревья размера 5.
foreach ( var n in AllBinaryTrees(4))
Console .WriteLine(TreeString(n));
* This source code was highlighted with Source Code Highlighter .
Обратите внимание, что если вы уберёте крайние скобки, то мы получим решение задачи «напечатать все правильные комбинации из четырёх пар скобок»! Если вы пронумеруете все бинарные деревья, тогда вы пронумеруете все решения множества различных эквивалентных задач.
В следующий раз: что мы можем сгенерировать ещё?
Источник