• Author / Uploaded
• Americo RT

Citation preview

Universidad Nacional Mayor de San Marcos Facultad de Ingeniería de Sistemas e Informática

Proyecto final – Estructura de Datos

Registro de entrada del hospital FISI-SALUD ALUMNOS: 

DOCENTE: PRO CONCEPCION LUZMILA Lima - Perú 5-11-2018

2019

1

INDICE I.-INTRODUCCION………………………………………………………………….3 II.-PROBLEMÁTICA………………………………………………..………………4 III.- JUSTIFICACION DEL ESTUDIO O PROYECTO…………………….. 5 IV.-MARCO TEORICO……………………………………………………………..6 V.-ALCANCE DE EL PROYECTO.……………………………………………….8 VI.-APORTE TEORICO…………………………………………………………….16 VII.-APORTE PRACTICO………………………………………………………….28 VIII.-EVALUACION………………………………………………………………...31 IX.-CONCLUSIONES………………………………………………………………..32

5-11-2018

X.-BIBLIOGRAFIA……………………………………………………………………33

2

INTRODUCCION Esta solución facilita el registro electrónico de la documentación que entra y sale de la entidad, así como la gestión de la documentación registrada. Gestionar información se refiere a un ciclo de actividad organizacional, la adquisición de información de una o más fuentes, la custodia y la distribución de esa información a aquellos que la necesitan, y su disposición final a través del archivado o borrado El propósito principal de la gestión de información es tener los registros en una tabla con un orden secuencial, tal que represente un orden, el cual puede ser numérico, alfabético o alfanumérico, ascendente o descendente otro propósito que se tendría vendría a ser la facilidad de las búsquedas de los registros del conjunto ordenado.

5-11-2018

Es importante destacar las operaciones que se pueden realizar gracias a una buena gestión de información como la eliminación de registros, el editar, el ingreso de más registros y como se mencionó antes la búsqueda de registros, esto se logra aplicando lo aprendido en clase ya que al tener un mejor registro los tiempos de esperan disminuyen poco o drásticamente al hacer cualquier consulta, ya sea utilizando el método que utilizemos.

3

PROBLEMA El hospital FISI-SALUD, dedicada al rubro del servicio de salud no presenta un algoritmo capaz de poder gestionar la información que ellos tienen en la entrada de su establecimiento, aun manejan los datos de forma manual para tener un respaldo, si bien esto es importante, se debería de aplicar la tecnología para poder rebajar sus costos en cuanto a tiempo y productividad además que no haya peligro de perdida de información. Esto se produce debido a que el hospital no confía en programas, por la seguridad y el costo que le causaría, pero analizando bien, el costo de impresión y la utilización de papel tiene un valor económico mucho más alto, lo cual no beneficia a la empresa y disminuye su productividad. Debido a que la tecnología abarca gran parte de las soluciones en el mundo, en la presente investigación se planteara e implementará un programa, que seguirá una determinada metodología, que permita gestionar la información a través de la utilización archivos, siendo su función principal leer el contenido de documento un Excel, para después hacer las comparaciones de búsqueda secuencial y búsqueda directa (a través de los distintos arboles), para determinar cuál es la más eficiente y así sea aplicado posteriormente.

5-11-2018

Para esto usaremos el lenguaje de programación C++, la programación será modular para poder llevar un mejor orden, además de la fácil detección de posibles errores en el código, así como para proporcionar facilidad en el mantenimiento de este código.

4

JUSTIFICACIÓN DEL ESTUDIO O PROYECTO

Aquí se muestran los objetivos y justificación por el que se realizara el trabajo:  El ineficiente sistema de registro de entrada en el hospital nos abre una problemática que debe ser resuelta lo más antes posible  Crear algoritmos (en el lenguaje C++) que puedan gestionar registros de entrada del hospital FISISALUD.  Determinar

cuál

de

los

distintos

arboles

