Langue C
  1. Langue C
  3. Comment générer des arbres AVL non équilibrés au maximum
Intereting Posts
types en conflit erreur lors de la compilation du programme c en utilisant gcc Conversion d’un int en une valeur hexadécimale de 2 octets en C Existe-t-il un outil pour tester la concision du programme c? Quel est un exemple dans lequel connaître C me fera écrire un meilleur code dans n’importe quelle autre langue? Erreur de liaison LNK2005 lors de la tentative de compilation de plusieurs fichiers CUDA Jeu sous Linux: Changer d’images: imprimer sur du texte déjà imprimé Reprise de ? Nprintf après avoir atteint la limite has_zero et find_zero dans word_at_a_time.h, utilisés pour Quelle est la différence entre les déclarations suivantes en C? fonction de pow en C Compilateur C à IEC 61131-3 IL déséquilibré nested pour les boucles dans openmp Générateur de permutation sur C utiliser fork dans un if-statement / processus de gestion Encodage d’un stream de données en même temps que la vidéo dans FFMPEG

Comment générer des arbres AVL non équilibrés au maximum

J’ai écrit une bibliothèque d’arbres AVL en langage C sous forme de conteneurs sortingés à usage général . À des fins de test, j’aimerais pouvoir remplir un arbre de manière à ce qu’il soit déséquilibré au maximum, c’est-à-dire qu’il ait la hauteur maximale pour le nombre de nœuds qu’il contient.

Les arbres AVL ont la propriété intéressante que si, à partir de l’arbre vide, vous insérez des nœuds dans l’ordre croissant (ou décroissant), l’arbre est toujours exactement équilibré (c’est-à-dire qu’il a sa hauteur minimale pour un nombre donné de nœuds). Une séquence de clés entières qui génère un arbre AVL exactement équilibré T n pour chaque nombre de nœuds n, à partir de l’arbre vide T 0 , est simplement:

  • k 1 = 0
  • k n + 1 = k n +1, c’est-à-dire que k n = n-1

Je cherche une séquence (espérons-le simple) de clés entières qui, lorsqu’elles sont insérées dans l’arbre T 0 initialement vide, génèrent des arbres AVL T 0 , …, T n qui sont tous au maximum non équilibrés.

Je serais également intéressé par une solution où seul le dernier arbre, T n , est au maximum déséquilibré (le nombre de nœuds n serait un paramètre de l’algorithme).

Une solution répondant à la contrainte

  • max (k 1 , …, k n ) – min (k 1 , …, k n ) + 1 ≤ 2 n

est préférable, mais pas ssortingctement requirejse. Une plage de clé de 4 n au lieu de 2 n peut constituer une cible raisonnable.

Je n’ai rien trouvé sur Internet concernant la génération, par insertion, d’arbres AVL de hauteur maximale. Bien sûr, la séquence d’arbres générés que je recherche inclura tous les arbres dits de Fibonacci, qui sont les arbres AVL d’une profondeur donnée avec le nombre minimal de nœuds. Bizarrement, Wikipedia anglais ne mentionne même pas les arbres de Fibonacci (ni les chiffres de Fibonacci!) Dans l’article sur les arbres AVL, alors que le Wikipedia allemand a un très bon article qui leur est entièrement consacré. Mais je suis toujours dans le noir concernant ma question.

Les bidouilles en langage C sont les bienvenues.

Solution de base

Les arbres de Fibonacci ont plusieurs propriétés qui peuvent être utilisées pour former un arbre de Fibonacci compact:

  1. Chaque nœud d’un arbre de Fibonacci est lui-même un arbre de Fibonacci.
  2. Le nombre de nœuds dans un arbre de Fibonacci de hauteur n est égal à F n + 2 – 1.
  3. Le nombre de nœuds entre un nœud et son enfant de gauche est égal au nombre de nœuds dans l’enfant de droite du nœud de gauche.
  4. Le nombre de noeuds entre un noeud et son enfant de droite est égal au nombre de noeuds de l’enfant de gauche du noeud.

Sans perte de généralité, nous supposerons que notre arbre de Fibonacci possède la propriété supplémentaire suivante:

  1. Si un nœud a la hauteur n, l’enfant gauche a la hauteur n-2 et l’enfant droit a la hauteur n-1.

