come posso restituire la mediana di un albero di ricerca binario filettato in tempo costante?

Question

come posso restituire la mediana di un albero di ricerca binario filettato in tempo costante?

#1 da (3 voti)
#2 da (2 voti)
#3 da (1 voti)

0

Ho difficoltà a capire come implementare e trovare la mediana di un albero di ricerca binario filettato in tempo costante.

L'albero è composto da id e nome del lavoratore.

I dettagli forniti sono dati:

In un albero di ricerca binario con n nodi, ci sono n + 1 puntatori sinistro e destro con il valore NIL. Per ogni nodo z nell'albero eseguiamo la seguente modifica: Se lasciato [z] = NIL allora lasciato [z] ottiene il valore del predecessore dell'albero (z); E se right [z] = NIL allora right [z] ottiene il valore di tree-successor (z).

In sostanza, da quello che capisco è un albero di ricerca binaria doppiamente filettato.

Non sono sicuro di come restituire la mediana in un tempo costante.

Quello che so è che se vogliamo restituire la mediana in O (n) in un normale albero di ricerca binaria, allora si ottiene usando Morris in-order traversal e poi facilmente calcolato se il numero di nodi è pari o dispari .

Tuttavia, come può essere calcolato in tempo costante?

Ho già fatto l'attraversamento con in ordine, post-ordine, pre-ordine usando un tempo lineare con il numero di elementi in esso.

Per favore aiutami, rimani fermo per un bel po '.

grazie mille

data-structures algorithms implementations

posta BeginningMath 25.07.2018 - 07:19

fonte

3 risposte

Leggi altre domande sui tag data-structures algorithms implementations

Va bene per Pattern Repository contenere nomi di metodi insoliti? Come posso mantenere sincronizzate le directory

score 3 · Answer 1

Se per "albero di ricerca binario filettato" si intende "albero binario bilanciato".

Facile. Restituisce la radice!

link

La caratteristica fondamentale di un albero binario bilanciato è che stai bilanciando i nodi a sinistra e a destra mentre modifichi l'albero, mantenendo la metà di essi a sinistra e metà a destra ;-) La mediana allora è sempre a la radice dell'albero Quindi domanda trabocchetto; -)

Se intendi qualcos'altro, probabilmente non lo troverai in tempo costante. Se devi vagare attraverso l'albero quasi a caccia in giro, sarà quasi necessario dipendere da quanto è grande l'albero, e quindi non essere costante.

score 2 · Answer 2

per semplicità, assumeremo che la mediana sia il valore al ceil (n / 2) dell'indice di inorder (1-indexed). all'inizio dell'albero aggiungi un puntatore al nodo mediano & conteggio del numero di nodi (n). Manutenzione: su ogni inserimento / cancellazione di un nodo tenere il vecchio n in una variabile temporanea, incrementare n per uno e quindi controllare se la mediana, (ceil (n / 2)), valore dell'indice è cambiato. se cresce di 1, imposta il mediano come successore se diventa più piccolo di 1, imposta il predecessore della mediana come mediana In questo modo puoi semplicemente riportare la mediana in tempo costante.

score 1 · Answer 3

Per un albero di ricerca binaria bilanciato in base alla dimensione dispari, il nodo radice rappresenta la mediana.

Per un albero di ricerca binaria bilanciato in base alla dimensione, l'approccio dipende dalla definizione della mediana. Nel caso in cui si calcoli semplicemente i due valori centrali, si otterrebbe la media del valore radice con il valore adiacente sul lato del sottostruttura più grande. In un albero collegato, trovare quel vicino è un'operazione a tempo costante.

La parte difficile qui è mantenere le dimensioni dell'albero bilanciate (bilanciate in base al peso). La maggior parte degli algoritmi di bilanciamento dell'albero bilancia invece l'altezza, il che non è interessante qui. Gli algoritmi di bilanciamento del peso in genere mantengono i pesi sinistro e destro all'interno di un fattore l'uno dell'altro, ma qui vogliamo che la differenza di peso sia zero o uno.

AFAIK questo è facile da fare dato inserimenti O (n) (ad esempio ricostruendo l'albero dopo ogni inserimento).