implementados busca de manera más rápida el índice del código, con ese mismo índice se hará una búsqueda directa en el archivo.  Se implementará una tabla estadística de los tiempos en que se demoran cada operación realizada en el programa.

5-11-2018

 Brindar una rápida y eficaz respuesta al problema.

5

6

5-11-2018

MARCO TEÓRICO “Un archivo es un conjunto de datos estructurados en una colección de entidades elementales o básicas denominadas registros que son de igual tipo y constan a su vez de diferentes entidades de nivel más bajos denominadas campos.” (Manejo de Archivos en C, Lic. Virginia Valero). Existen 2 tipos de archivos: Archivo de texto: sólo están permitidos ciertos rangos de valores para cada byte. Algunos bytes tienen un significado especial, por ejemplo, el valor hexadecimal 0x1A marca el fin de fichero. Si abrimos un archivo en modo texto, no será posible leer más allá de un byte con ese valor, aunque el fichero sea más largo. Archivo binario: están permitidos todos los valores para cada byte. En estos archivos el final del fichero se detecta de otro modo, dependiendo del soporte y del sistema operativo. La mayoría de las veces se hace guardando la longitud del fichero. Cuando queramos almacenar valores enteros, o en coma flotante, o imágenes, etc, deberemos usar este tipo de archivos.

Existen diferentes formas de poder crear y acceder a un archivo en el lenguaje C, entre una de las formas está la

5-11-2018

La diferencia radica en cómo el programa va a tratar con el archivo Una vez sé que se cree un archivo y la información escrita en él se ha hecho como texto o como binario, en las siguientes operaciones, habrá que tratar el archivo siempre del mismo modo, en otras palabras, no se podrá cambiar la forma de leer o escribir el archivo.

7

biblioteca , la cual contiene los elementos necesarios para procesar el fichero, otra forma sería con la biblioteca , la cual contiene funciones para la edición de archivos, adicionalmente también se da la declaración de un tipo de variable llamado FILE, esta última forma será con la cual vamos a trabajar. x

5-11-2018

La importancia del uso de archivos en programas es esencial, ya que la información será guardada en una memoria secundaria, lo cual permite ingresar, buscar, eliminar o modificar la información contenida en el archivo.

8

ALCANZES DEL PROYECTO Lo que se realizara en este proyecto es sobre los diferentes tipos de árboles y métodos de búsqueda que se plantearan en este proyecto ARBOLES:

Un árbol es una colección de elementos, llamados nodos, uno de los cuales se distingue con el nombre de raíz. Los nodos mantienen entre ellos una relación que define una estructura jerárquica (de “paternidad”) entre ellos. Este nodo raíz es el padre de las raíces de los árboles que componen la lista, a partir del cual, se establece la relación de paternidad entre ellos. El conjunto vacío de nodos es un árbol, llamado nulo o vacío. Si n es un nodo y A 1 , A 2 , . . . , A k son árboles con raíces n 1 ,n 2 , . . . , n k , respectivamente, se puede construir un nuevo árbol haciendo n el padre de los nodos n 1 , n 2 , . . . , n k . En este árbol n es la raíz y T 1 , T 2 , . . . , T k son los subárboles de la raíz. Los nodos n 1 , n 2 , . . . , n k se conocen como los hijos del nodo n. ARBOL ABB:

Es aquel en el cual la distribución de las ramas sigue cierto orden. Los árboles ordenados de grado 2 son de especial interés puesto que representan una de las estructuras de datos más importante en computación, conocida como árboles binarios.

Los árboles AVL están siempre equilibrados de tal modo que, para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor

5-11-2018

ARBOL AVL:

9

de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles. Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos. ARBOL B:

La idea tras los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Pero, por otro lado, pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites (uno superior y otro inferior) en el número de nodos hijo son definidos para cada implementación en particular.

