6524994
Description
Flashcards by MIRIAM SANTOS ESPINOSA , updated more than 1 year ago
|
|
Created by MIRIAM SANTOS ESPINOSA
about 8 years ago
|
|
| Question | Answer |
| ARBOLES BINARIOS A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos. | La representación gráfica de un árbol binario es la siguiente: |
| Hay dos formas tradicionales de representar un árbol binario en memoria: Por medio de datos tipo punteros también conocidos como variables dinámicas o listas. Por medio de arreglos. Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras. | Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión. Cada nodo se representa gráficamente de la siguiente manera: |
| Existen cuatro tipos de árbol binario:. Distinto. Similares. Equivalentes. Completos. | A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos. |
| DISTINTO Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. | Ejemplo: |
| SIMILARES Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. | Ejemplo: |
| EQUIVALENTES Son aquellos arboles que son similares y que además los nodos contienen la misma información | Ejemplo: |
| COMPLETOS Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subarbol izquierdo y el subarbol derecho. | Ejemplo: |
| Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. | Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación: |
| INORDEN Recorrer el subarbol izquierdo en inorden. Examinar la raíz. Recorrer el subarbol derecho en inorden. | Ejemplo: |
| PREORDEN Examinar la raíz. Recorrer el subarbol izquierdo en preorden. recorrer el subarbol derecho en preorden. | Ejemplo: |
| POSTORDEN Recorrer el subarbol izquierdo en postorden. Recorrer el subarbol derecho en postorden. Examinar la raíz. | Ejemplo: |
| Arboles Enhebrados ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor. ARBOL ENHEBRADO A LA IZQUIERDA. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden. | El siguiente ejemplo es un árbol binario enhebrado a la derecha. |
| Arboles binarios de busqueda Un árbol de búsqueda binaria es una estructura apropiada para muchas de las aplicaciones que se han discutido anteriormente con listas. La ventaja especial de utilizar un arbol es que se facilita la búsqueda. Un árbol binario de búsqueda es aquel en el que el hijo de la izquierda (si existe) de cualquier nodo contiene un valor más pequeño que el nodo padre, y el hijo de la derecha (si existe) contiene un valor más grande que el nodo padre. | Un ejemplo de arbol binario de búsqueda es el siguiente: |
| La terminología es la siguiente: HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y. PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y. HERMANO. Dos nodos serán hermanos si son descendientes directos de un mismo nodo. | HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos). NODO INTERIOR. Es un nodo que no es raíz ni terminal. GRADO. Es el número de descendientes directos de un determinado nodo. |
| GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol. NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1. ALTURA. Es el máximo número de niveles de todos los nodos del árbol. | PESO. Es el número de nodos del árbol sin contar la raíz. LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente. |
| Árbol Binario Equilibrado Un Árbol Binario está Equilibrado o es Perfectamente Balanceado si la diferencia de alturas de los hijos derecho e izquierdo es, como máximo de 1 | Ejemplo: |
| Inserción de un nodo | Los pasos que se deben realizar para agregar un nuevo nodo a un árbol binario de búsqueda son los siguientes: 1. Comparar la clave a insertar con la raíz del árbol. Si es mayor, se sigue con el a subárbol derecho. Si es menor, se continúa con el subárbol izquierdo. |
| 2. Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las siguientes a condiciones: 2.1 El subárbol derecho, o el subárbol izquierdo, es igual a vacío, en cuyo caso se procederá a insertar el elemento en el lugar que le corresponde. | Ejemplo: |
| Eliminación de Nodos en un Árbol Binario La eliminación de nodos en un árbol binario depende del numero de hijos que tenga el nodo. Existen tres casos: | a) El Nodo No Tiene Hijos Entonces el nodo se elimina simplemente remplazando su posicion por el puntero null. b) El Nodo Tiene Un Hijo Entonces el nodo se elimina remplazando su posicion por la posicion del hijo unico que tiene. |
| c) El Nodo Tiene Dos Hijos Entonces el nodo es eliminado y es remplazado por el sucesor mayor de sus dos hijos. |
Want to create your own Flashcards for free with GoConqr? Learn more.