Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

ESTRUCTURAS Y BASE DE DATOS -- ARBOLES

No description
by

Carlos Mondragon

on 1 July 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of ESTRUCTURAS Y BASE DE DATOS -- ARBOLES

Características del árbol, en relación a su tamaño.
Definicion:
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Ejemplo de un arbol

Nodo hijo
: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.

Nodo padre
: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre.

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. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Nodo rama
: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Todos los nodos deben contener el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama
árbol completo.
BUSQUEDA

Orden
: 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
: 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. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.

Altura
: 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.

ARBOLES BINARIOS
Se trata de árboles de orden 2 o arboles binarios en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.
La búsqueda consiste en acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica.
La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
INSERCION Ó INSERTAR
La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el subárbol izquierdo y si es mayor se inserta en el subárbol derecho.
Operaciones en arboles binarios
• Buscar un elemento.
• Insertar un elemento.
• Borrar un elemento.
• Movimientos a través del árbol:
o Izquierda.
o Derecha.
o Raiz.
• Información:
o Comprobar si un árbol está vacío.
o Calcular el número de nodos.
o Comprobar si el nodo es hoja.
o Calcular la altura de un nodo.
o Calcular la altura de un árbol.

ESTRUCTURAS Y BASE DE DATOS -- ARBOLES

BORRADO
Existen varios casos para el borrado dentro de un arbol.
Borrar un nodo sin hijos o nodo hoja: S
implemente se borra y se establece a nulo el apuntador de su padre.
Borrar un nodo con un subárbol hijo:
Se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
Borrar un nodo con dos subárboles hijo:
Consta de remplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho).
Nodo a eliminar 70
Nodo a eliminar 74
Nodo a eliminar 59
MOVIMIENTOS A TRAVEZ DEL ARBOL
Para movernos a través del árbol usaremos punteros auxiliares, de modo que desde cualquier puntero los movimientos posibles serán: moverse al nodo raíz de la rama izquierda, moverse al nodo raíz de la rama derecha o moverse al nodo Raiz del árbol.
INFORMACION
Hay varios parámetros que podemos calcular o medir dentro de un árbol. Algunos de ellos nos darán idea de lo eficientemente que está organizado o el modo en que funciona.
* Comprobar si un árbol está vacío.
Un árbol está vacío si su raíz es NULL.
* Calcular el número de nodos.
Tenemos dos opciones para hacer esto, una es llevar siempre la cuenta de nodos en el árbol al mismo tiempo que se añaden o eliminan elementos. La otra es, sencillamente, contarlos.
* Comprobar si el nodo es hoja.

Basta con comprobar si tanto el árbol izquierdo como el derecho están vacíos. Si ambos lo están, se trata de un nodo hoja.
* Calcular la altura de un nodo.
Lo que haremos es buscar el elemento del nodo de que queremos averiguar la altura. Cada vez que avancemos un nodo incrementamos la variable que contendrá la altura del nodo.
-Empezamos con el nodo raíz apuntando a Raiz, y la 'Altura' igual a cero.
- Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda y el valor de la altura es 'Altura'.
- Incrementamos 'Altura'.
-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 la búsqueda en el árbol derecho.

* Calcular la altura de un árbol
.
Para buscar este valor tendremos que recorrer todo el árbol, de nuevo es indiferente el tipo de recorrido que hagamos, cada vez que cambiemos de nivel incrementamos la variable que contiene la altura del nodo actual, cuando lleguemos a un nodo hoja compararemos su altura con la variable que contiene la altura del árbol si es mayor, actualizamos la altura del árbol.

- Iniciamos un recorrido del árbol en postorden, con la variable de altura igual a cero.
- Cada vez que empecemos a recorrer una nueva rama, incrementamos la altura para ese nodo.
- Después de procesar las dos ramas, verificamos si la altura del nodo es mayor que la variable que almacena la altura actual del árbol, si es así, actualizamos esa variable.
+ Mondragon Mendoza Carlos Alberto
+ Aguilar Perez Carlos
+ Hernandez Javier
3CV2
Estructuras y Base de Datos
Prof. Anzaldo Bustos Jorge
Full transcript