Ahora nos centraremos en algunos de los problemas más comunes que surgen en la computación, los de búsqueda y ordenamiento. En esta sección estudiaremos la búsqueda. La búsqueda es el proceso algorítmico de encontrar un ítem particular en una colección de ítems. Una búsqueda normalmente devuelve True o False según el ítem esté o no presente, respectivamente. En ocasiones, el algoritmo se puede modificar para devolver la posición donde se encuentre el ítem. Para nuestros propósitos, este nos interesa ya que al crear un archivo índice y buscar el dato nos interesa este nos devuelva con la búsqueda el índice requerido.

5-11-2018

Búsqueda

10

A pesar de que esto es fácil de escribir, un proceso subyacente debe llevarse a cabo para responder a la pregunta. Resulta que hay muchas maneras diferentes de buscar el ítem. Lo que nos interesa aquí es cómo funcionan estos algoritmos y compararlos entre sí. Búsqueda secuencial

Cuando los ítems de datos se almacenan en una colección, por ejemplo, en una lista, decimos que tienen una relación lineal o secuencial. Cada ítem de datos se almacena en una posición relativa a los demás. Estas posiciones relativas son los valores de los índices de los ítems individuales. Dado que estos valores de los índices están ordenados, es posible para nosotros visitarlos en secuencia. Este proceso da lugar a nuestra primera técnica de búsqueda, la búsqueda secuencial. La Figura 1 muestra cómo funciona esta búsqueda. Comenzando en el primer ítem de la lista, simplemente nos trasladamos de un ítem a otro, siguiendo el orden secuencial subyacente hasta que encontremos lo que buscamos o nos quedemos sin ítems. Si nos quedamos sin ítems, hemos descubierto que el ítem que estábamos buscando no estaba presente.

Figura 1: Búsqueda secuencial en una lista de enteros

Para analizar los algoritmos de búsqueda, tenemos que tomar una decisión sobre una unidad básica de cálculo.. Cada comparación puede o no descubrir el ítem que estamos buscando. Además, aquí hacemos otra suposición. La lista de ítems no está ordenada de ninguna manera. Los ítems se han colocado al azar en la lista. En otras palabras, la probabilidad de que el ítem que estamos buscando esté en una posición determinada es exactamente la misma para cada posición de la lista.

5-11-2018

Análisis de la búsqueda secuencial

11

Si el ítem no está en la lista, la única manera de saberlo es compararlo con cada ítem presente. Si hay n ítems, entonces la búsqueda secuencial requiere n comparaciones para descubrir que el ítem no está allí. En el caso de que el ítem sí esté en la lista, el análisis no es tan sencillo. En realidad, hay tres escenarios diferentes que pueden ocurrir. En el mejor de los casos encontraremos el ítem en el primer lugar que miramos, al principio de la lista. Sólo necesitaremos una comparación. En el peor de los casos, no descubriremos el ítem hasta la última comparación, la n-ésima comparación. ¿Cómo sería el caso promedio? En promedio, encontraremos el ítem alrededor de la mitad de la lista; es decir, compararemos contra n/2 ítems. Recordemos, sin embargo, que a medida que n se hace grande, los coeficientes, sean cuales sean, se vuelven insignificantes en nuestra aproximación, por lo que la complejidad de la búsqueda secuencial es O(n). La Tabla 1 resume estos resultados. Caso

Mejor caso

Peor caso

Caso promedio

El ítem está presente

11

nn

n/2

El ítem no está presente

nn

nn

nn

Suponga que la lista de ítems se construyó de modo que los ítems estuvieran en orden ascendente, de menor a mayor. Si el ítem que estamos buscando está presente en la lista, la posibilidad de que esté en alguna de las n posiciones sigue siendo la misma que antes. Aún tendremos que hacer el mismo número de comparaciones para encontrar el ítem. Sin embargo, si el ítem no está presente hay una ligera ventaja.

5-11-2018

