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

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

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

Спасибо заранее!

Ответы

Ответ 1

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

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

Наложение полигонов на треугольники

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

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

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

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

2x2 grid = > 2 пути

  _|       |
_|       __|

3x3 сетка = > 5 путей

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

4x4 grid = > 14 путей
5x5 сетка = > 42 пути

и т.д.

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

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

Ответ 2

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

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

Ответ 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);
}