|
Les données sont généralement stockées dans des structures d'arbres binaires en utilisant des algorithmes spécialisés . De nombreux avantages proviennent de stocker des données dans une structure arborescente . Par exemple , la recherche d'un arbre binaire ordonné est beaucoup plus rapide que le tri d'une structure de données séquentielles comme un tableau. Une structure de données d'arbre est assurée par de nombreux types de modèles , au cours de l'accès aux données et de modification. La compréhension de ces modèles peuvent vous aider à concevoir de meilleurs algorithmes pour optimiser un algorithme d'arbre . Composants de base d' un arbre
Un arbre binaire binaire se compose de nœuds , qui stockent les données et pointer vers d'autres noeuds dans l'arbre . Le nœud racine est le point de départ de l'arbre et occupe le plus haut niveau. Il peut avoir jusqu'à deux nœuds enfants. Ces nœuds enfants peuvent également avoir jusqu'à deux nœuds enfants. Le nombre de nœuds enfants d' un noeud donné est appelé le degré du nœud. Un noeud sans enfant et un degré de zéro est appelé une feuille. La longueur de nœuds à partir du nœud racine au nœud feuille le plus éloigné est à la hauteur de l'arbre. La profondeur d'un noeud est la distance entre le noeud racine à elle. Chaque nœud qui a la même profondeur est dit être sur le même niveau .
Complète Binary Tree
Un arbre binaire complet est un arbre où chaque noeud a exactement deux ou zéro enfants. En d'autres termes , chaque noeud a deux enfants ou est une feuille. Un exemple d'un arbre binaire complet est le diagramme de décision binaire, ou BDD .
Parfait Binary Tree
Un arbre binaire parfait a les mêmes propriétés de l' arbre binaire complet , mais tous les noeuds feuilles sont au même niveau , ce qui signifie que la profondeur de l'ensemble des feuilles est le même dans un arbre binaire parfait . Comme il est aussi un arbre binaire complet , tous les nœuds sauf les nœuds feuilles ont un diplôme de 2.
Équilibré Binary Tree
Un arbre binaire équilibré est celui dans lequel la profondeur de chaque noeud de feuille est soit le même ou est différent d'une valeur de un. Ajout et suppression de noeuds d'un arbre binaire équilibré peut déséquilibrer , donc une série d'ajustements appelé rotations doivent avoir lieu afin de rééquilibrer l'arbre. Garder un arbre équilibré assure que le temps de recherche moyen de n'importe quel nœud est optimal . Surcharge importante est nécessaire pour maintenir l'équilibre d'un arbre.
Dégénéré Binary Tree
Un arbre binaire dégénéré est celui dans lequel chaque noeud à l'exception du nœud feuille a exactement un nœud enfant . Il a les mêmes caractéristiques de performance d'une liste chaînée , ce qui augmente le temps de recherche d' un nœud d'un montant considérable . Par exemple, prenons un cas dans lequel le noeud recherché est le nœud de la feuille. La totalité de l'arbre doit être parcouru pour trouver ce nœud. Avec un arbre binaire équilibré , en trouvant un noeud de feuille ne nécessite un certain nombre de traversées de noeud correspondant à la profondeur du noeud feuille . Avec de grands arbres , la différence de performance peut être importante.
|
