Блог

Изучая каталонские числа, некоторые из приложений, с которыми я столкнулся, были:

1. ни одно из возможных бинарных деревьев поиска с использованием n узлов.
2. нет способов нарисовать непересекающиеся хорды, используя 2 * n точек на окружности.
3. нет способов упорядочить n пар круглых скобок.

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

Не удалось найти ни одного другого полезного ресурса в Интернете, который объясняет часть «КАК«. Все просто говорят, что это решение.

Может кто-нибудь, пожалуйста, объяснить.

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

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

Вот способ преобразовать строку из n пар круглых скобок, которые правильно сопоставлены, в двоичное дерево с n внутренними узлами. Рассмотрим крайнюю левую круглую скобку, которая будет левой круглой скобкой, вместе с соответствующей ей правой круглой скобкой. Превратите строку в узел двоичного дерева. Вложенная строка, которая находится внутри рассматриваемых в данный момент круглых скобок, становится левым дочерним элементом этого узла, а вложенная строка, которая находится после (справа) рассматриваемой в данный момент правой круглой скобки, становится правым дочерним элементом. Одна или обе вложенные строки могут быть пустыми, и рассматриваемые в данный момент круглые скобки просто удаляются. Если какая-либо из вложенных строк не пуста, продолжайте эту процедуру рекурсивно, пока не будут удалены все круглые скобки.

Вот два примера. Давайте начнем со строки ((())) . Мы начинаем с

Рассмотренные круглые скобки являются самыми внешними. Это становится

(Я не стал утруждать себя рисованием внешних конечных узлов) затем

тогда

это самое левое двоичное дерево Википедии с 3 внутренними узлами.

Теперь давайте сделаем еще одну строку, (())() . Мы начинаем с

Опять же, рассмотренные скобки являются самыми внешними. Это преобразуется в

И теперь рассмотренные круглые скобки — это первые две, а не самые внешние. Это становится

который, наконец, становится

это второе двоичное дерево в списке Википедии.

Я надеюсь, теперь вы понимаете. Вот список всех пяти возможных строк из 3 пар круглых скобок, которые правильно спарены, за которыми следует список бинарных деревьев Википедии. Теперь эти списки соответствуют друг другу.

     ((()))       (()())        (())()       ()(())       ()()()