Supusimos anteriormente que los ítems en nuestra colección habían sido colocados aleatoriamente de modo que no hubiera orden relativo entre ellos. ¿Qué pasaría con la búsqueda secuencial si los ítems estuvieran ordenados de alguna manera? ¿Seríamos capaces de mejorar en algo la eficiencia en nuestra técnica de búsqueda?

12

La Figura muestra este proceso a medida que el algoritmo busca el ítem 50. Observe que los ítems aún se comparan en secuencia hasta el 54. No obstante, en este punto, sabemos algo más. No sólo el 54 no es el ítem que estamos buscando, sino que ningún otro ítem más allá de 54 servirá ya que la lista está ordenada. En este caso, el algoritmo no tiene que seguir mirando a lo largo de todos los ítems para reportar que no se encontró el elemento. Puede detenerse inmediatamente.

Figura 2: Búsqueda secuencial en una lista ordenada de enteros

La Tabla 2 resume estos resultados. Note que en el mejor de los casos podríamos descubrir que el ítem no está en la lista mirando únicamente un ítem. En promedio, lo sabremos solamente después de mirar n2n2ítems. Sin embargo, esta técnica sigue siendo O(n)O(n). En resumen, una búsqueda secuencial se mejora ordenando la lista sólo en caso que no encontremos el ítem.

El ítem está presente

11

n

n/2

El ítem no está presente

11

n

n/2

Es posible aprovechar mejor la lista ordenada si somos inteligentes en nuestras comparaciones. En la búsqueda secuencial, cuando comparamos contra el primer ítem, hay a lo sumo n−1n−1 ítems restantes para verificar si el primer ítem no es el valor que estamos buscando. En lugar de buscar secuencialmente en la lista, una búsqueda binaria comenzará examinando el ítem central. Si ese ítem es el que estamos buscando, hemos terminado. Si no es el ítem correcto, podemos utilizar la naturaleza ordenada de la lista para eliminar la mitad de los ítems restantes. Si el ítem que

5-11-2018

Búsqueda binaria

13

buscamos es mayor que el ítem central, sabemos que toda la mitad inferior de la lista, así como el ítem central, se pueden ignorar de la consideración posterior. El ítem, si es que está en la lista, debe estar en la mitad superior. Podemos entonces repetir el proceso con la mitad superior. Comenzar en el ítem central y compararlo con el valor que estamos buscando. Una vez más, o lo encontramos o dividimos la lista por la mitad, eliminando por tanto otra gran parte de nuestro espacio de búsqueda posible. La Figura 3 muestra cómo este algoritmo puede encontrar rápidamente el valor 54. La función completa se muestra en el CodeLens 3.

Figura 3: Búsqueda binaria en una lista ordenada de enteros

Antes de pasar al análisis, debemos observar que este algoritmo es un gran ejemplo de una estrategia de dividir y conquistar. Dividir y conquistar significa que dividimos el problema en partes más pequeñas, resolvemos dichas partes más pequeñas de alguna manera y luego reensamblamos todo el problema para obtener el resultado. Cuando realizamos una búsqueda binaria en una lista, primero verificamos el ítem central. Si el ítem que estamos buscando es menor que el ítem central, podemos simplemente realizar una búsqueda binaria en la mitad izquierda de la lista original. Del mismo modo, si el ítem es mayor, podemos realizar una búsqueda binaria en la mitad derecha. De cualquier manera, ésta es una llamada recursiva a la función de búsqueda binaria pasándole una lista más pequeña.

Para analizar el algoritmo de búsqueda binaria, necesitamos recordar que cada comparación elimina aproximadamente la mitad de los ítems restantes de la consideración. ¿Cuál es el número máximo de comparaciones que este algoritmo

5-11-2018

Análisis de la búsqueda binaria

14

