Estructura De Rbol







































Índice

Concepto 1
Características 2
Operaciones básicas 2
Búsqueda e inserción 3
Eliminación 4
Ejemplos 4
Conclusión 6
Bibliografía 7












Estructura de árbol.

Concepto

Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende envarias ramificaciones o líneas (edges), cada una de las cuales puede extenderse en ramificaciones hasta terminar, finalmente en una hoja.

En computación definimos un árbol como un conjunto de nodos y líneas. Un nodo es un elemento de información que reside en el árbol. Una línea es un par de nodos ordenados , y a la secuencia de líneas se le denomina ruta (path).


Terminologías utilizadas enárboles

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 1+ el número de conexiones entre el nodo y la raíz.

Tipos de árboles

Árboles Binarios
Árbol de búsqueda binario auto-balanceable
Árboles AVL
Árboles Rojo-Negro
Árbol AA

Árbol desegmento

Árboles Multicamino
Árboles B (Árboles de búsqueda multicamino autobalanceados)
Árbol-B+
Árbol-B*

Características

1) NODO indica un elemento, o ítem, de información.

2) Todo árbol que no es vacío, tiene un único nodo raíz.

3) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. X es hijo de Y.

4) Un nodo X es antecesor directo de un nodo Y,si el nodo X apunta al nodo Y. X es padre de Y.

5) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

6) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

7) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.
8) Grado es el número de descendientes directos de undeterminado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol.

9) 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.

10) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.


Además, los árboles tienen las siguientes propiedades:


Tienen un nodo al que se le llama raíz delárbol.
Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no tiene ninguna).
Existe una ruta única del nodo raíz a todos los demás nodos del árbol.
Si hay una ruta , entonces a "b" se le denomina, hijo de "a" y es el nodo raíz de un subárbol.

Operaciones básicas

Tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:

Añadir oinsertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través del árbol.
Recorrer el árbol completo.

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).

Búsqueda e inserción

Partiendo siempre del nodo raíz, el modo de buscar un elemento se define deforma recursiva.
Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol.
Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda con éxito.
Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda en el árbol izquierdo.
Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos labúsqueda en el árbol derecho.
El valor de retorno de una función de búsqueda en un ABB puede ser un puntero al nodo encontrado, o NULL, si no se ha encontrado.


Para insertar un elemento nos basamos en el algoritmo de búsqueda. Si el elemento está en el árbol no lo insertaremos. Si no lo está, lo insertaremos a continuación del último nodo visitado.
Necesitamos un puntero auxiliar para conservar...

Leer documento completo

Regístrate para leer el documento completo.