Hai riscoperto un paio di cose ...
-
"Albero binario" non significa automaticamente "albero di ricerca binario".
-
Il modulo di testo di una struttura dati non è la fine della storia. Le strutture dati possono essere adattate e "aumentate". Alcune strutture dati aumentate sono esempi di libri di testo a pieno titolo, ad es. alberi intervallati .
L'aggiunta di dati di riepilogo aggiuntivi a ciascun nodo è un trucco abbastanza comune con strutture di dati ad albero. Uno dei miei preferiti è l'inclusione di informazioni sulle dimensioni del sottostrato accanto a sintesi chiave. In questo modo, ho dei contenitori che possono facilmente supportare l'accesso con pedice e la ricerca basata su chiave. Nel mio caso, si tratta di alberi a più vie con tutti gli elementi di dati nei nodi foglia (fondamentalmente alberi B +). Quindi le chiavi nei nodi del ramo sono in realtà solo un'altra forma di sommario - la prima (o ultima) chiave nella sottostruttura. Con entrambi i tipi di sottostruttura e tasti discreti, un altro trucco utile a volte è la possibilità di cercare in O (log n) il tempo per la chiave più bassa > = un minimo che non è già presente nell'albero.
E ovviamente, è altrettanto valido non avere chiavi se non ne hai bisogno. Un contenitore che supporta la sottoscrizione ma non la ricerca basata sulla chiave è, ovviamente, un vettore o una matrice. Una versione ad albero multiway potrebbe essere appropriata se hai bisogno di un vettore enorme con frequenti inserzioni / cancellazioni su posizioni arbitrarie, anche se è una cosa di nicchia nella migliore delle ipotesi. Un vettore basato su un albero binario potrebbe avere anche qualche applicazione di nicchia.
Un esempio che ho usato i riepiloghi delle dimensioni degli alberi secondari non è in realtà una struttura dati in quanto dipende dai contenitori sottostanti. È usato dove l'informazione è strutturata logicamente come un albero. In un BST, i dati sono strutturati logicamente come una sequenza ordinata - l'utente finale non sa o cura che ciò sia implementato tramite strutture ad albero. Questa classe viene utilizzata quando le relazioni genitore / figlio sono rilevanti per l'applicazione.
Normalmente i dati sottostanti vengono tenuti in un modo simile a come si costruiscono strutture ad albero all'interno di un database relazionale - gli elementi hanno campi padre ecc. - sebbene la libreria sia disgiunta da essa essendo un modello basato su criteri C ++. Funziona attraverso un insieme di chiamate semplici come Get_Parent , Get_Next_Child e così via, che sono di solito banali da implementare.
Io chiamo la libreria uno "strumento XML", fondamentalmente perché supporta una vista dell'albero sottostante simile agli elementi XML. Puoi attraversare l'intero albero, ad esempio, e vedrai iniziare i "tag" e terminare i "tag" per ciascun nodo nell'ordine in cui ti aspetteresti di vedere i tag in un file XML che rappresenta quell'albero. Esistono altri ordini di attraversamento, come ad esempio "treeview" (preordine), e c'è il supporto per l'indice e il traversal semplice.
E c'è il supporto per i sommari in cui ogni oggetto ottiene una dimensione (che può essere zero, ma non negativa) e viene mantenuto un totale parziale. Ho usato questo ad es. per un controllo del tavolo da albero che, ovviamente, non ho mai finito. Quando un elemento viene compresso, il suo riepilogo delle dimensioni totali per i suoi discendenti viene forzato a zero (con modifiche propagate nell'albero) in modo che le ricerche basate sulla posizione all'interno di questa vista dell'albero non vedano quei discendenti. Ciò semplifica la ricerca e l'iterazione degli elementi attualmente visibili.
BTW - il controllo della tabella ad albero della GUI incompiuta non è mai stata l'applicazione più importante, è solo facile da visualizzare.
