Share
Finora abbiamo esaminato le strutture dati che organizzano i dati in modo lineare. Gli elenchi collegati contengono dati da un singolo nodo iniziale a un singolo nodo di terminazione. Le matrici tengono i dati in blocchi contigui e unidimensionali.
In questa sezione vedremo come aggiungere una nuova dimensione ci permetterà di introdurre una nuova struttura dati: l'albero. Nello specifico, esamineremo un tipo di albero noto come albero di ricerca binario. Gli alberi di ricerca binaria prendono la struttura ad albero generale e applicano una serie di regole semplici che definiscono la struttura dell'albero.
Prima di conoscere queste regole, impariamo cos'è un albero.
Un albero è una struttura di dati in cui ogni nodo ha zero o più figli. Ad esempio, potremmo avere un albero come questo:
Una struttura ad albero organizzativa In questo albero, possiamo vedere la struttura organizzativa di un'azienda. I blocchi rappresentano persone o divisioni all'interno dell'azienda e le linee rappresentano relazioni di segnalazione. Un albero è un modo molto efficace e logico per presentare e archiviare queste informazioni.
L'albero mostrato nella figura precedente è un albero generale. Rappresenta le relazioni genitori / figli, ma non ci sono regole per la struttura. L'amministratore delegato ha un rapporto diretto ma potrebbe altrettanto facilmente non avere nessuno o venti. Nella figura, le vendite sono visualizzate a sinistra di Marketing, ma quell'ordinamento non ha significato. In effetti, l'unico vincolo osservabile è che ogni nodo ha al massimo un genitore (e il nodo più in alto, il Consiglio di amministrazione, non ha un genitore).
Un albero di ricerca binario utilizza la stessa struttura di base dell'albero generale mostrato nell'ultima figura ma con l'aggiunta di alcune regole. Queste regole sono:
Diamo un'occhiata a un albero che viene costruito utilizzando queste regole:
Albero di ricerca binario Osserva come i vincoli che abbiamo specificato vengono applicati nel diagramma. Ogni valore a sinistra del nodo radice (otto) ha un valore inferiore a otto e ogni valore a destra è maggiore o uguale al nodo radice. Questa regola si applica in modo ricorsivo ad ogni nodo lungo la strada.
Con questo albero in mente, pensiamo ai passi che sono stati fatti per costruirlo. Quando il processo è iniziato, l'albero era vuoto e quindi è stato aggiunto un valore, otto. Poiché è stato il primo valore aggiunto, è stato inserito nella posizione radice (genitore finale).
Non conosciamo l'ordine esatto in cui sono stati aggiunti gli altri nodi, ma presenterò un possibile percorso. I valori verranno aggiunti utilizzando un metodo chiamato Inserisci che accetta il valore.
Albero BinaryTree = new BinaryTree (); tree.Add (8); tree.Add (4); tree.Add (2); tree.Add (3); tree.Add (10); tree.Add (6); tree.Add (7);
Passiamo attraverso i primi elementi.
Otto è stato aggiunto per primo e divenne la radice. Successivamente, quattro sono stati aggiunti. Poiché quattro sono meno di otto, è necessario andare a sinistra di otto come da regola numero due. Poiché otto non ha un bambino alla sua sinistra, quattro diventano l'immediato figlio di otto di sinistra.
Due sono aggiunti in seguito. due sono meno di otto, quindi va a sinistra. C'è già un nodo a sinistra di otto, quindi la logica di confronto viene eseguita di nuovo. due sono meno di quattro e quattro non hanno figli rimasti, quindi due diventano il figlio di quattro di sinistra.
Tre sono aggiunti in seguito e vanno a sinistra di otto e quattro. Se confrontato con i due nodi, è più grande, quindi tre è aggiunto alla destra di due come da regola numero tre.
Questo ciclo di confronto dei valori su ciascun nodo e quindi il controllo di ogni bambino più e più volte finché non viene trovato lo slot appropriato viene ripetuto per ogni valore fino a quando non viene creata la struttura finale dell'albero.
Il BinaryTreeNode rappresenta un singolo nodo nell'albero. Contiene riferimenti ai figli sinistro e destro (null se non ce ne sono), il valore del nodo e il IComparable.CompareTo metodo che consente di confrontare i valori del nodo per determinare se il valore dovrebbe andare a sinistra oa destra del nodo corrente. Questo è l'intero BinaryTreeNode la classe, come puoi vedere, è molto semplice.
class BinaryTreeNode: IComparable dove TNode: IComparable public BinaryTreeNode (valore TNode) Value = value; public BinaryTreeNode Left get; impostato; public BinaryTreeNode Right get; impostato; Valore pubblico TNode get; set privato; /// /// Confronta il nodo corrente con il valore fornito. /// /// Il valore del nodo da confrontare con /// 1 se il valore dell'istanza è maggiore di /// il valore fornito, -1 se inferiore o 0 se uguale. public int CompareTo (altro TNode) return Value.CompareTo (altro);
Il BinaryTree class fornisce i metodi di base necessari per manipolare l'albero: Inserisci, Rimuovere, un contiene metodo per determinare se un oggetto esiste nell'albero, diversi metodi di attraversamento e di enumerazione (questi sono metodi che ci permettono di enumerare i nodi nell'albero in vari ordini ben definiti), e il normale Contare e Chiaro metodi.
Per inizializzare l'albero, c'è a BinaryTreeNode riferimento che rappresenta il nodo head (root) dell'albero e c'è un numero intero che tiene traccia di quanti oggetti sono presenti nell'albero.
public class BinaryTree: IEnumerable dove T: IComparable private BinaryTreeNode _head; privato int _count; pubblico vuoto Aggiungi (valore T) lancia nuova NotImplementedException (); public bool Contains (valore T) throw new NotImplementedException (); public bool Remove (valore T) throw new NotImplementedException (); public void PreOrderTraversal (Azione azione) throw new NotImplementedException (); public void PostOrderTraversal (Azione azione) throw new NotImplementedException (); public void InOrderTraversal (Action action) throw new NotImplementedException (); public IEnumerator GetEnumerator () throw new NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () throw new NotImplementedException (); public void Clear () throw new NotImplementedException (); public int Count get;
| Comportamento | Aggiunge il valore fornito alla posizione corretta all'interno dell'albero. |
| Prestazione | O (log n) in media; O (n) nel peggiore dei casi. |
L'aggiunta di un nodo all'albero non è terribilmente complessa e diventa ancora più semplice quando il problema viene semplificato in un algoritmo ricorsivo. Ci sono due casi che devono essere considerati:
Nel primo caso, assegniamo semplicemente il nuovo nodo e lo aggiungiamo all'albero. Nel secondo caso, confrontiamo il valore con il valore del nodo. Se il valore che stiamo cercando di aggiungere è inferiore al valore del nodo, l'algoritmo viene ripetuto per il figlio sinistro del nodo. Altrimenti, viene ripetuto per il figlio destro del nodo.
pubblico vuoto Aggiungi (valore T) // Caso 1: l'albero è vuoto. Assegna la testa. if (_head == null) _head = new BinaryTreeNode (valore); // Caso 2: l'albero non è vuoto, quindi ricorsivamente // trova la posizione giusta per inserire il nodo. else AddTo (_head, value); _count ++; // Algoritmo di aggiunta ricorsiva. AddTo vuoto privato (nodo BinaryTreeNode, valore T) // Caso 1: il valore è inferiore al valore corrente del nodo 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);
| Comportamento | Rimuove il primo nore trovato con il valore indicato. |
| Prestazione | O (log n) in media; O (n) nel peggiore dei casi. |
Rimuovere un valore dall'albero è un'operazione concettualmente semplice che diventa sorprendentemente complessa nella pratica.
Ad un livello elevato, l'operazione è semplice:
Il primo passaggio è semplice e, come vedremo, viene realizzato utilizzando lo stesso meccanismo utilizzato dal metodo Contains. Una volta identificato il nodo da rimuovere, tuttavia, l'operazione può richiedere uno dei tre percorsi dettati dallo stato dell'albero attorno al nodo da rimuovere. I tre stati sono descritti nei seguenti tre casi.
Caso 1: il nodo da rimuovere non ha figli giusti.
Caso 1 Il nodo da rimuovere non ha figli giusti In questo caso, l'operazione di rimozione può semplicemente spostare il figlio sinistro, se ce n'è uno, nella posizione del nodo rimosso. L'albero risultante sarebbe simile a questo:
Caso 1: stato dell'albero dopo la rimozione Caso Due: il nodo da rimuovere ha un figlio destro che, a sua volta, non ha figli lasciati.
Caso due Il nodo da rimuovere ha un figlio destro che non ha figli sinistra In questo caso, vogliamo spostare il figlio destro del nodo rimosso (sei) nella posizione del nodo rimosso. L'albero risultante sarà simile a questo:
Stato dell'albero dopo la rimozione Terzo caso: il nodo da rimuovere ha un figlio destro che, a sua volta, ha un figlio sinistro.
Caso 3: il nodo da rimuovere ha un figlio destro che ha un figlio sinistro In questo caso, il figlio di sinistra del figlio destro del nodo rimosso deve essere posizionato nello slot del nodo rimosso.
Prendiamoci un minuto per riflettere sul perché questo è vero. Ci sono due fatti che sappiamo del sotto-albero che inizia con il nodo che viene rimosso (ad esempio, il sotto-albero la cui radice è il nodo con il valore cinque).
Abbiamo bisogno di inserire un valore nello slot del nodo rimosso che è inferiore o uguale a ogni nodo alla sua destra. Per fare ciò, abbiamo bisogno di ottenere il valore più piccolo sul lato destro. Quindi abbiamo bisogno del nodo più a sinistra del bambino giusto.
Dopo la rimozione del nodo, l'albero sarà simile a questo:
Caso 3: rimozione di albero dopo nodo Ora che comprendiamo i tre scenari di rimozione, diamo un'occhiata al codice per farlo accadere.
Una cosa da notare: The FindWithParent metodo (vedere la sezione Contiene) restituisce il nodo da rimuovere e il genitore del nodo rimosso. Questo perché quando il nodo viene rimosso, è necessario aggiornare i genitori Sinistra o Destra proprietà per indicare il nuovo nodo.
Potremmo evitare di farlo se tutti i nodi avessero un riferimento al loro genitore, ma ciò avrebbe comportato un sovraccarico della memoria per nodo e costi di contabilità necessari solo in questo caso.
public bool Remove (valore T) BinaryTreeNode current, parent; // Trova il nodo da rimuovere. current = FindWithParent (valore, out parent); if (current == null) return false; _contare--; // Caso 1: se la corrente non ha figli destra, la corrente a sinistra sostituisce la corrente. if (current.Right == null) if (parent == null) _head = current.Left; else int result = parent.CompareTo (current.Value); if (risultato> 0) // Se il valore genitore è maggiore del valore corrente, // rende il figlio sinistro corrente un figlio sinistro del genitore. parent.Left = current.Left; else if (result < 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) // Se il valore genitore è maggiore del valore corrente, // crea il figlio destro corrente come figlio sinistro del genitore. parent.Left = current.Right; else if (result < 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) // Se il valore genitore è maggiore del valore corrente, // rende a sinistra il figlio sinistro del genitore. parent.Left = leftmost; else if (result < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Comportamento | Restituisce true se l'albero contiene il valore fornito. Altrimenti restituisce falso. |
| Prestazione | O (log n) in media; O (n) nel peggiore dei casi. |
contiene rimanda a FindWithParent, che esegue un semplice algoritmo di tree-walking che esegue i seguenti passi, iniziando dal nodo principale:
Da contiene restituisce a booleano, il valore restituito è determinato dal fatto FindWithParent restituisce un valore non nullo BinaryTreeNode (true) o null (false).
Il FindWithParent il metodo è usato anche dal metodo Remove. Il parametro out, parent, non è utilizzato da contiene.
public bool Contains (valore T) // Rimanda alla funzione helper di ricerca del nodo. BinaryTreeNode parent; return FindWithParent (value, out parent)! = null; /// /// Trova e restituisce il primo nodo contenente il valore specificato. Se il valore /// non viene trovato, restituisce null. Restituisce anche il genitore del nodo trovato (o null) /// che viene utilizzato in Rimuovi. /// BinaryTreeNode privato FindWithParent (valore T, out BinaryTreeNode parent) // Ora, prova a trovare i dati nell'albero. BinaryTreeNode current = _head; parent = null; // Anche se non abbiamo una corrispondenza ... while (corrente! = Null) int result = current.CompareTo (valore); if (risultato> 0) // Se il valore è inferiore a corrente, andare a sinistra. genitore = corrente; current = current.Left; else if (result < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Comportamento | Restituisce il numero di valori nell'albero (0 se vuoto). |
| Prestazione | O (1) |
Il campo count viene incrementato dal Inserisci metodo e decrementato dal Rimuovere metodo.
conteggio int pubblico get return _count;
| Comportamento | Rimuove tutti i nodi dall'albero. |
| Prestazione | O (1) |
public void Clear () _head = null; _count = 0;
Gli attraversamenti degli alberi sono algoritmi che consentono di elaborare ciascun valore nell'albero in un ordine ben definito. Per ciascuno degli algoritmi discussi, verrà utilizzato il seguente albero come input del campione.
Gli esempi che seguono tutti accettano un Azione parametro. Questo parametro definisce l'azione che verrà applicata a ciascun nodo mentre viene elaborato dall'incrocio.
La sezione Ordine per ogni attraversamento indicherà l'ordine in cui verrebbe attraversato il seguente albero.
L'albero dei campioni per i risultati di ordinamento trasversale | Comportamento | Esegue l'azione fornita su ciascun valore in preordine (vedere la descrizione che segue). |
| Prestazione | Sopra) |
| Ordine | 4, 2, 1, 3, 5, 7, 6, 8 |
L'attraversamento pre-ordine elabora il nodo corrente prima di spostarsi a sinistra e quindi a destra. A partire dal nodo radice, quattro, l'azione viene eseguita con il valore quattro. Quindi vengono elaborati il nodo sinistro e tutti i relativi figli, seguito dal nodo destro e da tutti i relativi figli.
Un uso comune del preorder traversal sarebbe quello di creare una copia dell'albero che contenesse non solo gli stessi valori del nodo, ma anche la stessa gerarchia.
public void PreOrderTraversal (Action action) PreOrderTraversal (action, _head); private void PreOrderTraversal (Action action, BinaryTreeNode node) if (node! = null) action (node.Value); PreOrderTraversal (action, node.Left); PreOrderTraversal (action, node.Right);
| Comportamento | Esegue l'azione fornita su ciascun valore nel post ordine (vedere la descrizione che segue). |
| Prestazione | Sopra) |
| Ordine | 1, 3, 2, 6, 8, 7, 5, 4 |
L'attraversamento postorder visita ricorsivamente il figlio sinistro e destro del nodo e quindi esegue l'azione sul nodo corrente dopo che i bambini sono completi.
Gli attraversamenti postorder vengono spesso utilizzati per eliminare un intero albero, ad esempio nei linguaggi di programmazione in cui ogni nodo deve essere liberato o per eliminare i sottoalberi. Questo è il caso perché il nodo radice viene elaborato (cancellato) per ultimo e i suoi figli vengono elaborati in un modo che ridurrà al minimo la quantità di lavoro Rimuovere l'algoritmo deve essere eseguito.
pubblico vuoto PostOrderTraversal (Azione azione) PostOrderTraversal (azione, _head); private void PostOrderTraversal (Action action, BinaryTreeNode node) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (action, node.Right); azione (node.Value);
| Comportamento | Esegue l'azione fornita su ciascun valore in In ordine (vedi la descrizione che segue). |
| Prestazione | Sopra) |
| Ordine | 1, 2, 3, 4, 5, 6, 7, 8 |
Inorder traversal elabora i nodi nell'ordine di ordinamento: nell'esempio precedente, i nodi sarebbero ordinati in ordine numerico dal più piccolo al più grande. Lo fa trovando il nodo più piccolo (a sinistra) e poi elaborandolo prima di elaborare i nodi più grandi (a destra).
Gli attraversamenti inorder vengono utilizzati ogni volta che i nodi devono essere elaborati in ordine.
L'esempio che segue mostra due diversi metodi per eseguire un attraversamento inorder. Il primo implementa un approccio ricorsivo che esegue un callback per ogni nodo attraversato. Il secondo rimuove la ricorsione attraverso l'uso della struttura dati dello Stack e restituisce un IEnumerator per consentire l'enumerazione diretta.
Vuoto pubblico InOrderTraversal (Azione azione) InOrderTraversal (action, _head); private void InOrderTraversal (Action action, BinaryTreeNode node) if (node! = null) InOrderTraversal (action, node.Left); azione (node.Value); InOrderTraversal (action, node.Right); public IEnumerator InOrderTraversal () // Questo è un algoritmo non ricorsivo che utilizza uno stack per dimostrare la rimozione di // ricorsione. if (_head! = null) // Archivia i nodi che abbiamo saltato in questa pila (evita la ricorsione). Stack> stack = new Stack> (); BinaryTreeNode current = _head; // Quando rimuoviamo la ricorsione, dobbiamo tenere traccia del fatto che // dovremmo andare al nodo di sinistra o ai nodi di destra dopo. bool goLeftNext = true; // Inizia spingendo Head in pila. stack.Push (corrente); while (stack.Count> 0) // Se stiamo andando a sinistra ... if (goLeftNext) // Spingi tutto tranne il nodo più a sinistra nello stack. // Faremo il più a sinistra dopo questo blocco. while (current.Left! = null) stack.Push (corrente); current = current.Left; // Inorder è left-> yield-> right. resa resa corrente.Valore; // Se possiamo andare bene, fallo. if (current.Right! = null) current = current.Right; // Una volta che siamo andati a destra una volta, dobbiamo iniziare // a sinistra di nuovo. goLeftNext = true; else // Se non possiamo andare bene, allora abbiamo bisogno di uscire dal nodo genitore // in modo che possiamo processarlo e poi andare al suo nodo giusto. current = stack.Pop (); goLeftNext = falso;
| Comportamento | Restituisce un enumeratore che enumera utilizzando l'algoritmo Traversal InOrder. |
| Prestazione | O (1) per restituire l'enumeratore. L'enumerazione di tutti gli elementi è O (n). |
public IEnumerator GetEnumerator () return InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua