Spiegazione dell’algoritmo Reingold Tilford, con procedura dettagliata | di Kay Jan Wong | Settembre 2023 | Intelligenza-Artificiale

Algoritmo per tracciare i nodi dell’albero con esempi numerici e codice Python

L’algoritmo Reingold-Tilford del 1981 crea una rappresentazione visivamente gradevole dei dati gerarchici disponendo i nodi in una struttura ad albero per massimizzare la leggibilità. In altre parole, è un algoritmo per recuperare il file (x, y) coordinate di ogni nodo di un albero.

Secondo il cartaci sono alcune regole estetiche che un buon diagramma ad albero dovrebbe seguire,

1. I nodi alla stessa profondità dovrebbero trovarsi lungo una linea retta e le linee rette che definiscono le profondità dovrebbero essere parallele

2. Un figlio sinistro dovrebbe essere posizionato a sinistra del suo nodo genitore e un figlio destro a destra (applicabile solo agli alberi binari)

3. Un genitore dovrebbe concentrarsi sui propri figli

4. Un albero e la sua immagine speculare dovrebbero produrre disegni che si riflettono l’uno nell’altro, e un sottoalbero dovrebbe essere disegnato allo stesso modo indipendentemente da dove si trova nell’albero

Determinare il y le coordinate dei nodi sono semplici, mentre il x le coordinate sono leggermente più complicate. Questo articolo tenterà di spiegare l’algoritmo con esempi numerici su un albero leggermente più complesso rispetto agli altri documenti e articoli che ho letto, in modo da poter coprire più scenari. Introdurrò anche terminologie aggiuntive non utilizzate nel documento originale per distinguere meglio tra i diversi termini.

Un’intuizione importante riguardo all’algoritmo è che traccerà l’albero da una direzione da sinistra a destra. Puoi pensare che il nodo più a sinistra abbia una coordinata di (0, 0)e i vari sottoalberi si sposteranno di conseguenza verso destra.

Fatto divertente: scikit-learn Anche la libreria Python utilizza questo algoritmo per tracciare alberi decisionali!

Prima di determinare le coordinate finali di ogni nodo, 3 termini sono cruciali. Il documento originale fa riferimento ai termini x E modma nella mia spiegazione userò un ulteriore shift…