requerirá para examinar la lista completa? Si empezamos con n ítems, alrededor de n2n2 ítems se dejarán después de la primera comparación. Después de la segunda comparación, habrá aproximadamente n4n4. Después n8n8, n16n16, y así sucesivamente. ¿Cuántas veces podemos dividir la lista? La Tabla 3 nos ayuda a ver la respuesta. Comparaciones

Número aproximado de ítems restantes

1

n/2

2

n/4

3

n/8

... i

n/2i

A pesar de que una búsqueda binaria es generalmente mejor que una búsqueda secuencial, es importante tener en cuenta que para valores pequeños de n, el costo adicional del ordenamiento probablemente no vale la pena. De hecho, siempre debemos considerar si es rentable asumir el trabajo extra del ordenamiento para obtener beneficios en la búsqueda. Si podemos ordenar una sola vez y luego buscar muchas veces, el costo del ordenamiento no es tan significativo. Sin embargo, para listas grandes, incluso ordenar una vez puede resultar tan costoso que simplemente realizar

5-11-2018

Cuando dividimos la lista suficientes veces, terminamos con una lista que tiene un único ítem. Ya sea aquél ítem único el valor que estamos buscando o no lo sea. En todo caso, habremos terminado. El número de comparaciones necesarias para llegar a este punto es i donde n/2i=1. La solución para i nos da i=log n. El número máximo de comparaciones es logarítmico con respecto al número de ítems de la lista. Por lo tanto, la búsqueda binaria es O(logn). Es necesario enfrentar una cuestión de análisis adicional.

15

una búsqueda secuencial desde el principio podría ser la mejor opción.

APORTE TEÓRICO METODOLOGÍA 1. Registrar la información que se obtiene y se procede a escribirlo en una hoja de Excel, posteriormente se guarda el libro, pero con la extensión csv. 2. Corroborar que todos los datos que se escribe en el Excel estén completos además deben mantener sus campos iniciales. EJEMPLO: Si nuestro Excel tiene los campos NOMBRE y APELLIDOS, no puedo introducir un campo EDAD. 3. Se debe de reconocer que tipo de variable será cada campo del libro del Excel, ya que será útil para la implementación del código, específicamente en la declaración de variables. 4. Se debe de implementar las funciones que tendrá el código a realizarse.     

Se deberá de implementar distintos árboles, con sus respectivas búsquedas, ya que esto permitirá realizar una

5-11-2018

Insertar: añadir un registro al archivo Excel. Eliminar: quitar un registro del archivo según el código. Buscar: Recorrer de manera secuencial el archivo. Editar: modificar un registro mediante su código. Leer: Crea un archivo.dat, para la búsqueda física de un registro mediante su índice.  BuscaFisica: Realiza una búsqueda directa mediante el índice obtenido del árbol.  ArchivoIndice: Crea un csv solo con los índices y códigos de cada registro del Excel.

16

búsqueda directa del código y así se podrá hacer las comparaciones en base al tiempo entre búsqueda secuencial vs búsqueda directa. En esta investigación y tome 3 tipos de árboles: Árbol ABB, Árbol AVL y Árbol B. 5. Diseñar, especificar e implementar: se procederá a especificar cada función del programa, posteriormente se implementará, ya sea en el lenguaje C++ y Java.

Función LeerArchivo Diseño: El archivo Excel llega a la función y esta crea un archivo G que genera Datos.dat

CENTER.csv

Datos.dat

G = {e1, e2, …, en} Especificación: ACCION LeerArchivo(FILE F, entero acum) //El archivo F lee el Excel y se hace una copia y se guarda en el archivo G //El acum captura la ultima referencia del ultimo registro leído del archivo F PRE: CENTER.csv //ARCHIVO EXCEL POS: G =< > V G = < e1, e2,…..en>

5-11-2018

Implementación:

17

Función Mostrar Diseño: Se abre el archivo Datos.dat y se comienza a imprimir cada registro en la pantalla. G= e1, e2, …, en CENTER.csv

Se muestra los datos del archivo

