Utilizzando un albero 2-3-4 invece di un albero splay

Question

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.

Answer 1

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).