Différence entre une liste de liens et un arbre de recherche binaire
quelles sont les principales différences entre une liste liée et un BinarySearchTree? Est-ce que la BST est juste un moyen de maintenir une liste de liens? Mon instructeur a parlé de LinkedList puis DE BST, mais ne les a pas comparés ou n'a pas dit quand préférer l'un plutôt que l'autre. C'est probablement une question stupide mais je suis vraiment confus. J'apprécierais que quelqu'un puisse clarifier cela d'une manière simple.
13 réponses
Liste De Liens:
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 liée, les éléments sont reliés entre eux par un seul pointeur suivant. Dans un arbre binaire, chaque noeud peut avoir 0, 1 ou 2 sous-noeuds, où (dans le cas d'un arbre de recherche binaire) la clé du noeud de gauche est moindre que la clé du noeud et la clé du noeud de droite est plus que le noeud. Tant que l'arbre est équilibré, les searchpath de chaque élément est beaucoup plus courte que celle de liste.
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
------ ------ ------
par des structures plus grandes le chemin de recherche Moyen devient significatif 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
------ ------ ------
Arbre De Recherche Binaire est un arbre binaire dans lequel chaque noeud interne x magasins un élément tel 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 droit de x inférieur ou égal à x.
Liste De Liens se compose d'une séquence de noeuds, chacun contenant arbitraire valeurs et une ou deux références pointant vers les noeuds suivants et/ou précédents.
En informatique, un arbre de recherche binaire (BST) est une structure de données d'arbre binaire qui a les propriétés suivantes:
- chaque nœud (élément dans l'arbre) a une valeur distincte;
- les sous-arbres de gauche et de droite doivent aussi être des arbres de recherche binaires;
- le sous-arbre gauche d'un nœud ne contient que des valeurs inférieures à la valeur du nœud;
- le sous-arbre droit d'un noeud ne contient que des valeurs supérieures ou égales à celles du noeud valeur.
En informatique, un liste de liens est l'une des principales structures de données, et peut être utilisé pour mettre en œuvre d'autres structures de données.
donc une arborescence de recherche binaire est un concept abstrait qui peut être implémenté avec une liste liée ou un tableau. Tandis que la liste liée est une structure de données fondamentale.
je dirais que la PRINCIPALE différence est qu'un arbre de recherche binaire est triée. Lorsque vous insérez dans un arbre de recherche binaire, où ces éléments finissent par être stockés en mémoire est une fonction de leur valeur. Avec une liste liée, les éléments sont ajoutés aveuglément à la liste quelle que soit leur valeur.
tout de suite, vous pouvez certains compromis: Les listes liées préservent l'ordre d'insertion et l'insertion est moins chère Arbres binaires sont généralement plus rapides à la recherche
une liste liée est un nombre séquentiel de "noeuds" liés entre eux, c'est-à-dire:
public class LinkedListNode
{
Object Data;
LinkedListNode NextNode;
}
un arbre de recherche binaire utilise une structure de noeud similaire, mais au lieu de lier au noeud suivant, il lie à deux noeuds enfant:
public class BSTNode
{
Object Data
BSTNode LeftNode;
BSTNode RightNode;
}
en suivant des règles spécifiques lors de l'ajout de nouveaux noeuds à un TSB, vous pouvez créer une structure de données qui est très rapide à traverser. D'autres réponses ici ont détaillé ces règles, je voulais juste montrer au niveau du code la différence entre les noeuds classe.
il est important de noter que si vous insérez des données triées dans un BST, vous finirez avec une liste liée, et vous perdrez l'avantage d'utiliser un arbre.
les listes de liens et les OSB n'ont pas vraiment grand chose en commun, sauf qu'elles sont toutes deux des structures de données qui agissent comme des conteneurs. listes de liens permet essentiellement d'insérer et de supprimer des éléments efficacement à n'importe quel endroit de 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 au précédent).
arbre de recherche binaire d'autre part, est un structure de données d'une abstraction supérieure (c'est-à-dire qu'elle n'est pas spécifiée comment ceci est implémenté en interne) qui permet des recherches efficaces (i.e. pour trouver un élément spécifique, vous n'avez pas à regarder tous les éléments.
notez Qu'une liste liée peut être considérée comme un arbre binaire dégénéré, c'est-à-dire un arbre où tous les noeuds n'ont qu'un enfant.
C'est en fait assez simple. Une liste chaînée est juste un tas d'éléments enchaînés, dans aucun ordre particulier. On peut y voir un arbre vraiment maigre qui ne se ramifie jamais:
1 -> 2 -> 5 -> 3 -> 9 -> 12 -> |i. (ce dernier est un fichier ascii-art tentative de fin null)
un arbre de recherche binaire est différent de 2 façons: la partie binaire signifie que chaque noeud a 2 enfants, pas un seul, et la partie de recherche signifie que ces enfants sont organisés pour accélérer les recherches-seulement les petits éléments, à gauche, et seulement les plus grands à droite:
5
/ \
3 9
/ \ \
1 2 12
9 n'a pas d'enfant gauche, et 1, 2, et 12 sont des "feuilles" - ils n'ont pas de branches.
sens?
pour la plupart des types d'utilisation "de recherche", un BST est mieux. Mais pour "garder une liste de choses à traiter plus tard Premier-In-premier-Out ou dernier-In-Premier-Out" genre de choses, une liste liée pourrait bien fonctionner.
le problème avec une liste liée est la recherche au sein de celui-ci (que ce soit pour la récupération ou l'insertion).
pour une liste mono-liée, vous devez commencer par la tête et chercher séquentiellement pour trouver l'élément désiré. Pour éviter d'avoir à numériser la liste entière, vous avez besoin de références supplémentaires aux noeuds de la liste, auquel cas, ce n'est plus une simple liste liée.
un arbre binaire permet une recherche et une insertion plus rapides en étant intrinsèquement trié et navigable.
une alternative que j'ai utilisée avec succès dans le passé est une liste D'attente. Cela fournit quelque chose qui ressemble à une liste liée, mais avec des références supplémentaires pour permettre des performances de recherche comparables à un arbre binaire.
une liste de liens n'est que cela... liste. C'est linéaire; chaque noeud a une référence au prochain noeud (et au précédent, si vous parlez d'une liste doublement liée). Un arbre branches - - - chaque noeud a une référence à divers noeuds enfant. Un arbre binaire est un cas particulier dans lequel chaque nœud n'a que deux enfants. Ainsi, dans une liste, chaque nœud est un nœud précédent et d'un noeud suivant, et dans un arbre binaire, un nœud a gauche de l'enfant, droit enfant et le parent.
Ces relations peuvent être bidirectionnel ou unidirectionnel, selon la façon dont vous devez être capable de traverser la structure.
ils ont des similitudes, mais la principale différence est qu'un arbre de recherche binaire est conçu pour soutenir la recherche efficace d'un élément, ou "clé".
un arbre de recherche binaire, comme une liste doublement liée, 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'arbre binaire est réorganisé de sorte que les éléments liés au noeud "gauche" sont moins que le noeud courant et les éléments liés au noeud" droit " sont plus grands que le noeud courant.
dans une implémentation simple, le nouvel élément est comparé au premier élément de la structure (la racine de l'arbre). Si elle est inférieure, la branche" gauche "est prise, sinon la branche" droite " est examinée. Cela continue avec chaque nœud, jusqu'à ce qu'une branche est vide; le nouvel élément remplit cette position.
avec cette approche simple, si les éléments sont ajoutés dans l'ordre, vous finissez avec une liste liée (avec les mêmes performances). Différents algorithmes existent pour maintenir une certaine mesure d'équilibre dans l'arbre, en réarrangeant les noeuds. Par exemple, les arbres AVL font le plus de travail pour garder l'arbre aussi équilibré que possible, donnant les meilleurs temps de recherche. Les arbres rouges-noirs ne maintiennent pas l'arbre aussi équilibré, ce qui entraîne des recherches un peu plus lentes, mais font moins de travail en moyenne à mesure que les clés sont insérées ou enlevées.
la liste liée est des données linéaires droites avec des noeuds adjacents connectés entre eux par exemple A->B->C. Vous pouvez le considérer comme une clôture droite.
la BST est une structure hiérarchique comme un arbre dont le tronc principal est relié à des branches et ces branches à leur tour reliées à d'autres branches et ainsi de suite. Le mot" binaire " signifie ici que chaque branche est connectée à un maximum de deux branches.
vous utilisez la liste liée pour représenter des données droites seulement avec chaque élément connecté jusqu'à un maximum d'un article; alors que vous pouvez utiliser la BST pour connecter un article à deux articles. Vous pouvez utiliser BST pour représenter une donnée telle que l'arbre généalogique, mais qui deviendra l'arbre de recherche n-ary puisqu'il peut y avoir plus de deux enfants à chaque personne.
un arbre de recherche binaire peut être implémenté de n'importe quelle manière, il n'a pas besoin d'utiliser une liste liée.
une liste liée est simplement une structure qui contient des noeuds et des pointeurs/références à d'autres noeuds à l'intérieur d'un noeud. Étant donné le noeud principal d'une liste, vous pouvez naviguer vers n'importe quel autre noeud dans une liste liée. Les listes doublement liées ont deux pointeurs / Références: la référence normale au noeud suivant, mais aussi une référence au noeud précédent. Si le dernier noeud d'une liste doublement liée renvoie le premier noeud dans la liste comme le prochain noeud, et le premier noeud renvoie le dernier noeud comme son noeud précédent, on dit qu'il s'agit d'une liste circulaire.
un arbre de recherche binaire est un arbre qui divise ses entrées en deux moitiés à peu près égales basées sur un algorithme de comparaison de recherche binaire. Il suffit donc de quelques recherches pour trouver un élément. Par exemple, si vous aviez un arbre de 1 à 10 et que vous deviez en chercher trois, l'élément du haut serait d'abord coché, probablement 5 ou 6. Trois serait moins que ça, alors seule la première moitié de l'arbre pourrait alors être vérifié. Si la valeur suivante est 3, vous l'avez, sinon une comparaison est faite, etc, jusqu'à ce qu'elle ne soit pas trouvée ou que ses données soient retourné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 De Liens à partir de wikipedia, et Arbre De Recherche Binaire, aussi de wikipedia.
ce sont des structures de données totalement différentes.
Une liste chaînée est une séquence de l'élément où chaque élément est lié à la suivante, et dans le cas d'une liste doublement chaînée, la précédente.
un arbre de recherche binaire est quelque chose de totalement différent. Il a un noeud racine, le noeud racine a jusqu'à deux noeuds enfant, et chaque noeud enfant peut avoir jusqu'à deux notes enfant, etc. C'est une structure de données assez intelligente, mais il serait quelque peu fastidieux de l'expliquer ici. Découvrez Wikipedia artcle.