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

Question

Допустим, последовательность 8, 3, 10, 7, 9, 12, 5, 11, 4, 6. В результате дерево будет выглядеть следующим образом:

 8 
    / \ 
    3 10 
    \ /\ 
     7 9 12 
    / /
    5  11 
/\ 
    4 6 

Сколько возможных способов эта последовательность может быть заказана так что конечным результатом является то же самое дерево? Например, 8, 10, 3, 7, 9, 12, 5, 11, 4, 6 - один ответ.

До сих пор я думаю, что для каждого поддерева порядок двух братьев и сестер не имеет значения. Итак, 2, 1, 3 совпадает с 2, 3, 1. Это применимо к каждому родительскому-ребру в дереве. Мне просто сложно понять рекурсию и комбинации.

Answer 1

Предполагая, что все записи в дереве разные, ответ дается формулой длины крюка для деревьев. Это зависит только от формы дерева.

Он гласит:

число возможных массивов = п!/product (число узлов поддеревьев)

где n - номер узла полного дерева. Например для дерева:

 10 
    / \ 
    5  4 
    \ /\ 
     4 1 2 
    / /
    3  1 
/\ 
    1 1 

В результате 10!/(10 * 5 * 4 * 4 * 3 * 2 * 1 * 1 * 1 * 1) = 756

Это упражнение Knuth Art of Computer Programming Том 3: поиск и сортировка.