inserimento albero splay
https://stackoverflow.com/questions/2008630
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
passando attraverso alcuni esercizi per affinare le mie abilità di alberi binari, ho deciso di implementare un albero strombatura, come indicato nel Wikipedia:. Splay albero
Una cosa che non ricevo è la parte che riguarda l'inserimento.
Si dice:
In primo luogo, cerchiamo x nell'albero splay. Se x non esiste, allora non trovarlo, ma il suo nodo padre y. In secondo luogo, si esegue un'operazione strombatura su y che si muoverà y alla radice dell'albero splay. Terzo, si inserirà il nuovo nodo x come radice in modo appropriato. In questo modo sia y viene lasciato o figlio destro della nuova radice x.
La mia domanda è questa: Il testo di cui sopra sembra eccessivamente concisa rispetto agli altri esempi in questo articolo, perché? Sembra che ci sono alcuni trucchi lasciato fuori qui. Ad esempio, dopo strombatura il nodo y fino alla radice, non posso sostituire appena ciecamente radicolare con x, y e l'aderenza su x sia come figlio sinistro o destro.
Supponiamo il valore non esiste già nella struttura.
Ho questo albero:
10
/ \
5 15
/ \ \
1 6 20
e voglio inserire 8. Con la descrizione di cui sopra, lo farò fino a trovare il 6 nodi, e in un normale albero binario, 8 sarebbe aggiunto come un bambino destra del 6 nodi, ma qui devo prima al splay il 6 nodi fino a radice:
6
/ \
5 10
/ \
1 15
\
20
allora uno di questi due sono palesemente sbagliato:
8 8
\ /
6 6
/ \ / \
5 10 5 10
/ \ / \
1 15 1 15
\ \
20 20
6 is not greater than 8 10 is not less than 8
mi sembra che l'unico modo per fare la divaricazione prima, e poi aggiungendo correttamente il nuovo valore come root significherebbe devo controllare i seguenti criteri (per aggiungere il nodo strombato come il bambino a sinistra della nuova radice) :
- il nodo I strombato alla radice è inferiore alla nuova radice (6 <8)
- il bambino più a destra del nodo I strombato alla radice è anche inferiore alla nuova radice (20 8)
Tuttavia, se dovessi dividere il nodo I strombato, prendendo il figlio destro e aggiungendo come il figlio destro del nuovo nodo, io ottengo questo:
8
/ \
6 10
/ \
5 15
/ \
1 20
Ma, è questo semplice alterazione andando sempre di darmi un albero corretta? Sto avendo un momento difficile venire con un esempio, ma potrebbe questo cavo al seguente:
- Il nuovo valore che voglio aggiungere è superiore alla root temporanea (il nodo I strombato alla radice), ma anche superiore al bambino più a sinistra del tasto destro del figlio della root temporanea?
Ie. un albero che avrebbe sostanzialmente simile a questa, dopo divaricazione, ma prima si sostituisce la radice?
10
/ \
5 15
/ \
11 20
e voglio aggiungere 13, che renderebbe il nuovo albero in questo modo:
13
/ \
10 15
/ / \
5 11 20 <-- 11, on the wrong side of 13
o può mai accadere questo?
La mia seconda domanda è questa: Non sarebbe molto più facile di riscrivere solo l'operazione nel seguente modo:
In primo luogo, cerchiamo x nell'albero splay. Se x non esiste, allora non trovarlo, ma il suo nodo padre y. Poi aggiungiamo il nuovo nodo sia come figlio sinistro o destro del nodo genitore. In terzo luogo, abbiamo eseguire un'operazione strombatura sul nodo abbiamo aggiunto che si muoverà il nuovo valore alla radice dell'albero splay.
sottolineatura mia per mostrare quello che ho cambiato.
Soluzione
Non vedo come il problema che descrivi potrebbe accadere. Se si desidera inserire 13 in questo albero è necessario prima di trovare in cui sarebbe:
10
/ \
5 15
/ \
11 20
Da 10 si va a destra, da 15 si va a sinistra, da 11 si va a destra ... e poi non hai più elementi. Se 13 erano stati nella struttura, avremmo trovato come un figlio destro di 11. Quindi, secondo la regola che eseguire un'operazione strombatura su 11 che si muoverà 11 alla radice dell'albero splay:
11
/ \
10 15
/ \
5 20
Poi aggiungiamo 13 come la nuova radice, con 11 come il figlio sinistro:
13
/ \
11 15
/ \
10 20
/
5
Ora non c'è nessun problema.
In primo luogo, cerchiamo x nell'albero splay. Se x non esiste, allora non trovarlo, ma il suo nodo padre y. Poi si aggiunge il nuovo nodo sia come figlio sinistro o destro del nodo genitore. In terzo luogo, si esegue un'operazione strombatura sul nodo abbiamo aggiunto che spostare il nuovo valore alla radice dell'albero splay.
Questo suona per me come avrebbe funzionato troppo, ma se fossi in te, mi piacerebbe solo cercare di implementare la versione come descritto in Wikipedia dato un sacco di persone che hanno testato ed è già ben documentato.
Altri suggerimenti
"Splay Tree" ha fatto subito mi ricordo un articolo in CUJ ho letto qualche tempo fa, si potrebbe trovare qualche informazione c'è: Implementazione Splay Albero in C ++ .
Terzo, inserire il nuovo nodo x come radice in modo appropriato. In questo modo sia y viene lasciato o figlio destro della nuova radice x.
Sì, ma questa nuova radice x deve avere 2 figli, è per questo che questa frase potrebbe sembrare confuso.
il nuovo nodo sarebbe aggiunto alla struttura proprio come un normale albero binario di ricerca. Quindi il nuovo nodo sarebbe strombato per essere il principale o il primo livello dalla radice. Inoltre, quando inseriamo un nuovo nodo, abbiamo bisogno di trovare la posizione di metterlo, in modo da fare un ritrovamento. E tutte le operazioni tra cui ritrovamento su un albero splay innescare un'operazione strombatura. Può essere ecco perché l'articolo di Wikipedia lo descrive così. Ho appena inserisco il nuovo nodo e splay in su. In entrambi i casi l'albero diventa più equilibrato di quanto non fosse. funziona qui
