Возможное количество бинарных деревьев поиска, которые могут быть созданы с помощью N ключей, определяется N-м каталонским номером. Зачем?

Question

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

Я пытался определить, почему это так; неспособный найти что-либо, что могло бы даже попытаться объяснить это интуитивно, я прибегаю к коллективному знанию SO. Я нашел другие способы вычисления количества возможных деревьев, но они казались менее интуитивными, и не было предложено никаких объяснений, кроме как их использовать. Кроме того, на вики-странице (эта ссылка выше) даже показано изображение возможных древовидных образований с 3 клавишами, что заставило бы меня думать, что есть хорошее и аккуратное объяснение, которое нужно услышать (что, разумеется, не включено в статью ).

Заранее спасибо!

Answer 1

Поскольку в статье в Википедии, на которую вы ссылались, четыре доказательства , похоже, вы не ищете математического объяснения соответствия между каталонскими числами и перестановками двоичного дерева.

Итак, вместо этого есть два способа интуитивно представить себе, как каталонская последовательность (1, 2, 5, 14, 42, ...) возникает в комбинаторных системах.

Нарезание кубиками многоугольников

Для многоугольника со стороны N , сколько способов вы можете нарисовать разрезы между вершинами, которые полностью разрезают многоугольник на треугольники?

• Треугольник (N = 3): 1 (это уже треугольник)
• Квадрат (N = 4): 2 (можно разрезать по любой диагонали)
• Пентагон (N = 5): 5 (Две линии разреза, исходящие из вершины. Пять вершин на выбор)
• Шестиугольник (N = 6): 14 (попробуйте нарисовать)
• ... и т. Д.

Рисование пути через сетку без пересечения диагонали

В этом случае число уникальных путей является каталонским числом.

2x2 grid => 2 пути

  _|       |
_|       __|

3x3 grid => 5 путей

    _|       |       _|         |         |
  _|      _ _|      |          _|         |
_|      _|       _ _|      _ _|      _ _ _|

4x4 сетка => 14 путей
Сетка 5х5 => 42 дорожки

и т. Д.

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

Ваше желание не просто слепо принять соответствие между деревом и последовательностью достойно восхищения. К сожалению, в этом обсуждении трудно пойти намного дальше (и объяснить, почему каталонская формула «такова», как она есть), не прибегая к биномиальной математике. Обсуждение в Википедии биномиальных коэффициентов является хорошей отправной точкой, если вы хотите глубже понять комбинаторику (которая включает в себя подсчет перестановок ).

Answer 2

каталанский http://www.nohre.se/publicImages/catalan.png

Любое двоичное дерево поиска может быть закодировано путем посещения всех узлов предварительного порядка и кодирования 1 для каждого родителя и 0 для каждого листа. Если дерево имеет n родителей, у него будет n + 1 лист, и, следовательно, двоичный код будет иметь n 1: s и (n + 1) 0: s. Более того, любой префикс кода будет иметь по крайней мере столько же 1: s, сколько и 0: s. Следовательно, число возможных деревьев равно числу путей ниже диагонали.

Answer 3

Ну вот рекурсивное решение для подсчета деревьев ...

int countTrees(int numkeys){

if(numkeys > 1){
    int i =1;
    int sum=0;

    for(i = 1; i <= numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);
}