Différence entre une LinkedList et un arbre de recherche binaire
https://stackoverflow.com/questions/270080
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Quelles sont les principales différences entre une liste chaînée et un BinarySearchTree? La BST est-elle juste un moyen de maintenir une liste de choix? Mon instructeur a parlé de LinkedList, puis de BST, mais ne les a pas comparées ou n'a pas précisé quand préférer l'une à l'autre. C'est probablement une question idiote mais je suis vraiment confus. J'apprécierais que quelqu'un puisse clarifier cela d'une manière simple.
La solution
Liste chaînée:
Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7)
Arbre binaire:
Node(1)
/
Node(2)
/ \
/ Node(3)
RootNode(4)
\ Node(5)
\ /
Node(6)
\
Node(7)
Dans une liste chaînée, les éléments sont liés entre eux via un seul pointeur suivant. Dans une arborescence binaire, chaque nœud peut avoir 0, 1 ou 2 sous-nœuds, où (dans le cas d’une arborescence de recherche binaire) la clé du nœud gauche est inférieure à la clé du nœud et la clé du nœud droit est supérieure à le noeud. Tant que l'arborescence est équilibrée, le chemin de recherche de chaque élément est beaucoup plus court que celui d'une liste chaînée.
chemins de recherche:
------ ------ ------
key List Tree
------ ------ ------
1 1 3
2 2 2
3 3 3
4 4 1
5 5 3
6 6 2
7 7 3
------ ------ ------
avg 4 2.43
------ ------ ------
Pour les structures plus grandes, le chemin de recherche moyen devient significativement plus petit:
------ ------ ------
items List Tree
------ ------ ------
1 1 1
3 2 1.67
7 4 2.43
15 8 3.29
31 16 4.16
63 32 5.09
------ ------ ------
Autres conseils
Un arbre de recherche binaire est un arbre binaire dans lequel chaque nœud interne x stocke un élément de sorte que l'élément stocké dans le sous-arbre gauche de x sont inférieurs ou égaux à x et les éléments stockés dans le sous-arbre de droite de x sont supérieurs ou égaux à x .
Désormais, une liste chaînée consiste en une séquence de nœuds, chacun contenant des valeurs arbitraires et une ou deux références pointant vers les nœuds suivant et / ou précédent.
En informatique, un arbre de recherche binaire (BST) est une structure de données d'arborescence binaire qui a les propriétés suivantes:
- chaque nœud (élément de l’arbre) a une valeur distincte;
- les sous-arbres gauche et droit doivent également être des arbres de recherche binaires;
- le sous-arbre de gauche d'un noeud ne contient que des valeurs inférieures à la valeur du noeud;
- le sous-arbre de droite d'un noeud ne contient que des valeurs supérieures ou égales à la valeur du noeud.
En informatique, une liste chaînée est l'une des structures de données fondamentales et peut être utilisé pour implémenter d'autres structures de données.
Ainsi, une arborescence de recherche binaire est un concept abstrait pouvant être implémenté avec une liste chaînée ou un tableau. Alors que la liste chaînée est une structure de données fondamentale.
Je dirais que la différence principale est qu'un arbre de recherche binaire est trié. Lorsque vous insérez dans un arbre de recherche binaire, l'emplacement de stockage de ces éléments en mémoire dépend de leur valeur. Avec une liste chaînée, les éléments sont ajoutés aveuglément à la liste, quelle que soit leur valeur.
Vous pouvez tout de suite faire des compromis: Les listes chaînées préservent l'ordre d'insertion et l'insertion est moins coûteuse Les arbres de recherche binaires sont généralement plus rapides à rechercher
Une liste chaînée est un nombre séquentiel de " noeuds " liés les uns aux autres, par exemple:
public class LinkedListNode
{
Object Data;
LinkedListNode NextNode;
}
Un arbre de recherche binaire utilise une structure de nœud similaire, mais au lieu de créer un lien vers le nœud suivant, il est lié à deux nœuds enfants:
public class BSTNode
{
Object Data
BSTNode LeftNode;
BSTNode RightNode;
}
En suivant des règles spécifiques lors de l'ajout de nouveaux nœuds à un fichier BST, vous pouvez créer une structure de données très rapide à parcourir. D'autres réponses ici ont détaillé ces règles, je voulais juste montrer au niveau du code la différence entre les classes de nœuds.
Il est important de noter que si vous insérez des données triées dans un fichier BST, vous obtenez une liste chaînée et vous perdez l'avantage de l'utilisation d'un arbre.
Pour cette raison, une liste chaînée est une structure de données de traversée O (N), tandis qu'un BST est une structure de données de traversée O (N) dans le pire des cas et un O (log N) dans le meilleur des cas.
Les listes chaînées et les fichiers BST n'ont pas vraiment beaucoup en commun, sauf que ce sont deux structures de données qui agissent en tant que conteneurs. Les Listes liées vous permettent d'insérer et de supprimer efficacement des éléments en tout lieu. dans la liste, tout en maintenant l'ordre de la liste. Cette liste est implémentée en utilisant des pointeurs d’un élément à l’autre (et souvent le précédent).
Un arbre de recherche binaire est en revanche une donnée. structure d’une abstraction supérieure (c’est-à-dire non spécifiée comment ceci est implémenté en interne) qui permet des recherches efficaces (c.-à-d. pour trouver un élément spécifique, vous n'avez pas à regarder tous les éléments.
Notez qu'une liste chaînée peut être considérée comme un arbre binaire dégénéré, c’est-à-dire un arbre où tous les nœuds n’ont qu’un seul enfant.
C'est en fait assez simple. Une liste chaînée est juste un tas d’articles enchaînés, sans ordre particulier. Vous pouvez penser à cela comme un arbre vraiment maigre qui ne se branche jamais:
1 - > 2 - > 5 - > 3 - > 9 - > 12 - > | i. (ce dernier est une tentative ascii-art d'un null final)
Un arbre de recherche binaire est différent de 2 manières: la partie binaire signifie que chaque nœud a 2 enfants, pas un, et la partie de recherche signifie que ces enfants sont conçus pour accélérer les recherches - uniquement éléments plus petits à gauche, et seulement les plus grands à droite:
5
/ \
3 9
/ \ \
1 2 12
9 n'a plus d'enfant et 1, 2 et 12 sont des "feuilles". - ils n'ont pas de branches.
Avez-vous du sens?
Pour la plupart des "recherches" " types d'utilisations, un BST est mieux. Mais juste pour "conserver une liste de choses à traiter plus tard, premier entré, premier sorti ou dernier entré, premier sorti" genre de choses, une liste chaînée pourrait bien fonctionner.
Le problème avec une liste liée est une recherche dans celle-ci (que ce soit pour une extraction ou une insertion).
Pour une liste à un seul lien, vous devez commencer en tête et rechercher séquentiellement pour trouver l'élément souhaité. Pour éviter d'avoir à analyser toute la liste, vous avez besoin de références supplémentaires aux nœuds de la liste. Dans ce cas, il ne s'agit plus d'une simple liste chaînée.
Un arbre binaire permet une recherche et une insertion plus rapides grâce à un tri et à une navigation inhérents.
Une alternative que j'ai utilisée avec succès dans le passé est une liste SkipList. Ceci fournit quelque chose qui ressemble à une liste chaînée mais avec des références supplémentaires pour permettre des performances de recherche comparables à un arbre binaire.
Une liste chaînée n’est que… une liste. C'est linéaire; chaque nœud a une référence au prochain nœud (et au précédent, si vous parlez d'une liste doublement chaînée). Un arbre branches --- chaque nœud a une référence à divers nœuds enfants. Un arbre binaire est un cas particulier dans lequel chaque nœud n'a que deux enfants. Ainsi, dans une liste chaînée, chaque nœud a un nœud précédent et un nœud suivant, et dans une arborescence binaire, un nœud a un enfant gauche, un enfant droit et un parent.
Ces relations peuvent être bidirectionnelles ou unidirectionnelles, selon la manière dont vous devez pouvoir traverser la structure.
Ils ont des similitudes, mais la principale différence est qu'un arbre de recherche binaire est conçu pour permettre une recherche efficace d'un élément, ou d'une "clé".
Un arbre de recherche binaire, semblable à une liste à double lien, pointe vers deux autres éléments de la structure. Cependant, lors de l'ajout d'éléments à la structure, plutôt que de simplement les ajouter à la fin de la liste, l'arborescence binaire est réorganisée de manière à ce que les éléments liés à l'élément "gauche" Les nœuds sont inférieurs au nœud actuel et les éléments liés au "droit" sont supérieurs au noeud actuel.
Dans une implémentation simple, le nouvel élément est comparé au premier élément de la structure (la racine de l’arbre). Si c'est moins, le " gauche " branche est prise, sinon le "droit" branche est examinée. Cela continue avec chaque noeud, jusqu'à ce qu'une branche soit trouvée vide; le nouvel élément remplit cette position.
Avec cette approche simple, si les éléments sont ajoutés dans l’ordre, vous vous retrouvez avec une liste chaînée (avec les mêmes performances). Différents algorithmes existent pour maintenir l’équilibre dans l’arbre en réorganisant les nœuds. Par exemple, les arbres AVL font le maximum pour maintenir l’arbre le plus équilibré possible, en donnant les meilleurs temps de recherche. Les arbres rouge-noir ne maintiennent pas l’arbre aussi équilibré, ce qui ralentit les recherches, mais travaillent moins en moyenne lorsque les clés sont insérées ou supprimées.
La liste chaînée est constituée de données linéaires droites avec des nœuds adjacents connectés les uns aux autres, par ex. A-> B-> C. Vous pouvez le considérer comme une clôture droite.
BST est une structure hiérarchique, tout comme un arbre dont le tronc principal est connecté à des branches et ces branches sont à leur tour connectées à d'autres branches, etc. Le " Binary " mot signifie ici que chaque branche est connectée à un maximum de deux branches.
Vous utilisez la liste chaînée pour représenter des données droites uniquement avec chaque élément connecté à un élément maximum; alors que vous pouvez utiliser BST pour connecter un élément à deux éléments. Vous pouvez utiliser BST pour représenter des données telles que l'arbre généalogique, mais cet arbre deviendra un arbre de recherche multiple car il peut y avoir plus de deux enfants par personne.
Un arbre de recherche binaire peut être implémenté de n'importe quelle manière, il n'est pas nécessaire d'utiliser une liste chaînée.
Une liste chaînée est simplement une structure qui contient des nœuds et des pointeurs / références à d’autres nœuds au sein d’un nœud. Étant donné le nœud principal d'une liste, vous pouvez rechercher tout autre nœud dans une liste liée. Les listes à double liaison ont deux pointeurs / références: la référence normale au noeud suivant, mais également une référence au noeud précédent. Si le dernier nœud d'une liste doublement chaînée fait référence au premier nœud de la liste en tant que nœud suivant et que le premier nœud fait référence au dernier nœud en tant que nœud précédent, il s'agit d'une liste circulaire.
Un arbre de recherche binaire est un arbre qui divise son entrée en deux moitiés à peu près égales, basées sur un algorithme de comparaison de recherche binaire. Ainsi, il suffit de très peu de recherches pour trouver un élément. Par exemple, si vous aviez un arbre avec 1-10 et que vous deviez en rechercher trois, tout d'abord, l'élément situé en haut serait vérifié, probablement un 5 ou un 6. Trois serait inférieur à celui, de sorte que seule la première moitié du l'arbre serait alors vérifié. Si la valeur suivante est 3, vous l'avez, sinon, une comparaison est effectuée, etc. jusqu'à ce qu'elle soit introuvable ou que ses données soient renvoyées. Ainsi, l’arbre est rapide pour la recherche, mais pas nécessairement rapide pour l’insertion ou la suppression. Ce sont des descriptions très approximatives.
Liste chaînée de wikipedia et Arbre de recherche binaire , également de wikipedia.
Ce sont des structures de données totalement différentes.
Une liste chaînée est une séquence d’éléments où chaque élément est lié au suivant et, dans le cas d’une liste doublement liée, au précédent.
Un arbre de recherche binaire est quelque chose de totalement différent. Il a un nœud racine, le nœud racine a jusqu'à deux nœuds enfants et chaque nœud enfant peut avoir jusqu'à deux notes enfants, etc. Il s'agit d'une structure de données assez intelligente, mais il serait fastidieux de l'expliquer ici. Consultez le article sur Wikipedia .