En combinant ces propriétés, nous trouvons que le nombre de nœuds entre un nœud de hauteur n et ses enfants gauche et droit est égal à F n-1 – 1, et nous pouvons utiliser ce fait pour générer un arbre de Fibonacci compact: 

 static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170}; void fibonacci_subtree(int root, int height, int *fib) { if (height == 1) { insert_into_tree(root); } else if (height == 2) { insert_into_tree(root + *fib); } else if (height >= 3) { fibonacci_subtree(root - *fib, height - 2, fib - 2); fibonacci_subtree(root + *fib, height - 1, fib - 1); } } ... for (height = 1; height <= max_height; height++) { fibonacci_subtree(0, height, fibs + max_height - 1); }

Cet algorithme génère le nombre minimum de nœuds possibles pour une hauteur donnée, ainsi que la plage minimale possible. Vous pouvez déplacer la plage en faisant en sorte que le nœud racine soit différent de zéro.

Algorithme de remplissage compact

La solution de base ne produit que des arbres de Fibonacci, qui ont toujours F n + 2 - 1 nœuds. Que faire si vous souhaitez générer une arborescence non équilibrée avec un nombre de nœuds différent tout en minimisant la plage?

Dans ce cas, vous devez générer le prochain arbre plus grand de Fibonacci avec quelques modifications:

  • Un certain nombre d'éléments à la fin de la séquence ne seront pas insérés.
  • Ces éléments créeront des lacunes, et leur localisation doit être suivie.
  • La différence entre les nœuds doit être réduite de manière appropriée.

Voici une approche qui tire toujours parti de la nature récursive de la solution: 

 void fibonacci_subtree(int root, int height, int *fib, int num_gaps, bool prune_gaps) { if(height < 1) return; if(prune_gaps && height <= 2) { if(!num_gaps) { if(height == 1) { insert_into_tree(root); } else if(height == 2) { insert_into_tree(root + *fib); } } return; } if(height == 1) { insert_into_tree(root); } else { int max_rr_gaps = *(fib - 1); int rr_gaps = num_gaps > max_rr_gaps ? max_rr_gaps : num_gaps; num_gaps -= rr_gaps; int max_rl_gaps = *(fib - 2); int rl_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps; num_gaps -= rl_gaps; int lr_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps; num_gaps -= lr_gaps; int ll_gaps = num_gaps; fibonacci_subtree(root - *fib + lr_gaps, height - 2, fib - 2, lr_gaps + ll_gaps, prune_gaps); fibonacci_subtree(root + *fib - rl_gaps, height - 1, fib - 1, rr_gaps + rl_gaps, prune_gaps); } }

La boucle principale est légèrement plus compliquée pour accueillir une plage de clés arbitraire: 

 void compact_fill(int min_key, int max_key) { int num_nodes = max_key - min_key + 1; int *fib = fibs; int max_height = 0; while(num_nodes > *(fib + 2) - 1) { max_height++; fib++; } int num_gaps = *(fib + 2) - 1 - num_nodes; int natural_max = *(fib + 1) - 1; int max_r_gaps = *(fib - 1); int r_gaps = num_gaps > max_r_gaps ? max_r_gaps : num_gaps; natural_max -= r_gaps; int root_offset = max_key - natural_max; for (int height = 1; height <= max_height; height++) { fibonacci_subtree(root_offset, height, fibs + max_height - 1, num_gaps, height == max_height); } }

Solution de forme fermée

Si vous examinez les différences entre chaque paire de mots générés par la solution de base, vous constatez qu'ils alternent entre deux éléments séquentiels de la séquence de Fibonacci. Ce motif alterné est défini par le mot de Fibonacci :

