Come si fa a "bilanciare" un albero di ricerca ternario? La maggior parte delle implementazioni non risolve il problema, ma suggerisce di inserirlo in un ordine ottimale (che non riesco a controllare)Bilanciare un albero di ricerca ternario
L'articolo su Dr. Dobbs su Ternary Search Trees dice: D.D. Sleator e R.E. Tarjan descrive algoritmi di bilanciamento teorici per alberi di ricerca ternaria in "Alberi di ricerca binaria autoregolanti" (Journal of the ACM, July 1985). Puoi trovare le versioni online di questo articolo con il tuo motore di ricerca preferito.
Una generalizzazione dell'albero di ricerca binaria è la B-Tree, che funziona per i fanagli ovunque da 2 in su. Non è l'unico modo per farlo, ma è comune.
In modo approssimativo il modo in cui funziona è che se un inserto o una cancellazione mette l'albero fuori equilibrio, ruba un elemento o uno spazio da un nodo adiacente. Se anche questo non è sufficiente per mantenere l'albero in equilibrio, la sua altezza sarà modificata per fare spazio.
L'OP parla di ** alberi di ricerca ternari **. – hmuelner
Non sono del tutto chiaro su come un albero B 1-2 differisca da un albero ternario. Puoi spiegarmelo? – SingleNegationElimination
Un B-Tree (in genere) contiene le chiavi complete nei nodi. In un albero di ricerca ternario la chiave è definita dal percorso del nodo. – hmuelner
leggere questo articolo:
"autoregolante di ternario Cerca cerca Utilizzando condizionali Rotazioni e randomizzato euristica" da "Ghada Hany Badr * e B. Giovanni Oommen †"
Essa vi aiuterà per comprendere TST auto-regolanti e di bilanciamento.
Quanto è grande un albero di ricerca? –
Un paio di migliaia di parole che vanno da 4 a 20 caratteri. Non sono sicuro se questo è grande o piccolo, ma è grande per me. – uroc
Sembra che buttare via l'albero quando arriva a un certo punto e sostituirlo con un albero costruito con "l'ordine ottimale" è la soluzione migliore - dovrebbe richiedere millisecondi, se è possibile risparmiare tempo. –