Énumérer les arbres de recherche

Question

Selon this question le nombre de différents arbres de recherche d'une certaine taille est égal à un nombre catalan. Est-il possible de énumérer ces arbres? Autrement dit, quelqu'un peut-il mettre en œuvre les deux fonctions suivantes:

Node* id2tree(int id); // return root of tree 

int tree2id(Node* root); // return id of tree 

(je demande parce que le code binaire pour l'arbre (se l'une des réponses à this question) serait un code très efficace pour représenter arbitrairement grands nombres entiers de inconnue gamme, à savoir un code de longueur variable pour les entiers

0 -> 0 
1 -> 100 
2 -> 11000 
3 -> 10100 
4 -> 1110000 
5 -> 1101000 
6 -> 1100100 
7 -> 1011000 
8 -> 1010100 
etc 

avis que le nombre d'entiers de chaque longueur de code est égal à 1, 1, 2, 5, .. (la séquence catalan).)

Answer 1

Pour les arbres binaires généraux (non-search) je peux voir comment cela serait possible, car lors de la construction de l'arbre il y a trois choix (le nombre d'enfants) pour chaque nœud, seulement limité par le total de N. pourrait trouver un moyen de représenter un tel arbre comme une séquence de choix (en construisant l'arbre dans un ordre spécifique), et représenter cette séquence comme un nombre de base-3 (ou peut-être une base variable serait plus appropriée). Mais pour les arbres de recherche binaires, toutes les organisations d'éléments ne sont pas acceptables. Vous devez également obéir aux contraintes d'ordre numériques. D'autre part, puisque l'insertion dans un arbre de recherche binaire est bien définie, vous pouvez représenter une arborescence entière de N éléments en ayant une liste de N nombres dans un ordre d'insertion spécifique. En permutant les nombres dans un ordre différent, vous pouvez générer un arbre différent. Les permutations sont bien sûr facilement comptées en utilisant des nombres à base variable: Vous avez N choix pour le premier élément, N-1 pour le second, etc. Cela vous donne une séquence de N nombres que vous pouvez encoder comme un nombre avec une base variant de N à 1. L'encodage et le décodage de base variable en binaire ou décimal sont trivialement adaptés à partir d'un algorithme de conversion à base fixe normale. (Ceux qui utilisent des opérations de module et de division).

Vous pouvez donc convertir un nombre de et vers une permutation, et étant donné une liste de nombres, vous pouvez convertir une permutation (de cette liste) depuis et vers un arbre de recherche binaire. Maintenant, je pense que vous pourriez obtenir tous les arbres de recherche binaires possibles de taille N en permutant seulement les entiers 1 à N, mais je ne suis pas entièrement sûr, et en essayant de prouver que c'est un peu trop pour ce post. J'espère que c'est un bon point de départ pour une discussion.

Answer 2

Il devrait être possible de convertir l'ID en arbre et en arrière.

L'identifiant et bitstrings être:

0 -> 0 
1 -> 100 
2 -> 11000 
3 -> 10100 
4 -> 1110000 
5 -> 1101000 
6 -> 1100100 
7 -> 1011000 
8 -> 1010100 

Considérons d'abord le fait que, compte tenu d'un bitstring, on peut facilement passer à l'arbre (une méthode récursive) et vice-versa (précommande, sortie 1 pour les parents et 0 pour feuille).

Le principal défi consiste à essayer de mapper l'identifiant à la chaîne de bits et vice versa.

Supposons une liste des arbres de n nœuds comme suit:

Left sub-tree n-1 nodes, Right sub-tree 0 nodes. (Cn-1*C0 of them) 
Left sub-tree n-2 nodes, Right sub-tree 1 node. (Cn-2*C1 of them) 
Left sub-tree n-3 nodes, right sub-tree 2 nodes. (Cn-3*C2 of them) 
... 
... 
Left sub-tree 0 nodes, Right sub-tree n-1 nodes. (C0*Cn-1 of them) 

Cr = rth catalan number. 

L'énumération que vous avez donné semble provenir de la procédure suivante: nous gardons le sous-arbre gauche fixe, énumérer les bons sous-arbres. Passez ensuite à la sous-arborescence suivante, énumérer les sous-arborescences de droite, et ainsi de suite. Nous commençons par la taille maximale sous-arbre gauche, puis le suivant est la taille maximale -1, etc

Donc disons que nous avons un id = S dire. Nous trouvons d'abord un n tel que

C0 + C1 + C2 + ... + Cn < S < = C0 + C1 + C2 + ... + 1 + Cn

Alors S correspondrait à un arbre avec n + 1 nœuds. Donc, vous considérez maintenant P = S - (C0 + C1 + C2 + ... + Cn), qui est la position dans l'énumération des arbres de n + 1 nœuds.

Maintenant, nous trouver un r tel que * C0 + Cn Cn-1 * C1 + .. + Cn-r Cr < P < = C0 + Cn Cn-1 * C1 + .. + r-Cn + 1 * Cr-1

Ceci nous indique combien de nœuds le sous-arbre gauche et le sous-arbre droit ont. Considérant P - Cn * C0 + Cn-1 * C1 + .. + Cn-r * Cr, nous pouvons maintenant déterminer la position exacte de l'énumération de sous-arbres à gauche (en ne considérant que les arbres de cette taille) et la sous-arborescence exacte position d'énumération et forme récursivement la chaîne de bits. Le mappage de la chaîne de bits à l'ID doit être similaire, car nous savons à quoi ressemblent les sous-arborescences gauche et droite, tout ce que nous devons faire est de trouver les positions correspondantes et faire un peu d'arithmétique pour obtenir l'ID.

Vous ne savez pas à quel point c'est utile. Vous travaillerez avec des nombres assez énormes tout le temps.