Un mot de Fibonacci est une séquence spécifique de chiffres binarys (ou de symboles de n'importe quel alphabet à deux lettres). Le mot de Fibonacci est formé par concaténation répétée de la même manière que les nombres de Fibonacci sont formés par addition répétée.

Il s'avère qu'il existe une solution fermée pour le mot Fibonacci : 

 static double phi = (1.0 + sqrt(5.0)) / 2.0; bool fibWord(int n) { return 2 + floor(n * phi) - floor((n + 1) * phi); }

Vous pouvez utiliser cette solution fermée pour résoudre le problème en utilisant deux boucles nestedes: 

 // Used by the outer loop to calculate the first key of the inner loop int outerNodeKey = 0; int *outerFib = fibs + max_height - 1; for(int height = 1; height <= max_height; height++) { int innerNodeKey = outerNodeKey; int *smallFib = fibs + max_height - height + 3; // Hat tip: @WalterTross for(int n = fibs[height] - 1; n >= 0; n--) { insert_into_tree(innerNodeKey); // Use closed-form expression to pick between two elements of the Fibonacci sequence bool smallSkip = 2 + floor(n * phi) - floor((n + 1) * phi); innerNodeKey += smallSkip ? *smallFib : *(smallFib + 1); } if(height & 0x1) { // When height is odd, add *outerFib. outerNodeKey += *outerFib; } else { // Otherwise, backtrack and reduce the gap for next time. outerNodeKey -= (*outerFib) << 1; outerFib -= 2; } }

J’ai trouvé cette réponse à ma question, mais j’espère toujours qu’un algorithme plus simple et, en particulier, plus efficace dans le temps et non moins dans l’utilisation de l’espace, pourra être trouvé, avec de meilleures propriétés de plage de clés également.

L’idée est de générer les arbres de Fibonacci jusqu’à une hauteur donnée (qui doit être connue à l’avance), en évitant complètement toutes les rotations d’arbres. Les arbres intermédiaires sont maintenus en équilibre AVL par le choix de l’ordre d’insertion. Puisqu’ils ont la hauteur du plus bas des deux arbres de Fibonacci qu’ils lient, ils sont tous déséquilibrés au maximum.

Les insertions sont effectuées en insérant virtuellement tous les nœuds dans la séquence des arbres de Fibonacci, mais en insérant pour chaque arbre virtuel uniquement les nœuds qui sont des sous-arbres de hauteur 1. Ce sont les nœuds “incrémentiels” entre deux arbres de Fibonacci consécutifs.

Voici comment cela fonctionne dans le cas max_height = 5 : 

 insert 0 => Fibonacci tree of height 1 (1 node): 0 insert 8 => Fibonacci tree of height 2 (2 nodes): 0 8 insert -8 insert 12 => Fibonacci tree of height 3 (4 nodes): 0 -8 8 12 insert -4 insert 4 insert 14 => Fibonacci tree of height 4 (7 nodes): 0 -8 8 -4 4 12 14 insert -12 insert -2 insert 6 insert 10 insert 15 => Fibonacci tree of height 5 (12 nodes): 0 -8 8 -12 -4 4 12 -2 6 10 14 15

Et voici le code (simplifié): 

 void fibonacci_subtree(int root, int height, int child_delta) { if (height == 1) { insert_into_tree(root); } else if (height == 2) { insert_into_tree(root + child_delta); } else if (height >= 3) { fibonacci_subtree(root - child_delta, height - 2, child_delta >> 1); fibonacci_subtree(root + child_delta, height - 1, child_delta >> 1); } } ... for (height = 1; height <= max_height; height++) { fibonacci_subtree(0, height, 1 << (max_height - 2)); }

METTRE À JOUR

La solution de godel9 résout le problème de la propagation des clés de cette solution. Voici la sortie du code de godel9: 

 insert 0 => Fibonacci tree of height 1 (1 node): 0 insert 3 => Fibonacci tree of height 2 (2 nodes): 0 3 insert -3 insert 5 => Fibonacci tree of height 3 (4 nodes): 0 -3 3 5 insert -2 insert 1 insert 6 => Fibonacci tree of height 4 (7 nodes): 0 -3 3 -2 1 5 6 insert -4 insert -1 insert 2 insert 4 insert 7 => Fibonacci tree of height 5 (12 nodes): 0 -3 3 -4 -2 1 5 -1 2 4 6 7

Et voici le code dans la version la plus proche de la mienne (ici avec un tableau de fibs statique): 

 static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170 }; void fibonacci_subtree(int root, int height, int *fib) { if (height == 1) { insert_into_tree(root); } else if (height == 2) { insert_into_tree(root + *fib); } else if (height >= 3) { fibonacci_subtree(root - *fib, height - 2, fib - 2); fibonacci_subtree(root + *fib, height - 1, fib - 1); } } ... for (height = 1; height <= max_height; height++) { fibonacci_subtree(0, height, fibs + max_height - 1); }

L'arbre de Fibonacci final de hauteur H a F H + 2 - 1 nœuds sans "trous" entre les valeurs de clé, et a k max - k racine = F H + 1 - 1. La plage de clés peut être positionnée commodément, si nécessaire , en décalant la valeur de clé de la racine et en échangeant éventuellement à gauche et à droite dans l’algorithme.

Ce qui rest non résolu, c'est le remplissage compact de toute plage de clés donnée avec des clés entières (alors que c'est sortingvial pour des arbres exactement équilibrés). Avec cet algorithme, si vous voulez créer un arbre déséquilibré au maximum avec n nœuds (avec des clés entières), où n n’est pas un nombre de Fibonacci - 1, et que vous voulez la plus petite plage possible de clés, vous pouvez trouver la première hauteur pouvant accueillir n nœuds, puis exécuter l'algorithme pour cette hauteur, mais en s'arrêtant lorsque n nœuds ont été insérés. Il restra un certain nombre de "trous" (dans le pire des cas, env. N / φ ≅ n / 1.618).

