Recherche binaire arbre AVL arbres
Pour autant que je sais la complexité du temps entre AVL arbres et Arbres Binaires sont les mêmes dans la moyenne des cas, la fonction AVLs battre techniciennes se chargent dans le pire des cas. Cela me donne un indice qui AVLs sont toujours supérieure à celle de techniciennes se chargent de toutes les façons possibles pour interagir avec eux, peut-être ajouter un peu de complexité quand il s'agit de l'équilibre des implémentations.
Est-il une raison tout le monde devrait utiliser techniciennes se chargent au lieu de AVLs en premier lieu?
- AVL arbres sont hors de la mode, de nos jours, ils ont été remplacés par des arbres rouge-noir.
Vous devez vous connecter pour publier un commentaire.
D'abord, obtenir la meilleure performance possible est pas le but ultime de la programmation. Donc, même si l'option B a été toujours plus rapides et consomment moins de mémoire qu'Un, cela ne veut pas dire que c'est toujours la meilleure option, si c'est plus compliqué. Plus compliqué code prend plus de temps pour écrire, est plus difficile à comprendre et est plus susceptible de contenir des bugs. Donc, si le plus simple mais moins efficace, l'option A est assez bon pour vous, alors cela signifie que c'est le meilleur choix.
Maintenant, si vous voulez comparer les AVL arbre à simple arbre de recherche binaire (BST) sans équilibrage, puis AVL consomment plus de mémoire (chaque nœud a à retenir son équilibre facteur) et chaque opération peut être plus lent (parce que vous avez besoin pour maintenir l'équilibre facteur et parfois effectuer des rotations).
Comme vous l'avez dit, BST sans équilibrage a une très mauvaise (linéaire) pire des cas. Mais si vous savez que ce pire des cas ne vous arrivera pas, ou si vous êtes d'accord si l'opération est lente dans de rares cas, le BST sans équilibrage peut-être mieux que AVL.
Puisqu'il est à la charge supplémentaire de la vérification et de la mise à jour des facteurs d'équilibre et de rotation des nœuds, de l'insertion et de suppression dans les arbres AVL peut être assez lente par rapport à la non-équilibré du BST.
En raison de l'étroitesse de l'équilibrage, la recherche ne prendra jamais linéaire-comme le temps, alors vous voudrez probablement utiliser AVL arbres dans les situations où la recherche est de plus en plus fréquentes de l'opération de mise à jour de l'arbre.
Mon hypothèse, c'est: quand vous parlez de la STB, tu veux dire un BST sans équilibrage.
Il pourrait être soutenu que si vous avez besoin d'un navigatable structure de données et vous savez que vos données ne seront pas pire des cas (tri) et est un peu petite, un BST (sans solde) serait suffisant.
Mais le plus probable est que c'est un cas rare.
Arbre AVL est aussi un BST, mais il peut rééquilibrer lui-même. Ce comportement rend plus rapide dans le pire des cas. Il garde le rééquilibrage de lui-même, donc dans le pire des cas il va consommer de O(log n ) temps lors de la plaine BST va prendre en O(n). Donc, la réponse à votre question: Il est toujours préférable de mettre en œuvre arbre AVL que de simples BST.