L'équilibrage d'un Arbre Binaire (AVL)

Un bouc émissaire arbre a peut-être le plus simple solde à la détermination de l'algorithme à comprendre. Si toute insertion provoque le nouveau nœud à être trop profonde, on trouve un nœud autour duquel de rééquilibrer, en regardant équilibre de poids, plutôt que la hauteur de l'équilibre. La règle pour savoir si rééquilibrer sur supprimer est aussi simple. Il ne stocke pas toutes les arcanes de l'information dans les nœuds. Il est plus difficile de prouver que c'est correct, mais vous n'avez pas besoin de comprendre l'algorithme...

Toutefois, contrairement à un AVL il n'est pas à la hauteur équilibrée à tous les temps. Comme le rouge et le noir de son déséquilibre est lié, mais contrairement à rouge-noir c'est accordable avec un paramètre, donc pour la plupart des fins pratiques, il semble aussi équilibré que vous en avez besoin pour être. Je pense que si vous l'accorder trop serré, si, il termine aussi mauvais ou pire que AVL pour le pire-cas des insertions.

Réponse à la question de modifier

Je vais vous donner mon cheminement personnel à la compréhension de l'AVL arbres.

Vous devez d'abord comprendre ce qu'est un arbre de rotation est, donc ignorer tout le reste vous avez déjà entendu parler de l'AVL algorithmes et de le comprendre. Obtenir directement dans votre tête qui est un droit de rotation et qui est une rotation à gauche, et ce que chacun fait à l'arbre, ou bien les descriptions précises des méthodes vais juste vous confondre.

Ensuite, comprendre que le truc pour équilibrer les arbres AVL est que chaque nœud enregistrements dans la différence entre la hauteur de son gauche et droit de sous-arbres. La définition de la taille de la équilibrée", c'est que c'est entre -1 et 1 inclus pour chaque nœud de l'arbre.

Ensuite, comprendre que si vous avez ajouté ou supprimé un nœud, vous pouvez le déséquilibre de l'arbre. Mais vous ne pouvez avoir modifié l'équilibre des nœuds qui sont les ancêtres du nœud que vous avez ajouté ou supprimé. Donc, ce que vous allez faire est de travailler votre chemin de retour vers l'arbre, à l'aide de rotations pour solde de tout déséquilibré nœuds de vous trouver, et la mise à jour de leur équilibre score, jusqu'à ce que l'arbre est équilibré à nouveau.

La partie finale de la compréhension, il est à rechercher dans un décent de référence les rotations spécifiques utilisés pour rééquilibrer chaque nœud que vous avez trouvé: c'est la "technique" de celui-ci, par opposition au concept haut de gamme. Vous n'avez qu'à se rappeler les détails lors de la modification d'arbre AVL code ou peut-être au cours de structures de données des examens. Il est ans depuis que j'ai eu arbre AVL code autant que de l'ouvrir dans le débogueur - implémentations ont tendance à arriver à un point où ils travaillent et ensuite rester à travailler. Donc, je ne me souviens pas. Vous pouvez sorte de travailler sur une table à l'aide d'un peu de jetons de poker, mais il est difficile d'être sûr que vous avez vraiment tous les cas (il n'y en a pas beaucoup). Le meilleur de le regarder.

Puis il y a les affaires de traduire tout cela dans le code.

Je ne pense pas que le fait de regarder les exemples de code permet de très bien avec n'importe quelle étape à l'exception de la dernière, si les ignorer. Même dans le meilleur des cas, où le code est écrit très clairement, il ressemble à un manuel de description des processus, mais sans les diagrammes. Dans un cas plus classique c'est un gâchis de structure C de la manipulation. Donc, il suffit de coller à ces livres.

OriginalL'auteur Steve Jessop

J'ai fait quelques travaux avec AVL arbres ces derniers temps.

La meilleure aide que j'ai pu trouver sur la façon d'équilibrer leur a été par le biais de la recherche sur google.

Je viens de codé autour de cette pseudo-code (si vous comprenez comment faire des rotations, il est assez facile à mettre en œuvre).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

OriginalL'auteur mscccc

L'arbre AVL est inefficace, parce que vous avez à faire potentiellement de nombreuses rotations par insertion/suppression.

Le Rouge-Noir arbre est probablement une meilleure solution parce que les insertions/suppressions sont beaucoup plus efficaces. Cette structure garantit le plus long chemin d'une feuille est de pas plus de deux fois le chemin le plus court. Ainsi, alors que de moins en moins équilibré qu'un arbre AVL, le pire déséquilibrée cas sont à éviter.

Si votre arbre sera lu de nombreuses fois, et ne pas être modifié après sa création, il peut être intéressant de les frais généraux supplémentaires pour une cuisine équilibrée arbre AVL. Aussi le Rouge-Noir arbre a besoin d'un bit supplémentaire de stockage pour chaque nœud, ce qui donne le nœud de la "couleur".

OriginalL'auteur user20493

il y a une mise en œuvre complète d'un auto-équilibrage arbre avl @ http://code.google.com/p/self-balancing-avl-tree/ . il met également en œuvre des temps logarithmique concaténer et diviser des opérations ainsi qu'une carte/multimap collections

OriginalL'auteur cos