6531244
Description
Flashcards by rafael negrete oropeza , updated more than 1 year ago
|
Created by rafael negrete oropeza
over 7 years ago
|
|
| Question | Answer |
| arbol :En ciencias de la computación y en informática, un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo {\displaystyle a} a es padre de un nodo {\displaystyle b} b si existe un enlace desde {\displaystyle a} a hasta {\displaystyle b} b (en ese caso, también decimos que {\displaystyle b} b es hijo de {\displaystyle a} a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama. | terminologías : Raíz - El nodo superior del árbol. Padre - Nodo con hijos. Hijo - Nodo descendiente de otro nodo. Hermanos - Nodos que comparten el mismo padre. Hojas - Nodos sin hijos. Nivel - El nivel de un nodo está definido por el número de conexiones entre el nodo y la raíz. |
| tipos de arboles: Árboles Binarios Árbol de búsqueda binario auto-balanceable Árboles AVL Árboles Rojo-Negro Árbol AA Árbol de segmento Árboles Multicamino Árboles B (Árboles de búsqueda multicamino autobalanceados) Árbol-B+ Árbol-B* | Operaciones de árboles. Representación: Las operaciones comunes en árboles son: Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son: Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre. Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array. |
| Uso de los árboles: Usos comunes de los árboles son: Representación de datos jerárquicos. Como ayuda para realizar búsquedas en conjuntos de datos (ver también: algoritmos de búsqueda en Árboles). | Recorrido de árboles: En ciencias de la computación, el recorrido de árboles se refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos). Tales recorridos están clasificados por el orden en el cual son visitados los nodos. Los siguientes algoritmos son descritos para un árbol binario, pero también pueden ser generalizados a otros árboles. |
| Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz: Visite la raíz Atraviese el sub-árbol izquierdo Atraviese el sub-árbol derecho | Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo: Atraviese el sub-árbol izquierdo Visite la raíz Atraviese el sub-árbol derecho |
| Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo: Atraviese el sub-árbol izquierdo Atraviese el sub-árbol derecho Visite la raíz | Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. |
| Nodo padre: nodo que contiene un puntero al nodo actual. Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles. En cuanto a la posición dentro del árbol: | Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'. |
| Nodo hoja: nodo que no tiene hijos. | Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. |
| Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc. | Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos. |
| Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3. | Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc. |
| Definición: Un Arbol Binario es un conjunto finito de nodos el cual es o bien vacío o consta de una raíz y dos árboles binarios disjuntos llamados subárboles derecho e izquierdo. |
Want to create your own Flashcards for free with GoConqr? Learn more.