Especificación: ACCION Mostrar(FILE G) //Se abre el archivo G y comienza la impresión de su contenido. PRE: G =< > V G =< e1, e2 ...,.en> POS: Archivo vacío V G= e1, e2,…..en

5-11-2018

Implementación:

18

Función Buscar Diseño: Se abre archivo Datos.dat y se comienza a recorrer hasta que coincida con el código a buscar, posteriormente se muestra todo el registro del código encontrado

Datos.csv

G= ex

Especificación: ACCION Buscar(FILE G, entero codigo) //Abre el archivo para buscar un registro de tipo INMUEBLE mediante su código PRE: G= < > V G = ∧ dato ∈ G

5-11-2018

Donde ex es el registro encontrado

19

POS: dato no existe

V

dato ∈ fs / ei = dato

Implementación:

Función Editar Diseño: Se abre archivo y se comienza a a recorrer hasta que se encuentre con el código ingresado, posteriormente se produce el cambio de los datos del registro G =< e1, e2., ex, ..,.en> Datos.csv

Donde ex fue encontrado y editado

Especificación: ACCION Editar (FILE G, entero código) //Se abre el archivo para buscar y editar un registro PRE: G = < > V G = ∧

dato ∈ G

5-11-2018

G =< e1, e2 ...,.en>

20

POS: dato no existe -> editado

V

dato ∈ G / ei = dato y G = e’i

Implementación:

Función Eliminar Diseño: Se abre archivo Datos.dat y se comienza a copiar todos los registros excepto el registro con el código ingresado, finalmente, se elimina el archivo antiguo y se renombra con el mismo nombre al archivo nuevo.

G =< e1, e2 …,ex,.,.en>

Especificación: ACCION Eliminar (FILE G, entero código)

G =< e1, e2 ...,.en> Se puede ver que ex ya no se encuentra en el archivo

5-11-2018

Datos.csv

21

//Abre un archivo para buscar y eliminar un registro de tipo inmueble mediante su código PRE:

G=

V G =

POS: dato no existe V codigo ∈ G / ei = codigo y G =

Implementación:

Función Ingresar Diseño: Se abre archivo Datos.dat y se ingresa un nuevo registro.

Datos.csv

G =< e1, e2 …,ex,.,.en> Donde ex es el nuevo registro ingresado

Especificación: ACCION Ingresar(FILE F, entero p) //Se abre el archivo F y se añade el registro n

5-11-2018

G =< e1, e2 .,.en>

22

// p es la última referencia del registro PRE: G = V G = POS: G = V G = //tal que n es el nuevo registro

5-11-2018

Implementación:

23

Función archivoIndice Diseño: se crea una copia del archivo Excel a otro archivo auxiliar conteniendo este solo la referencia y el código.

CENTER.csv

Auxiliar.csv

AUX = {e1, e2, …, en} Especificación: ACCION archivoIndice(FILE G, INMUEBLE A) //El archivo G lee el Excel y se hace una copia y se guarda en el archivo AUX PRE: INMUEBLES.csv //ARCHIVO EXCEL POS: AUX=< > V AUX = < e1, e2,…..en>

5-11-2018

Implementación:

24

TDA ARBOL BINARIO CREAR: crea un árbol vacío. Postcondición : árbol creado y vacío.

DESTRUIR: libera los recursos que mantienen el árbol. Precondición: el árbol debe haber sido creado.

PADRE (de un nodo determinado): devuelve el padre del nodo recibido. En caso de no existir el padre, devuelve NODO_NULO. Precondición: el nodo recibido no es NODO_NULO. Postcondición: ninguna

HIJO_IZQUIERDO (de un nodo determinado): devuelve el hijo a la izquierda del nodo recibido o NODO_NULO si no existe. Precondición: el nodo recibido no es NODO_NULO. Postcondición: ninguna.