Contrairement à ce que je comprenais intuitivement lorsque j’ai écrit l’introduction de cette solution, l’efficacité temporelle de cet algorithme, avec ou sans l’importante amélioration de godel9, est déjà optimale, car elle est O (n) (de sorte que lorsque les insertions sont incluses , il devient O (n log n)). En effet, le nombre d'opérations est proportionnel à la sum des nœuds de tous les arbres de Fibonacci de T F 1 = T 1 à T F H = T n , c'est-à-dire que N = Σ h = 1 ... H (F h + 2 - 1) = F H + 4 - H - 1. Mais deux nombres consécutifs de Fibonacci ont le rapport asymptotique φ 1.618, le nombre d’ or , de sorte que N / n 2 ≅ 2.618. Vous pouvez comparer cela avec des arbres binarys complètement équilibrés, où des formules très similaires s'appliquent, uniquement avec un "logarithme" de 2 au lieu de.

Bien que je doute qu'il soit utile de supprimer le facteur φ 2 , compte tenu de la simplicité du code actuel, il est intéressant de noter ce qui suit: lorsque vous ajoutez les nœuds "incrémentaux" de tout arbre de Fibonacci intermédiaire de hauteur h, la différence entre deux clés consécutives de cette "frontière de Fibonacci" (mon terme) est soit F H-h + 3, soit F H-h + 4 , selon un motif alterné particulier. Si nous connaissions une règle générasortingce pour ces différences, nous pourrions éventuellement remplir l'arbre simplement avec deux boucles nestedes.

Question interessante. Il semble que vous ayez déjà une bonne solution, mais je trouverais plus facile une approche plus combinatoire.

Hypothèses:

  • Soit U (n) le nombre de nœuds dans un arbre AVL asymésortingque au maximum de hauteur n.

  • U (0) = 0

  • U (1) = 1

  • U (n) = U (n-1) + U (n-2) + 1 pour n> = 2 (c’est-à-dire un nœud racine plus deux sous-arbres non équilibrés au maximum)

  • Par commodité, supposons que U (n-1) est toujours le sous-arbre de gauche et U (n-2) est toujours le droit.

  • Laissez chaque nœud être représenté par une chaîne unique représentant le chemin d’access de la racine au nœud. Le nœud racine est la chaîne emptry, les nœuds de niveau 1 sont “L” et “R”, les nœuds de niveau 2 sont “LL”, “LR”, “RL” et “RR”, etc.

Conclusions:

  • Une chaîne valide pour un nœud de niveau A dans U (n) est une longueur de caractères A et vérifie l’inégalité: n – nombre (“L”) – 2 * nombre (“R”)> = 1

  • compte (“L”) + compte (“R”) = A ou compte (“L”) = A – compte (“R”)

  • Donc compte (“R”) <= n - A - 1

  • Nous pouvons utiliser les fonctions suivantes pour générer tous les chemins valides à un niveau donné et déterminer la valeur de la clé sur chaque nœud. 

     void GeneratePaths(int height, int level) { int rLimit = height - level - 1; GeneratePaths(height, rLimit, level, ssortingng.Empty, 0); } void GeneratePaths(int height, int rLimit, int level, ssortingng prefix, int prefixlen) { if (prefixlen + 1 < level) { GeneratePaths(height, rLimit, level, prefix + "L", prefixlen + 1); if (rLimit > 0) GeneratePaths(height, rLimit - 1, level, prefix + "R", prefixlen + 1); } else if (prefixlen + 1 == level) { InsertNode(prefix + "L", height) if (rLimit > 0) InsertNode(prefix + "R", height); } } void InsertNode(ssortingng path, int height) { int key = fibonacci(height); int index = height - 2; for (int i=0; i < path.length(), i++) { int difference = fibonacci(index); char c = path.charAt(i); if (c == 'L') { key -= difference; index -= 1; } else if (c == 'R') { key += difference; index -= 2; } } InsertKey(key); }

Si vous utilisez ces fonctions pour générer une arborescence U (5), vous obtiendrez ce résultat. (Notez que les touches sur le bord gauche de l’arbre suivent la séquence de fibonacci de 1 à 5,) 

  5 3 7 2 4 6 8 1 3 4 6 1