Utilizzando un albero 2-3-4 invece di un albero splay
-
10-10-2019 - |
Domanda
Sono in corso le strutture di dati in questo momento e abbiamo imparato a conoscere 2-3-4 alberi e albero splay. Mi chiedevo in quali circostanze si usa un albero 2-3-4 invece di un albero splay? Sono entrambi di auto bilanciamento e ordinati in modo da non vedo che molta differenza tra di loro.
Soluzione
albero 2-3-4 cambia solo la struttura sugli inserti e eliminazioni, mentre un splay-albero anche ri-organizza i nodi sulle ricerche.
albero splay sarà, grazie alla riorganizzazione sulla ricerca, fornire più velocemente le risposte se il modello tipico utilizzo succede a cercare un piccolo sottoinsieme di elementi la maggior parte del tempo.
E 'possibile implementare un albero 2-3-4 in modo tale che il più piccolo elemento può essere guardato in O (1), ma in generale sia l'inserimento offerta e la cancellazione a O ammortizzato (log n).