Esiste un'implementazione di un albero di ricerca binario annotato con dimensioni secondarie

Question

Ho cercato la struttura dei dati dell'albero descritta a questo link (vicino al fondo):

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

Si dice che questa struttura dei dati potrebbe essere un albero delle dita. Tuttavia, dopo ulteriori ricerche sugli alberi delle dita, ho scoperto che questo manca delle "dita" che producono alberi di dito. Invece, sembra che questo sia solo un albero binario annotato (annotato con dimensioni della metropolitana).

Conosci un'implementazione esistente (in qualsiasi lingua) di questa struttura dati che potrei usare come riferimento per la mia implementazione (sebbene, preferibilmente non un'implementazione in un linguaggio di programmazione funzionale)?

Oppure, quale sarebbe il modo più ottimale per retrofit delle annotazioni delle dimensioni della metropolitana in una struttura dati esistente?

Grazie!

Answer 1

B-alberi contati di Simon Tatham sono simili. Se il conteggio dei nodi viene sostituito con una larghezza di buffer come in Tweak, questi forniscono operazioni come corde.

In effetti dalla lettura che la pagina a cui fai riferimento vedo che veniva usato come una tabella dei pezzi o una tabella di linea per un editor

nella carta, Alberi delta posizionali per conciliare gli aggiornamenti con l'archiviazione dei dati ottimizzata per le letture, gli autori presentano un albero che il comportamento nei confronti degli invarianti detiene tra i nodi nelle barre dell'albero una sorprendente somiglianza Le enfilades di Xanadu a cui anche l'ab-albero contabile è simile.

Answer 2

Ho un progetto su GitHub chiamato Boost. Alberi annotati integrati Ciò mira a fornire supporto generico per annotazioni come il conteggio dei substrati in Boost. Insudente. Il conteggio dei trainari era il mio caso d'uso originale per questo.

Attualmente richiede modelli variadici C ++ 11 e supporta solo RBTREE, ma funziona e spero di rimuovere entrambe queste restrizioni nel tempo Aggiornare: Ora si basa con C ++ 03. Supporta ancora solo RBTREE.

Se usato con una annotazione del conteggio della metropolitana, è simile a ciò che Jordan descrive nella risposta sopra - calcola (sinistra+a destra+1) su ciascun nodo. L'implementazione è abbastanza diversa: funziona con qualsiasi nodo e/o tratti di valore; Gli aggiornamenti delle annotazioni sono invece integrati negli algoritmi RBTREE, il che mantiene il numero di recaldulazioni fatte minime.

Answer 3

Ho implementato qualcosa di simile in base a una domanda che ho posto l'altro giorno. Ho aggiunto annotazioni ai nodi Boost :: intrusivi :: rbtree/avltree per calcolare la dimensione di ciascun sottostruttura (foreach nodo count = nodo-> sinistra-> conta + nodo-> destro-> conta + 1). Eseguo questo aggiornamento su inserzione/deletezione/ribilanciamento dell'albero utilizzando il gancio di value_traits boost per set_parent, set_left e set_right. Praticamente, come indicato nel sito a cui si fa riferimento, dopo ogni aggiornamento del nodo, aggiorna la dimensione del nodo corrente e quindi attraversa l'albero fino a quando non si preme la radice, aggiornando le dimensioni di ciascun nodo mentre vai.

Il problema arriva quando si desidera inserire nell'albero in una posizione specifica. Praticamente il momento in cui lo fai, invaliderai l'invariante di ordine chiave per la struttura degli alberi. Ciò significa che non sarai in grado di eseguire ricerche O (log n) efficienti per chiave. Ma, se lo volessi, probabilmente non saresti necessari comunque le annotazioni di dimensioni.