Ordinare una lista con un albero binario: come funziona Sortello

sortello ordinamento albero binario

Trello si presta bene per essere utilizzato come kanban board o, in generale, per ordinare l’elenco di cose da fare – per gli amici: ToDo list.
Mettere in ordine la lista ToDo può essere un’operazione lunga e macchinosa, durante la quale è facile perdere di vista l’insieme delle attività e le relazioni di priorità esistenti tra di loro.
La soluzione? Perdere volutamente di vista l’insieme delle card e confrontarne solo due per volta.

Sortello nasce per questo scopo: facilitare l’ordinamento delle card presenti in una colonna all’interno di una kanban board.

La matrice delle priorità

La matrice delle priorità si basa su un metodo molto semplice: si confrontano 2 a 2 tutti i task e si stila una classifica in base ai risultati ottenuti.

matrice priorità sortello albero binario

È facile notare che questo metodo non è molto efficiente, in quanto ci costringe ad eseguire (n^2 – n)/2 scelte, quindi con complessità O(n^2).
Una soluzione sicuramente più rapida o, nel peggiore dei casi, equivalente per rapidità alla matrice delle priorità, è l’ordinamento su albero binario, o (Binary-)Tree Sort.

Sortello si occupa di costruire un albero binario di ricerca, sottoponendo all’utente soltanto scelte 1 vs 1, nelle quali viene chiesto di indicare la card con priorità più alta.

 

Ordinamento di un albero binario (Binary-Tree Sort)

Questo metodo di ordinamento si basa sulla costruzione di un albero binario. In questo albero ogni nodo è posizionato in base ad una determinata relazione di importanza/precedenza/priorità rispetto ai nodi vicini.
Nel nostro caso, ogni nodo ha un priorità maggiore rispetto al sotto-albero di sinistra, e priorità minore rispetto al sotto-albero alla sua destra.

Se attraversato con strategia in-order, un albero di ordinamento binario restituisce la lista ordinata dei suoi elementi.

sortello inserimento nodo ordinare albero binario gif
Node insertion – Clicca sull’immagine per vedere la gif

 

Insertion cost

Il costo di inserimento di un nuovo elemento nell’albero – insertion cost – è mediamente O(log n), quindi inserire n elementi è un processo O(n log n).
Questo fa del binary-tree-sort (o più semplicemente tree-sort) un metodo veloce, che però degenera se l’albero è sbilanciato, fino al worst-case, O(n).

Ridurre l’insertion cost è possibile mantenendo l’albero bilanciato.
L’inserimento in un albero totalmente sbilanciato (rappresentato da un solo ramo) ha un costo pari a quello della matrice delle priorità, in quanto ogni nuovo elemento dovrà essere confrontato con tutti gli altri già presenti nell’albero.

È importante quindi prevedere un sistema di bilanciamento dell’albero che lo mantenga il più possibile simmetrico, riducendo il numero dei livelli di profondità e, quindi, il numero di passi per l’inserimento di un nuovo elemento.
Esistono metodi analitici per eseguire tale operazione, adatti per alberi di grandi dimensioni e in casi dove è richiesta una certa efficienza.

 

Bilanciamento dell’albero

In Sortello è stato implementato un bilanciamento “naive“, eseguito dopo l’inserimento di ogni nuovo elemento.
La semplicità dell’algoritmo è dovuta alla mancanza di necessità di prestazioni elevate: volendo ordinare una lista Trello è improbabile avere un albero con decine/centinaia di card, quindi non è richiesto un meccanismo efficiente in termini di prestazioni.

Il bilanciatore esegue i seguenti step, sull’albero costruito allo step n-esimo:

0. Attraversa l’albero, restituendo la lista ordinata delle n card fin qui inserite.

1. Estrae l’elemento centrale della lista (o uno dei due elementi centrali, nel caso di n pari), identificandolo come un nodo.

2. Gli elementi della lista precedenti al nodo estratto formeranno il sotto-albero sinistro, mentre quelli successivi il sotto-albero destro.

3. Su ciascuno dei sotto-alberi vengono ripetuti ricorsivamente i passi 1-3

ordinamento albero binario sortello gif
Tree balancing – Clicca sull’immagine per vedere la gif

 

Su un numero limitato di card, quelle che verosimilmente si possono avere in una lista Trello, questo processo è sufficientemente rapido da non generare interruzioni nel flusso di lavoro dell’utente, che vedrà la scelta successiva e proseguirà in maniera trasparente con l’ordinamento.

 

Test di benchmark

Per valutare l’utilità dell’algoritmo di bilanciamento, un test esegue l’ordinamento 100 volte, con e senza bilanciatore. Nel test viene calcolato il numero medio di passi per l’inserzione di tutti i nodi. Di seguito i risultati per un albero di 20 nodi: nel primo caso i nodi vengono mescolati prima di iniziare l’ordinamento; nel secondo la lista dei nodi da inserire è già ordinata e quindi, senza bilanciatore, genera un albero totalmente sbilanciato:

test benchmark albero binario sortello
test benchmark albero binario sortello

 

Abbiamo già parlato di Sortello in questo articolo, se non l’hai letto approfittane ora… niente paura, non ci sono formule matematiche ma un interessante studio della brand identity!