Share
Jusqu'à présent, nous avons examiné les structures de données qui organisent les données de manière linéaire. Les listes liées contiennent des données d'un seul nœud de départ vers un seul nœud de terminaison. Les tableaux contiennent des données dans des blocs unidimensionnels contigus.
Dans cette section, nous verrons comment l'ajout d'une dimension supplémentaire nous permettra d'introduire une nouvelle structure de données: l'arborescence. Plus précisément, nous examinerons un type d’arbre appelé arbre de recherche binaire. Les arbres de recherche binaires prennent l'arborescence générale et appliquent un ensemble de règles simples qui définissent la structure de l'arborescence.
Avant de connaître ces règles, apprenons ce qu'est un arbre.
Une arborescence est une structure de données où chaque nœud a zéro enfant ou plus. Par exemple, nous pourrions avoir un arbre comme celui-ci:
Une structure arborescente Dans cet arbre, nous pouvons voir la structure organisationnelle d'une entreprise. Les blocs représentent des personnes ou des divisions au sein de l'entreprise et les lignes représentent des relations hiérarchiques. Un arbre est un moyen très efficace et logique de présenter et de stocker cette information.
L'arbre montré dans la figure précédente est un arbre général. Il représente les relations parent / enfant, mais il n'y a pas de règles pour la structure. Le PDG a un rapport direct mais pourrait tout aussi bien n'en avoir aucun ou vingt. Dans la figure, les ventes sont représentées à gauche de Marketing, mais cette commande n'a aucune signification. En fait, la seule contrainte observable est que chaque nœud a au plus un parent (et le nœud le plus haut, le conseil d'administration, n'a pas de parent)..
Un arbre de recherche binaire utilise la même structure de base que l’arbre général présenté dans la dernière figure, mais avec l’ajout de quelques règles. Ces règles sont:
Regardons un arbre qui est construit en utilisant ces règles:
Arbre de recherche binaire Remarquez comment les contraintes que nous avons spécifiées sont appliquées dans le diagramme. Chaque valeur située à gauche du nœud racine (huit) a une valeur inférieure à huit et chaque valeur située à droite est supérieure ou égale au nœud racine. Cette règle s'applique de manière récursive à chaque nœud le long du chemin.
En pensant à cet arbre, réfléchissons aux étapes qui ont précédé sa construction. Lorsque le processus a démarré, l’arbre était vide, puis une valeur, huit, a été ajoutée. Parce que c’était la première valeur ajoutée, il a été placé à la position racine (parent ultime).
Nous ne connaissons pas l'ordre exact dans lequel les autres nœuds ont été ajoutés, mais je vais présenter un chemin possible. Les valeurs seront ajoutées en utilisant une méthode nommée Ajouter qui accepte la valeur.
BinaryTree tree = new BinaryTree (); tree.Add (8); arbre.Ajouter (4); arbre.Add (2); arbre.Ajouter (3); arbre.Ajouter (10); arbre.Ajouter (6); arbre.Ajouter (7);
Passons en revue les premiers articles.
Huit a été ajouté en premier et est devenu la racine. Ensuite, quatre ont été ajoutés. Comme quatre est inférieur à huit, il doit être placé à gauche de huit, conformément à la règle numéro deux. Comme huit n'a pas d'enfant à gauche, quatre devient l'enfant immédiatement gauche de huit.
Deux est ajouté ensuite. deux est inférieur à huit, donc il va à gauche. Il y a déjà un nœud à gauche de huit, donc la logique de comparaison est exécutée à nouveau. deux ont moins de quatre ans et quatre n'ont pas d'enfant gauche, alors deux deviennent l'enfant gauche de quatre.
Trois est ajouté ensuite et va à gauche de huit et quatre. Comparé au nœud deux, il est plus grand, donc trois sont ajoutés à la droite de deux, conformément à la règle numéro trois..
Ce cycle de comparaison de valeurs sur chaque nœud, puis de vérification répétée de chaque enfant jusqu'à ce que l'emplacement correct soit trouvé, est répété pour chaque valeur jusqu'à ce que la structure arborescente finale soit créée..
le BinaryTreeNode représente un seul nœud dans l'arborescence. Il contient des références aux enfants gauche et droit (null s'il n'y en a pas), à la valeur du nœud et à la IComparable.CompareTo méthode qui permet de comparer les valeurs de noeud pour déterminer si elle doit être placée à gauche ou à droite du noeud actuel. C'est la totalité BinaryTreeNode classe-comme vous pouvez le voir, c'est très simple.
class BinaryTreeNode: IComparable où TNode: IComparable public BinaryTreeNode (valeur du TNode) Valeur = valeur; public BinaryTreeNode Left get; ensemble; public BinaryTreeNode Right get; ensemble; public TNode Value get; ensemble privé; /// /// Compare le nœud actuel à la valeur fournie. /// /// Valeur du noeud à comparer à /// 1 si la valeur de l'instance est supérieure à /// la valeur fournie, -1 si inférieur ou égal à 0. public int CompareTo (TNode other) return Value.CompareTo (other);
le BinaryTree class fournit les méthodes de base dont vous avez besoin pour manipuler l'arbre: Ajouter, Retirer, une Contient méthode pour déterminer si un élément existe dans l’arbre, plusieurs méthodes de traversée et d’énumération (ce sont des méthodes qui nous permettent d’énumérer les noeuds de l’arbre dans divers ordres bien définis), et les méthodes normales. Compter et Clair les méthodes.
Pour initialiser l’arbre, il existe un BinaryTreeNode référence qui représente le nœud principal (racine) de l'arborescence et un nombre entier qui enregistre le nombre d'éléments contenus dans l'arborescence.
Classe publique BinaryTree: IEnumerable où T: IComparable private BinaryTreeNode _head; int_count privé; public void Add (valeur T) lance une nouvelle NotImplementedException (); public bool Contains (valeur T) lance une nouvelle NotImplementedException (); public bool Remove (valeur T) lance new NotImplementedException (); public void PreOrderTraversal (Action action) lance new NotImplementedException (); public void PostOrderTraversal (Action action) lance new NotImplementedException (); public void InOrderTraversal (action action) lance new NotImplementedException (); public IEnumerator GetEnumerator () lance new NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () lance new NotImplementedException (); public void Clear () lance new NotImplementedException (); public int Count get;
| Comportement | Ajoute la valeur fournie à l'emplacement correct dans l'arborescence. |
| Performance | O (log n) en moyenne; O (n) dans le pire des cas. |
L'ajout d'un nœud à l'arborescence n'est pas terriblement complexe et est encore plus facile lorsque le problème est simplifié en un algorithme récursif. Deux cas doivent être pris en compte:
Dans le premier cas, nous allouons simplement le nouveau nœud et l'ajoutons à l'arborescence. Dans le second cas, nous comparons la valeur à la valeur du nœud. Si la valeur que nous essayons d'ajouter est inférieure à la valeur du nœud, l'algorithme est répété pour l'enfant de gauche du nœud. Sinon, il est répété pour l'enfant de droite du nœud.
public void Add (valeur T) // Cas 1: l'arborescence est vide. Allouer la tête. if (_head == null) _head = new BinaryTreeNode (value); // Cas 2: L'arbre n'est pas vide, donc // trouvez récursivement // le bon emplacement pour insérer le nœud. else AddTo (_head, value); _count ++; // Algorithme d'ajout récursif. Void privé AddTo (noeud BinaryTreeNode, valeur T) // Cas 1: la valeur est inférieure à la valeur du noeud actuel if (value.CompareTo (node.Value) < 0) // If there is no left child, make this the new left, if (node.Left == null) node.Left = new BinaryTreeNode(value); else // else add it to the left node. AddTo(node.Left, value); // Case 2: Value is equal to or greater than the current value. else // If there is no right, add it to the right, if (node.Right == null) node.Right = new BinaryTreeNode(value); else // else add it to the right node. AddTo(node.Right, value);
| Comportement | Supprime le premier lieu trouvé avec la valeur indiquée. |
| Performance | O (log n) en moyenne; O (n) dans le pire des cas. |
Supprimer une valeur de l'arborescence est une opération conceptuellement simple qui devient étonnamment complexe en pratique..
A un niveau élevé, l'opération est simple:
La première étape est simple et, comme nous le verrons plus loin, est réalisée à l'aide du même mécanisme que celui utilisé par la méthode Contains. Une fois que le noeud à supprimer est identifié, toutefois, l'opération peut emprunter l'un des trois chemins dictés par l'état de l'arborescence autour du noeud à supprimer. Les trois états sont décrits dans les trois cas suivants.
Premier cas: le noeud à supprimer n'a pas d'enfant de droite.
Cas 1 Le noeud à supprimer n'a pas d'enfant de droite Dans ce cas, l'opération de suppression peut simplement déplacer l'enfant de gauche, s'il en existe un, à la place du nœud supprimé. L'arbre résultant ressemblerait à ceci:
Cas 1 - Etat de l'arbre après l'abattage Deuxième cas: le noeud à supprimer a un enfant droit qui, à son tour, n’a pas d’enfant gauche.
Deuxième cas Le noeud à supprimer a un enfant de droite qui n'a pas d'enfant de gauche Dans ce cas, nous voulons déplacer le bon enfant (six) du noeud supprimé à la place du noeud supprimé. L'arbre résultant ressemblera à ceci:
Etat de l'arbre après l'enlèvement Troisième cas: le nœud à supprimer a un enfant droit qui, à son tour, a un enfant gauche.
Cas 3 - Le nœud à supprimer a un enfant droit qui a un enfant gauche Dans ce cas, l'enfant le plus à gauche de l'enfant à droite du noeud supprimé doit être placé dans l'emplacement du noeud supprimé..
Prenons une minute pour réfléchir à la raison pour laquelle cela est vrai. Nous connaissons deux faits concernant le sous-arbre commençant par le nœud en cours de suppression (par exemple, le sous-arbre dont la racine est le nœud avec la valeur cinq).
Nous devons placer une valeur dans l'emplacement du nœud supprimé qui est inférieure ou égale à chaque nœud situé à sa droite. Pour ce faire, nous devons obtenir la plus petite valeur du côté droit. Nous avons donc besoin du nœud le plus à gauche de l'enfant de droite..
Après la suppression du noeud, l’arbre ressemblera à ceci:
Cas 3 - Suppression de l’arbre après le nœud Maintenant que nous comprenons les trois scénarios de suppression, examinons le code pour y arriver..
Une chose à noter: le FindWithParent La méthode (voir la section Contient) renvoie le nœud à supprimer ainsi que le parent du nœud à supprimer. Ceci est fait car lorsque le nœud est supprimé, nous devons mettre à jour celui du parent. La gauche ou Droite propriété pour pointer vers le nouveau noeud.
Nous pourrions éviter cela si tous les nœuds conservaient une référence à leur parent, mais cela entraînerait une surcharge de mémoire et une comptabilité par nœud qui ne sont nécessaires que dans ce cas..
public bool Remove (valeur T) BinaryTreeNode current, parent; // Trouver le noeud à supprimer. current = FindWithParent (valeur, parent hors); if (current == null) return false; _compter--; // Cas 1: Si current n'a pas d'enfant de droite, la gauche de current remplace current. if (current.Right == null) if (parent == null) _head = current.Left; else int result = parent.CompareTo (current.Value); if (result> 0) // Si la valeur parent est supérieure à la valeur actuelle, // fait de l'enfant gauche actuel un enfant gauche du parent. parent.Left = current.Left; else if (résultat < 0) // If parent value is less than current value, // make the current left child a right child of parent. parent.Right = current.Left; // Case 2: If current's right child has no left child, current's right child // replaces current. else if (current.Right.Left == null) current.Right.Left = current.Left; if (parent == null) _head = current.Right; else int result = parent.CompareTo(current.Value); if (result > 0) // Si la valeur parent est supérieure à la valeur actuelle, // fait de l'enfant de droite actuel un enfant de gauche du parent. parent.Left = current.Right; else if (résultat < 0) // If parent value is less than current value, // make the current right child a right child of parent. parent.Right = current.Right; // Case 3: If current's right child has a left child, replace current with current's // right child's left-most child. else // Find the right's left-most child. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) leftmostParent = leftmost; leftmost = leftmost.Left; // The parent's left subtree becomes the leftmost's right subtree. leftmostParent.Left = leftmost.Right; // Assign leftmost's left and right to current's left and right children. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) _head = leftmost; else int result = parent.CompareTo(current.Value); if (result > 0) // Si la valeur parent est supérieure à la valeur actuelle, // place à l'extrême gauche l'enfant gauche du parent. parent.Left = leftmost; else if (résultat < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Comportement | Renvoie true si l'arbre contient la valeur fournie. Sinon, il retourne faux. |
| Performance | O (log n) en moyenne; O (n) dans le pire des cas. |
Contient reporte à FindWithParent, qui exécute un algorithme simple d'arborescence qui effectue les étapes suivantes, en commençant au nœud principal:
Puisque Contient renvoie un Booléen, la valeur renvoyée est déterminée par si FindWithParent retourne un non-null BinaryTreeNode (vrai) ou nul (faux).
le FindWithParent Cette méthode est également utilisée par la méthode Remove. Le paramètre out, parent, n'est pas utilisé par Contient.
public bool Contains (valeur T) // Fait référence à la fonction d'assistance à la recherche de noeud. BinaryTreeNode parent; return FindWithParent (value, out parent)! = null; /// /// Recherche et retourne le premier nœud contenant la valeur spécifiée. Si la valeur /// n'est pas trouvée, elle renvoie null. Retourne également le parent du nœud trouvé (ou null) /// qui est utilisé dans Supprimer. /// private BinaryTreeNode FindWithParent (valeur T, hors parent BinaryTreeNode) // Maintenant, essayez de trouver des données dans l'arborescence. BinaryTreeNode current = _head; parent = null; // Bien que nous n'ayons pas de correspondance… while (current! = Null) int result = current.CompareTo (value); if (result> 0) // Si la valeur est inférieure à current, allez à gauche. parent = courant; current = current.Left; else if (résultat < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Comportement | Retourne le nombre de valeurs dans l'arbre (0 si vide). |
| Performance | O (1) |
Le champ de compte est incrémenté de la Ajouter méthode et décrémenté par le Retirer méthode.
public int Count get return _count;
| Comportement | Supprime tous les nœuds de l'arbre. |
| Performance | O (1) |
public void Clear () _head = null; _count = 0;
Les traversées d'arbres sont des algorithmes permettant de traiter chaque valeur de l'arbre dans un ordre bien défini. Pour chacun des algorithmes discutés, l’arbre suivant sera utilisé comme exemple d’entrée..
Les exemples qui suivent acceptent tous un action paramètre. Ce paramètre définit l'action qui sera appliquée à chaque nœud lors de son traitement par la traversée..
La section Ordre pour chaque parcours indiquera l’ordre dans lequel l’arbre suivant serait traversé.
L'arbre d'échantillon pour les résultats de classement de traversée | Comportement | Effectue l'action fournie sur chaque valeur en pré-commande (voir la description ci-après).. |
| Performance | Sur) |
| Ordre | 4, 2, 1, 3, 5, 7, 6, 8 |
La traversée de précommande traite le nœud actuel avant de passer aux enfants gauche et droit. À partir du nœud racine quatre, l'action est exécutée avec la valeur quatre. Ensuite, le nœud gauche et tous ses enfants sont traités, suivis du nœud droit et de tous ses enfants..
Une utilisation courante de la traversée des pré-commandes serait de créer une copie de l’arborescence contenant non seulement les mêmes valeurs de nœud, mais également la même hiérarchie..
public void PreOrderTraversal (Action action) PreOrderTraversal (action, _head); private void PreOrderTraversal (Action, Nœud BinaryTreeNode) if (node! = null) action (node.Value); PreOrderTraversal (action, node.Left); PreOrderTraversal (action, node.Right);
| Comportement | Effectue l'action fournie sur chaque valeur en post-commande (voir la description ci-après).. |
| Performance | Sur) |
| Ordre | 1, 3, 2, 6, 8, 7, 5, 4 |
La traversée postorder visite les enfants gauche et droit du nœud de manière récursive, puis exécute l'action sur le nœud actuel une fois les enfants terminés..
Les traversées postérieures sont souvent utilisées pour supprimer un arbre entier, par exemple dans les langages de programmation dans lesquels chaque nœud doit être libéré, ou pour supprimer des sous-arbres. C’est le cas parce que le noeud racine est traité (supprimé) en dernier et que ses enfants sont traités de manière à minimiser la quantité de travail que le Retirer algorithme doit effectuer.
public void PostOrderTraversal (Action action) PostOrderTraversal (action, _head); void privé PostOrderTraversal (action, noeud BinaryTreeNode) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (action, node.Right); action (node.Value);
| Comportement | Effectue l'action fournie sur chaque valeur de en ordre (voir la description qui suit). |
| Performance | Sur) |
| Ordre | 1, 2, 3, 4, 5, 6, 7, 8 |
Lors du traitement transversal des ordres dans l'ordre de tri des nœuds, dans l'exemple précédent, les nœuds seraient triés par ordre numérique, du plus petit au plus grand. Pour ce faire, il recherche le plus petit noeud (le plus à gauche), puis le traite avant de traiter les plus gros (à droite).
Les traversées dans l'ordre sont utilisées chaque fois que les nœuds doivent être traités dans l'ordre de tri.
L'exemple suivant montre deux méthodes différentes pour effectuer une traversée dans l'ordre. La première implémente une approche récursive qui effectue un rappel pour chaque nœud traversé. La seconde supprime la récursivité grâce à l’utilisation de la structure de données Stack et renvoie un IEnumerator pour permettre le dénombrement direct.
Public void InOrderTraversal (Action action) InOrderTraversal (action, _head); void privé InOrderTraversal (action, noeud BinaryTreeNode) if (node! = null) InOrderTraversal (action, node.Left); action (node.Value); InOrderTraversal (action, node.Right); public IEnumerator InOrderTraversal () // Ceci est un algorithme non récursif utilisant une pile pour démontrer la suppression de // la récursivité. if (_head! = null) // Stocke les noeuds que nous avons ignorés dans cette pile (évite la récursion). Stack> stack = new Stack> (); BinaryTreeNode current = _head; // Lors de la suppression de la récursivité, nous devons // savoir si nous devrions aller au nœud gauche ou aux nœuds droits ensuite. bool goLeftNext = true; // Commencez par pousser Head sur la pile. stack.Push (en cours); while (stack.Count> 0) // Si nous nous dirigeons vers la gauche… if (goLeftNext) // Place tout sauf le nœud le plus à gauche dans la pile. // Nous allons donner le plus à gauche après ce bloc. while (current.Left! = null) stack.Push (current); current = current.Left; // Inorder is left-> yield-> right. rendement retour actuel.Valeur; // Si nous pouvons aller à droite, fais-le. if (current.Right! = null) current = current.Right; // Une fois que nous sommes allés bien une fois, nous devons commencer // aller encore à gauche. goLeftNext = true; else // Si nous ne pouvons pas aller à droite, nous devons alors supprimer le nœud parent // pour pouvoir le traiter, puis accéder au nœud de droite. current = stack.Pop (); goLeftNext = false;
| Comportement | Renvoie un énumérateur qui énumère à l'aide de l'algorithme de parcours InOrder.. |
| Performance | O (1) pour renvoyer l'énumérateur. Énumérer tous les éléments est O (n). |
IEnumerator public GetEnumerator () return InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua