Комментарии 12
НЛО прилетело и опубликовало эту надпись здесь
Это перевод.
Данная статья — перевод на русский статьи Эрика Липперта. Такого рода вопросы — это к нему.
Вы путаете n-арное дерево и дерево общего вида (произвольное).
В n-арном дереве потомки имеют порядок (позицию): 1й, 2й, 4й, n-й. Какие-то позиции могут отсутствовать точно также, как в двоичном может не быть правого или левого потомка.
В произвольном дереве просто есть список потомков.
В n-арном дереве потомки имеют порядок (позицию): 1й, 2й, 4й, n-й. Какие-то позиции могут отсутствовать точно также, как в двоичном может не быть правого или левого потомка.
В произвольном дереве просто есть список потомков.
Эти скобочки сломали мне мозг.
Очевидно, что это не может быть совпадением.
Гм, конечно не может.
Давайте будем искать F(n) — число двоичных деревьев из n вершин. Предположим, что мы умеем решать задачи меньшей размерности чем n. Пусть в левом поддереве i вершин, тогда в правом (n-1-i) — значит всего таких деревьев F(i)*F(n-1-i). Число i изменяется от 0 до n-1, а значит ответ — сумма указаных произведений для i от 0 до n-1, что совпадает с формулой числа Каталана, что и требовалось.
Перечитал статью с утра и понял, что число двоичных деревьев искалось в прошлой статье (хотя почему-то не обосновалось). Потому мой комментарий надо отправить к туда. :-)
Очень понравилось, кстати, превращение произвольных неизоморфных деревьев в двоичные «с точки зрения структур данных». Если держать его в голове, то обоснование выше легко превращается в искомое C(n-1).
Очень понравилось, кстати, превращение произвольных неизоморфных деревьев в двоичные «с точки зрения структур данных». Если держать его в голове, то обоснование выше легко превращается в искомое C(n-1).
Интересная статья.
А блоки из Тетриса на картинках специально?
А блоки из Тетриса на картинках специально?
Всё же, надо заметить, что в математике дерево — это связный граф без циклов. И два дерева (собственно, как и просто два графа) считаются изоморфными, если можно пронумеровать вершины обоих так, что если вязть два номера, то вершины под этими номера одновременно соединены или не соединены ребром в обоих деревьях (графах). Поэтому 2, 3 и 4 деревья у Вас на рисунке — изоморфны, т.е., неразличимы с точки зрения теории графов.
Поэтому имеет смысл уточнить, что здесь считается произвольным деревом.
Поэтому имеет смысл уточнить, что здесь считается произвольным деревом.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Эрик Липперт — Генерация всех произвольных деревьев