Garder un arbre binaire équilibré lorsque les éléments sont insérés dans l'ordre
Je me demandais si il existe un algorithme pour le maintien de l'équilibre d'un arbre binaire, lorsqu'il est connu que les éléments sont toujours insérées dans l'ordre.
Une option serait d'utiliser la méthode standard de la création d'un équilibre de l'arbre à partir d'un tableau trié ou liste liée, comme discuté dans cette question, et aussi cette autre question. Cependant, je voudrais une méthode où quelques éléments peuvent être insérés dans l'arbre, ensuite effectué des recherches sur elle, et d'autres éléments, puis ajouté plus tard, sans avoir à décomposer l'arbre à une liste et re-faire la chose entière.
Une autre option serait d'utiliser l'un des nombreux auto-équilibrage de l'arbre implémentations, AVL, AA, Rouge-Noir, etc. etc. Cependant, tous ces imposer une sorte de surcharge dans le processus d'insertion, et je me demandais si il y a peut être un moyen d'éviter cela, étant donné la contrainte que les éléments sont toujours inséré dans l'ordre croissant.
Donc, pour plus de clarté, je voudrais savoir si il existe une méthode qui me permette de maintenir un équilibre arbre binaire, de sorte que je peux insérer l'arbitraire d'un nouvel élément à n'importe quel point et de maintenir l'équilibre de l'arbre, à condition que le nouvel élément est plus dans la commande de l'arbre de tous éléments déjà présents dans l'arbre.
Comme un exemple, supposons que j'ai eu l'arbre suivant:
4
/\
/ \
2 6
/\ /\
1 3 5 7
Est-il un moyen simple de maintenir l'équilibre lors de l'insertion d'un nouvel élément, si je sais que l'élément sera plus grande que 7?
source d'informationauteur
Vous devez vous connecter pour publier un commentaire.
Si vous êtes vraiment intéressés à faire à l'aide d'un BST (qui je pense n'est pas la meilleure option, comme vous pouvez le lire dans mon autre réponse), vous pouvez le faire comme ceci:
Normales de MARCHÉ. Cela signifie que les recherches sont en O(log N), si nous arrivons à garder la profondeur au cours des insertions.
Lors d'une insertion (en supposant que nous avons un élément plus grand que tous les précédents), vous marchez à partir de la racine la plus à droite de l'élément. Lorsque vous rencontrez un nœud dont le sous-arbre est un arbre binaire parfait (tous les noeuds contenus avons 2 enfants et toutes les feuilles sont à la même profondeur), vous insérez le nouveau nœud parent du nœud.
Si vous atteignez le plus à droite du nœud dans l'arbre, et vous n'avez pas appliquer la règle précédente, ce qui signifie qu'il a à gauche de l'enfant, mais il n'a pas un droit. Ainsi, le nouveau nœud devient le droit de l'enfant du nœud actuel.
Par exemple, dans le premier arbre ci-dessous, le sous-arbre de 4 n'est pas parfait, mais le sous-arbre de 5 est un arbre avec un seul nœud est parfait par la définition). Donc, nous ajouterons 6 en tant que parent de 5, ce qui signifie 4 est parent de 6 et 5 est la gauche de l'enfant de 6.
Si nous essayons d'ajouter un autre nœud puis, le sous-arbre de 4 n'est pas encore parfait, et il n'est ni l'une des 6. Et 6 est le plus à droite du nœud, nous avons donc ajouter 7 que le droit de l'enfant de 6.
Si nous utiliser cet algorithme, le sous-arbre de gauche de l'enfant de la racine sera toujours parfait et le sous-arbre de l'enfant n'aura jamais de plus grande hauteur que celle de gauche. À cause de cela, la hauteur de l'arbre entier sera toujours O(log N), et donc sera la recherche de temps. L'insertion prendra O(log N) trop de temps.
En comparaison avec l'auto-équilibrage de techniciennes se chargent, le temps, les problèmes sont les mêmes. Mais cet algorithme devrait être plus facile à mettre en œuvre et pourrait effectivement être plus rapide qu'eux.
En comparaison avec le tableau de solution en fonction de mon autre réponse, la complexité du temps de recherche est le même, mais cette BST a pire moment de l'insertion.
L'exigence de vous décrire, vous n'avez pas besoin d'un arbre à tous. Une triés tableau dynamique est tout ce dont vous avez besoin.
Lors de l'insertion, toujours insérer à la fin (O(1) amorti).
Lors de la recherche, de l'utilisation normale recherche binaire (O(log N)).
Cela suppose que vous n'avez pas besoin d'autres opérations, ou que vous n'avez pas l'esprit qu'ils seront en O(N).
Je suppose que vous connaissez a priori que les éléments dans l'ordre croissant. En outre, je suppose que vous voulez un arbre pour la recherche rapide d'un élément spécifique.
Je ne suis pas sûr de savoir si un arbre binaire est le mieux adapté pour l'insertion rapide que vous la décrivez. Mais il y a peut être d'autres structures de données que bien gérer les cas d'utilisation que vous décrivez: bien que je n'ai jamais utilisé, un skip-list vient à mon esprit. Depuis que vous avez toujours insérer des éléments plus grande que tous les éléments déjà dans la collection, il devrait être assez facile à mettre à jour les pointeurs.