Get best of the week

Árboles rojo-negros en javascript

imagen

Hola habr Recientemente estudiado árboles rojo-negro. Traté de visualizar los detalles del funcionamiento de los algoritmos de inserción y eliminación en d3.js. Espero que el resultado ayude a ahorrar tiempo a quienes estudian algoritmos en javascript. Puedes verlo aquí . El código fuente de la implementación de la que me basé aquí . Debajo de los detalles cortos del gato.

Busque soluciones existentes


El objetivo principal de la idea era comprender la implementación del algoritmo y visualizarlo. El primer paso fue buscar una implementación con explicaciones completas y comprensibles y código js. En el proceso de búsqueda, se entristeció que los autores a veces no terminaran la fuente, por ejemplo, hay un algoritmo de inserción, pero no hay eliminación. O hacen una visualización como esta , pero no proporcionan enlaces a la fuente. Entonces encontré este excelente artículo. Pero incluso matar, todavía no puedo entender por qué el autor insertó el código con imágenes y no dio un enlace al código fuente a pedido en los comentarios. También hay un paquete npm red-black-tree , cuyo código fuente completo es: 'en progreso ...' en el archivo Léame. También encontré una implementación popular árboles rojo-negros en js, de los cuales dependen muchos paquetes y millones de descargas por semana, pero el código tiene cinco años.

Priorización y especificación de tareas


En los cerebros de Porakinin, decidí que la legibilidad y la comprensión del código con fines educativos es más importante, por lo que tomé como base el artículo que se mencionó al principio, y no el paquete npm. La implementación resultó ser más conveniente y visual en términos de lectura de código. En el artículo, el autor comienza con un árbol binario, luego lo extiende a rojo-negro. Para la visualización, parece bastante lógico heredar de un árbol rojo-negro y hacer un árbol animado. Por lo tanto, después de volver a escribir el código y asegurarme de que funciona, comencé a dibujar un árbol animado. D3.js. viene al rescate. Hay maravillosas transiciones que le permiten mover elementos a las posiciones correctas y transformarlos suavemente en estados adecuados, a medida que funciona el algoritmo.

El significado de los árboles rojo-negros


Pensé durante mucho tiempo, como de una manera simple, explicar qué es qué. Probablemente, de todos modos, necesita leer la teoría de diferentes fuentes. Como dice el dicho: "No arrojarás palabras de una canción". Pero se pueden formular conclusiones resumidas simples en pocas palabras. La conclusión es que hay varios casos al insertar y eliminar un elemento, dependiendo de qué "abuelo", "padres", "tíos", "niños", "hermanos" repinten y cambien (giren) hacia el lado donde hay menos elementos . Como resultado, nunca sucede que la ruta desde el nodo más lejano al nodo raíz sea demasiado larga, por lo que la búsqueda del elemento deseado en dicha estructura es muy rápida. Bueno, esto se compensa con la complejidad de la inserción y eliminación.

More articles:


All Articles