Universidad de Costa Rica
Escuela de ciencias de la computación y la informática
Curso de programación 2
CI – 1201
“implementación de la clase Arbol_Rojinegro “
Alumno:
Carlos Andrés González
Numero de carné:
A52512
Profesor:
Adolfo Dimare
Introducción
El objetivo de
esta tarea programada es que el estudiante Implemente
un programa para aplicar los conceptos de reutilización de software
implementando la clase Arbol_Rojinegro tomando en base la clase Bin_Tree.
La documentación de
esta tarea junto con los códigos fuente se pueden consultar en Internet en la siguiente página:
http://www.geocities.com/quetzalinn/Rojinegro.html
Y el archivo .zip con todos los archivos y una documentación mas
completa esta en:
http://www.geocities.com/quetzalinn/Rojinegro.zip
Descripción del problema
a resolver:
El estudiante debe
Implementar un programa que inserte y elimine elementos en un árbol rojinegro.
Planteo:
Para
resolver el problema es necesario recurrir a bibliotecas con el propósito de
conseguir la definición y propiedades de la clase árbol rojinegro.
Luego
se debe realizar una reutilización de software con la clase Bin_Tree y en base
a esta implementar la clase Arbol_Rojinegro.
Objetivos:
El objetivo de esta
tarea es implementar una clase en base a otra respetando el REP.
Requerimientos: Utilizar un compilador.
Resolución
del problema:
Para realizar el
programa se deberá heredar la clase Bin_Tree y de esta forma poder utilizar sus
métodos públicos. Además se debe añadir al REP de la clase Arbol_Rojinegro un
valor que almacene el color de las hojas. Luego se implementa la función de inserción
y eliminación de elementos de un árbol rojinegro respetando el REP de la clase
Bin_Tree.
Abstracción:
El
estudiante debe tomar una clase e implementar la inserción y eliminación de
elementos.
Especificación
de la clase:
La
clase Arbol_Rojinegro es una implementación de árboles balanceados lo cual
permite una muy rápida manipulación de los elementos de este contenedor.
Operaciones/Métodos:
Lista
de los miembros con enlaces a los documentos de cada archivo a los que
pertenecen:
·
Bin_Tree_h : Bin_Tree.h
·
borrado()
: Arbol_Rojinegro.h
·
busca_nodo()
: Arbol_Rojinegro.h
·
check_ok()
: lkptr.h
·
Comp() : Bin_Tree.h
·
COMPILER_lkptr
: lkptr.h
·
copyDeep() : Bin_Tree.h
·
corregirEliminar()
: Arbol_Rojinegro.h
·
corregirInsercion()
: Arbol_Rojinegro.h
·
depth()
: Bin_Tree.h
·
height() : Bin_Tree.h
·
height0()
: Bin_Tree.h
·
inserción()
: Arbol_Rojinegro.h
·
IPD_cout() : Bin_Tree.h
·
lkptr_h : lkptr.h
·
main()
: Arbol_Rojinegro.cpp
·
operator!=() : Bin_Tree.h, lkptr.h
·
operator==() : Bin_Tree.h, lkptr.h
·
orderedInsert() : Bin_Tree.h
·
Rojinegro_h
: Arbol_Rojinegro.h
·
rotarDer()
: Arbol_Rojinegro.h
·
rotarIzq()
: Arbol_Rojinegro.h
Especificación
del programa:
El programa solamente
crea un árbol rojinegro al cual se le pueden meter y quitar valores.
Implementación:
Modelo de la clase:
+=========+
|
lkptr.h |
+=========+
|
+==========+
|
Bin_Tree.h |
+==========+
|
+================+
| Arbol_Rojinegro.h |
+================+
|
+======+
| .obj |
+======+
|
+=========+ +======+
| C++.lib | =====>
|
linker
|
+=========+ +======+
|
+==================+
| C++.lib |
.obj | .obj
|
+==================+
|
+==================+
|
Arbol_Rojinegro.exe |
+==================+
Compilador usado:
Microsoft Visual
Studio 2005
Guía de uso del
programa:
Abrir el archivo Arbol_Rojinegro.vcproj
y compilarlo, posteriormente usar la opción RUN de la barra de herramientas.
Datos de prueba del
programa:
La implementación no incluye los
datos de prueba, solamente quedan los de la clase base.
Código fuente:
El código fuente y la
documentación Doxygen se encuentran en Internet (ver introducción).
Bibliografía:
Como programar en
C/C++, Deitel&Deitel