Número de BST com chaves duplicadas - algoritmo, matemática, árvore, árvore de pesquisa binária, programação dinâmica

Se houver n vértice com chaves distintas do que o número de BST dado por Número catalão. Mas se alguns elementos são duplicados, como podemos contar o número de BST?

Minha ingênua ideia de que se tivermos k elementos iguaisentre n, que devemos dividir o número catalão em k! (permutações de k elementos). Mas se nós verificá-lo no exemplo mais simples (BST construir em [1, 1, 1]), percebemos que é uma idéia errada.

Então, como devemos levar em conta as chaves duplicadas quando contamos o número de BST?

O que é BST na minha pergunta: árvore binária onde todas as chaves no filho esquerdo menor que no root e no filho direito todas as chaves são maiores ou iguais que no root.

Respostas:

As chaves duplicadas não fazem diferença parao número de árvores distintas. Cada árvore tem uma forma distinta, então você nem precisa das chaves para diferenciá-las. Você pode remover as chaves completamente e as árvores ainda seriam todas diferentes.

Experimente com o seu exemplo simples: [1,1,1]. Você ainda pode fazer os 5 BSTs distintos com estas chaves:

    1      1      1      1      1
/      /      /             
1      1      1   1      1      1
/                       /        
1          1             1          1

EDITAR para novos requisitos:

Se as crianças esquerdas devem ser estritamente menos do queseus pais, em seguida, chaves duplicadas formam uma lista vinculada que funciona como um único nó, já que você não pode ter nenhum filho ausente nela. A lista inteira de valores iguais terá apenas uma forma, um filho à esquerda e um filho à direita:

    1
/ 
0   1

1

2

Então, neste caso, você pode simplesmente subtrair o número de chaves duplicadas.

Para N chaves com M duplicatas, ou seja, chaves exclusivas N-M, existem maneiras catalãs (N-M) de fazer a árvore.