14 noviembre 2009

Red-Black Trees vs Binary Trees

He acabado de implementar la estructura red-black tree (árbol rojinegro o árbol rojo-negro). Es un árbol binario de búsqueda modificado para conseguir que siempre esté equilibrado y no ocurran los casos peores del árbol binario típico. Sólo hay que modificar la estructura del árbol para añadir un nuevo atributo a cada nodo: su color (rojo o negro). Además al insertar y borrar nodos hay que reorganizar el árbol efectuando rotaciones aprovechando los colores.

Artículo wikipedia
Artículo Mathworld

He hecho 3 tests sencillos:

  1. 30 vectores aleatorios de 10000 elementos insertados aleatoriamente

  2. 30 vectores aleatorios de 10000 elementos insertados ordenadamente

  3. 30 vectores aleatorios de 10000 elementos todos iguales



El tiempo total de los tests utilizando un árbol binario de búsqueda normal ha sido 17m40.500s. En cambio, el red-black tree que he implementado ha tardado 10.485s (sí, 10 segundos) en mi portátil.

Ejecutando sólo el test 1 que es más realista el red-black tree sigue ganando: tarda 4.040s frente a los 5.660s del árbol binario normal.