HIJO_DERECHO (de un nodo determinado): devuelve el hijo a la derecha del nodo recibido o NODO_NULO si no existe. Precondición: el nodo recibido no es NODO_NULO. Postcondición: ninguna.

RAIZ: devuelve el nodo que está en la raíz del árbol o NODO_NULO si el árbol es nulo. Precondición: el árbol debe haber sido creado. Postcondición: ninguna

INSERTAR_HIJO_IZQUIERDA (recibe un árbol y un nodo determinado): inserta el árbol como hijo a la izquierda del nodo. Si ya existe el hijo a izquierda, la primitiva se encarga de que sea destruido junto con sus descendientes.

Postcondición: árbol modificado por la inserción del nuevo nodo

5-11-2018

Precondiciones: el árbol recibido no es ARBOL_VACIO y el nodo no es NODO_NULO.

25

INSERTAR_HIJO_DERECHA (recibe un árbol y un nodo determinado): inserta el árbol como hijo a la derecha del nodo. Si ya existe el hijo a derecha, la primitiva se encarga de que sea destruido junto con sus descendientes. Precondiciones: el árbol recibido no es ARBOL_VACIO y el nodo no es NODO_NULO. Postcondición: árbol modificado por la inserción del nuevo nodo

PODAR_HIJO_IZQUIERDA (de un nodo determinado): devuelve el subárbol con raíz hijo a la izquierda del nodo recibido, al cual se le quita el subárbol izquierdo. Precondición: el nodo recibido no es NODO_NULO. Postcondición: árbol modificado por el borrado de un nodo

PODAR_HIJO_DERECHO (de un nodo determinado): devuelve el subárbol con raíz hijo a la derecha del nodo recibido, al cual se le quita el subárbol derecho. Precondición: el nodo recibido no es NODO_NULO. Postcondición: árbol modificado por el borrado de un nodo

ARBOLES BINARIOS DE BUSQUEDA

Primitivas del árbol binario de búsqueda Crear: crea el árbol BB Precondición: --Postcondición: árbol creado

Insertar (un elemento determinado): agrega el elemento al árbol manteniendo el orden del mismo. Precondición: el árbol debe haber sido creado. Postcondición: árbol alterado por la inserción del nuevo elemento.

Precondiciones: el árbol debe haber sido creado y el elemento debe estar en el mismo.

5-11-2018

Borrar (un elemento determinado): borra el elemento indicado.

Postcondiciones: árbol modificado por el borrado del elemento.

26

Buscar (un elemento determinado): determina si un elemento está o no en el árbol Precondiciones: el árbol debe haber sido creado Postcondiciones. ninguna

TDA ÁRBOL AVL Un árbol binario está equilibrado (según han definido AddelsonVelskii y Landis) si, para cada uno de sus nodos ocurre que las alturas de sus dos subárboles difieren a lo sumo en 1. Los árboles que cumplen esta condición son denominados a menudo árboles AVL. La especificación coincide con la del Árbol binario de búsqueda. La implementación varía en las operaciones que modifican la altura de un nodo: insertar y borrar, porque para mantener tras cada inserción y borrado la condición de equilibrio, se llevan a cabo algunos reajustes locales, cambiando punteros. A través de los árboles AVL se llega a un procedimiento de búsqueda análogo al de los ABB pero con la ventaja de garantizar un caso peor de O(log2 n),y manteniendo el árbol siempre equilibrado. Árbol AVL de altura h con mínima cantidad de nodos: En un árbol de tal característica, debe haber una raíz, un subárbol AVL mínimo de altura h-1 y otro subárbol AVL también mínimo de altura h-2. El número de nodos n(Th) está dado por la relación de recurrencia n(Th) = 1 + n(Th-1) + n(Th-2) Esta relación es similar a la que aparece en los números de Fibonacci (Fn = Fn-1 + Fn-2) (los valores para n(Th) están relacionados con los valores de la sucesión. de Fibonacci)

Resolviendo se llega a log2(n+1)