Trova mediana in O (1) nell'albero binario

Question

Supponiamo di avere un BST bilanciato (albero di ricerca binario). Ogni nodo dell'albero contiene un campo speciale count, che conta tutti i discendenti di quel nodo + il nodo stesso. Chiamano questa struttura dati order statistics binary tree.

Questa struttura di dati supporta due operazioni di O (log):

• rank(x) - numero di elementi che sono meno di x
• findByRank(k) - trova il nodo con rank == k

Ora desidero aggiungere una nuova operazione median() per trovare la mediana. Posso supporre che questa operazione sia O (1) se l'albero è bilanciato?

Answer 1

Se l'albero è completo (cioè tutti i livelli completamente riempiti), sì è possibile.

Answer 2

A meno che l'albero non sia completo, la mediana potrebbe essere un nodo foglia. Quindi, in generale, il costo sarà O (logN). Immagino che ci sia una struttura dati con le proprietà richieste e con un'operazione findMedian di O (1) (Forse una lista di salto + un puntatore al nodo mediano, non sono sicuro di findByRank e operazioni di classificazione) ma una BST bilanciata non è uno di loro.

Answer 3

In un albero di statistiche di ordine bilanciato, trovare la mediana è O (log N). Se è importante trovare la mediana nel tempo O (1), è possibile aumentare la struttura dei dati mantenendo un puntatore alla mediana. Il problema, ovviamente, è che è necessario aggiornare questo puntatore durante ogni operazione di inserimento o cancellazione. L'aggiornamento del puntatore richiederebbe O (log N) tempo, ma poiché tali operazioni richiedono già tempo O (log N), il lavoro extra di aggiornamento del puntatore mediano non modifica il loro costo di big-O.

In pratica, ciò ha senso solo se si eseguono molte operazioni di "trova mediana" rispetto al numero di inserimenti/eliminazioni.

Se lo si desidera, è possibile ridurre il costo dell'aggiornamento del puntatore mediano durante Inserimento/Cancellazione a O (1) utilizzando un (doubly) threaded binary tree, ma Inserisci/Elimina sarebbe ancora O (log N).