He implementado un árbol de búsqueda binario y quiero agregar más funcionalidad en su función de inserción para que sea un árbol de auto-equilibrio. Estoy codificando en C#.Implementando un árbol de búsqueda binaria equilibrado?
¿Alguien me puede sugerir buenos tutoriales o enlaces sobre esto? Hice algunas búsquedas y encontré algunos enlaces, pero ninguno de ellos era lo suficientemente descriptivo.
Gracias.
Existen muchos algoritmos para árboles de búsqueda de autoequilibrado, muchos de los cuales son complejos y otros bastante simples (aunque con algunas advertencias).
El libro "Introducción a los algoritmos, segunda edición" de Cormen, Leisserson, Rivest y Stein es una excelente introducción a los algoritmos y cubre muy bien red/black trees. También es un gran libro en general sobre algoritmos y estructuras de datos.
Si está interesado en usar splay trees, que son extremadamente rápidos y realmente bastante fáciles de implementar, el original paper on the data structure es muy accesible. Además de eso, incluye una prueba de todos los límites de tiempo de ejecución.
El treap es un simple árbol binario de búsqueda equilibrado aleatorio que puede ser implementado con bastante facilidad una vez que sabes cómo implementar tree rotations. Las rotaciones de árboles también se usan en árboles de cobertura, por lo que podría valer la pena investigar.
Para AVL trees, this lecture parece ser un buen recurso.
Espero que esto ayude!
echa un vistazo a http://code.google.com/p/self-balancing-avl-tree/, implementa un árbol avl de auto-equilibrio en C#. Además, también implementa operaciones de concatenación y división.
¿Qué tipo de datos está almacenando en el árbol y por qué? –
Sugeriría buscar un árbol negro rojo. –
Buscaría árboles AVL. AFAIK son más fáciles de implementar que los árboles rojo-negro. – CodesInChaos