6530401
Description
Flashcards by Alexis Uribe, updated more than 1 year ago
|
Created by Alexis Uribe
over 8 years ago
|
|
| Question | Answer |
| Árbol | Es una estructura de datos jerárquica. La relación entre los elementos es de uno a muchos. |
| Tipos de Árbol | Lineales (listas enlazadas, pilas y colas) No lineales (arboles binarios y grafos o redes). |
| Terminología | Nodo: Cada elemento en un árbol. Nodo Raíz: Primer elemento agregado al árbol. Nodo Padre: Se le llama así al nodo predecesor de un elemento. |
| Terminología | Nodo Hijo: Es el nodo sucesor de un elemento. Hermanos: Nodos que tienen el mismo nodo padre. Nodo Hoja: Aquel nodo que no tiene hijos. Subárbol: Todos los nodos descendientes por la izquierda o derecha de un nodo. |
| Árbol Binario de Búsqueda | Este tipo de árbol permite almacenar información ordenada. Reglas a cumplir: Cada nodo del árbol puede tener 0, 1 ó 2 hijos. Los descendientes izquierdos deben tener un valor menor al padre. Los descendientes derechos deben tener un valor mayor al padre. |
| Implementación de un ABB… | class NodoArbol { public: int info; NodoArbol *izq, *der; NodoArbol( ); NodoArbol(int dato); }; NodoArbol(void) { izq = der = NULL; } NodoArbol(int dato) { info = dato; izq = der = NULL; } class ABB { private: NodoArbol *raiz; public: ABB( ); // constructor ~ABB( ); // destructor //otros métodos }; |
| Implementación de la búsqueda | ... p=raiz; while (p != NULL) { if (p->info == valor) return p; else p=(p->info > valor? p->izq: p->der); } return NULL; … |
| Comentarios importantes. | El orden de inserción de los datos, determina la forma del ABB. ¿Qué pasará si se insertan los datos en forma ordenada? La forma del ABB determina la eficiencia del proceso de búsqueda. Entre menos altura tenga el ABB, más balanceado estará, y más eficiente será. |
| Proceso para eliminar un nodo | Si el nodo a eliminar es un: Nodo hoja Buscar el Nodo Padre del nodo a borrar. Desconectarlo. Liberar el nodo. Nodo con un hijo Buscar el Nodo Padre del nodo a borrar. Conectar el hijo con el padre del nodo a borrar. Liberar el nodo. Nodo con dos hijos Localizar el nodo predecesor o sucesor del nodo a borrar. Copiar la información. Eliminar el predecesor o sucesor según sea el caso. |
| Alexis Uribe Rendón |
Want to create your own Flashcards for free with GoConqr? Learn more.