Búscalo aquí:

Arbol rojinegro [código]

Un árbol rojinegro es una de las estructuras de datos de tipo diccionario más usadas. Es un árbol binario balanceado que asegura que sus operaciones tengan una complejidad de O(log N) en el peor de los casos. En este post comparto el código fuente escrito en C++ del árbol rojinegro.


En un árbol rojinegro (ARN) se verifican las siguientes propiedades:

  1. Todo nodo es rojo o negro (representación lógica)
  2. La raíz es negra
  3. Todo nodo hoja (NULO) es negro
  4. Si un nodo es rojo, entonces sus dos hijos son negros
  5. Para cada nodo, todos los caminos desde ese nodo a sus hojas descendientes tienen el mismo número de nodos negros.
La implementación se realizó sobre la plataforma wxDEVC++ usando el compilador MingW de C++ haciendo uso de Programación Orientada a Objetos (POO) y de templates en C++ lo que permite hacer uso de diferentes tipos de objetos los cuales son almacenados en el árbol rojinegro para su posterior manipulación eficiente mediante las operaciones propias de dicha estructura de datos. El uso de punteros en esta estructura es indispensable para la implementación eficiente, es por eso que para entender el código se debería tener los conocimientos básicos del manejo de punteros en C++.

El código fue implementado junto con Dámaris Amaro y lo pueden DESCARGAR DESDE AQUI.




Quieres leer más post como éste???...suscribete aquí!!!

7 comentarios:

  1. no logro compilar el codigo ni en c++, si me puedes dar una ayuda t lo agradeceria mi correo es paisa00@hotmail.es gracias......

    ResponderEliminar
  2. Hola, todo codigo fuente en c++/Java/prolog o en cualquier otro lenguaje que aqui publico estan funcionando correctamente, es decir los errores que puedan surgir no se deben a error en programación, mayormente estos errores se deben a la mala configuración del entorno sobre los que se montan.

    En el caso de C++ esto es comun, si programas una funcion en DevC++ es muy probable que sobre Visual C++ no "corra" bien...esto debido principalmente al uso de un compilador diferente.

    Es por ese motivo que especifico en el post que la implementación se realizó sobre la plataforma wxDEVC++ usando el compilador MingW de C++...dale una revision a las caracteristicas de tu compilador y asegurate de que se este llamando correctamente al header (archivo .h)

    saludos

    ResponderEliminar
  3. y no tienes un codigo q realize lo mismo en java ??? es q me presenta dificultad para la ejecuccion d este codigo.... gracias

    ResponderEliminar
  4. Las estructuras de datos tienen por objetivo una major organizacion de los datos (valga la redundancia) y para ello se tienen que implementar metodos eficientes, ademas de una administracion eficiente de los accesos de lectura y escritura ya sea en memoria o en disco. El uso de lenguajes como C++ es ideal para este tipo de programas gracias a las caracteristicas de este lenguaje de programación, motivo por el cual muchos autores lo sugieren.

    Java por su naturaleza de uso de la maquina virtual, tiende a tomar un "poco más" de tiempo en su procesamiento, por lo que, a mi humilde opinión, no sería demasiado conveniente su uso para este tipo de programación, salvo se haga uso de técnicas que permitan "acelerar" el trabajo y por ende la optimizacion del código.

    Por este par de razones es que las estructuras de datos que programo generalmente las hago sobre C++ y no en Java (aunque no descarto el uso de este lenguaje para este tipo de programas).

    Saludos

    ResponderEliminar
  5. pero no logro entender el por q al compilar este codigo en wxDEVC++ con el compilador MingW, lo unico q me aparece es una ventana DOS la cual dice:

    se insertaran 100000 elementos
    Tiempo = 2.867
    7 no se encuentra
    ingrese una letra

    y despues d haber ingresado la letra lo unico q ocurre es q se cierra el DOS, lo estoy haciendo bn o q es lo q sucede ???

    gracias...

    ResponderEliminar
  6. El programa esta corriendo perfectamente!!! si te das cuenta en la funcion main() se coloca un test de insercion automatica de 100000 elementos en 2.867 segundos...luego se hace una busqueda en el arbol rojinegro del elemento 7...el cual segun el programa no se encuentra

    Finalmente aparece un mensaje de "ingrese una letra" lo cual sirve para salir de la ventana DOS...lo que significa que el código esta funcionando perfectamente, si necesitas hacer tus propias inserciones de elementos puedes hacerlo reemplazando la funcion de test.

    Analiza un poco el codigo para que lo entiendas un poco mejor y no creas que ciertos mensajes se tratan de errores, no es cuestion de ejecutar un programa, hay que revisarlo :D

    Saludos.

    ResponderEliminar
  7. por que no lo hicieron con una reprecentacion grafica con sus bolitas eso ustedes saben

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...