Все существующие двоичные деревья
Недавно я написал небольшой алгоритм, который выполняет некоторые операции c двоичными деревьями. Я хотел его протестировать. Я создал несколько небольших тестов, которые выполнились успешно, но не был полностью удовлетворен. Я был, в общем-то, уверен, но что если существуют странные топологии двоичных деревьев, о которых я не подумал, и которые приведут к ошибке. Я решил, что должно существовать конечное количество топологий двоичных деревьев определенного размера. И я решил попробовать их все.
Прежде, чем продолжить, мне нужна краткая нотация записи двоичного дерева. Вот узел моего дерева:
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;
}
}
Всё довольно просто: левый потомок, правый потомок и всё. Обратите внимание, что ради простоты я убрал данные, которые обычно хранятся в узле дерева. Пока давайте предположим, что в качестве данных хранятся целые числа. Еще одним интересным моментом является то, как я представил дерево в виде очень короткой строки. Пустой узел (null tree node) дерева[1] обозначим x. А непустой узел моего «дерева без данных» будет представлен в виде: (left right) (т.е. в виде круглых скобок, в которых будет вначале представлен левый потомок, а затем правый). Рассмотрим следующее дерево:
1
/ \
x 2
/ \
x x
Узел 2 содержит два пустых дочерних узла и будет обозначен (xx). Узел 1 содержит пустого потомка слева и узел 2 справа, поэтому будет обозначен (x(xx)). Разумно? Мы можем написать небольшой рекурсивный код, который будет создавать такие строки:
public static string BinaryTreeString(Node node)
{
var sb = new StringBuilder();
Action<Node> 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();
}
Как мы можем перечислить все возможные двоичные деревья определенного размера? Думаю, рекурсивно.
Существует только одно дерево с нулевым количеством непустых узлов: 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 случаев, каждый из которых требует от нас решения аналогичной задачи на некотором дереве, состоящем из количества узлов меньшим, чем k. Эта задача идеально подходит для рекурсивного решения. Вот код:
static IEnumerable<Node> 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);
}
Еще раз замечу, что алгоритм решения на основе LINQ, выглядит куда более похожим на свою спецификацию, чем эквивалентное решение на основе нескольких вложенных циклов.
И, конечно, если мы выполним:
foreach (var t in AllBinaryTrees(4))
Console.WriteLine(BinaryTreeString(t));
то получим все деревья, состоящие из четырех ненулевых узлов.
(x(x(x(xx))))
(x(x((xx)x)))
(x((xx)(xx)))
(x((x(xx))x))
(x(((xx)x)x))
((xx)(x(xx)))
((xx)((xx)x))
((x(xx))(xx))
(((xx)x)(xx))
((x(x(xx)))x)
((x((xx)x))x)
(((xx)(xx))x)
(((x(xx))x)x)
((((xx)x)x)x)
Теперь у меня есть инструмент генерации различных топологий деревьев, который можно использовать для тестирования алгоритма.
Так сколько же существует таких деревьев? Похоже, их может быть довольно много.
Количество топологий двоичных деревьев, состоящих из n узлов, определяется числами Каталана, у которых есть множество интересных свойств. n-ое число Каталана вычисляется по формуле (2n)! / (n+1)!n!, и растет экспоненциально. (Соответствующая статья в Википедии содержит несколько доказательств того, что это самая короткая форма вычисления числа Каталана.) Количество двоичных деревьев заданного размера следующее:
0 |
1 |
1 |
1 |
2 |
2 |
4 |
14 |
8 |
1430 |
12 |
208012 |
16 |
35357670 |
Так что, мой план попробовать все деревья определенного размера, видимо, не очень хорош. При количестве узлов более 15 мы получаем слишком большое число комбинаций, чтобы попытаться проверить их все за короткий промежуток времени. Тем не менее, я считаю, что иметь такой инструмент очень удобно.
Вот вам задача: давайте забудем на секунду о двоичных деревьях и рассмотрим произвольные деревья. Из узла произвольного дерева может выходить 0, 1 или любое конечное количество ветвей. Давайте непустое произвольное дерево будем записывать в виде списка потомков в скобках. Таким образом, {{}{}{{}}} – это дерево
1
/|\
2 3 4
|
5
Поскольку узлы 2, 3 и 5 не содержат потомков, они будут записываться как {}. Разумно? Обратите внимание, что порядок важен; {{}{}{{}}} и {{}{{}}{}} – это разные деревья с похожей структурой.
Мой первый вопрос: при заданном количестве узлов n, количество каких деревьев больше – произвольных или двоичных? И второй вопрос: можете ли вы разработать механизм перечисления произвольных деревьев?
[1] Пустой узел дерева не содержит ни левого, ни правого дочерних узлов и называется также листовым узлом (leaf node). – Примеч. перев.