Arboles

A B

C E

Facilitador: Laryenso Gutiérrez

ARBOLE S F

G

D H

Bachilleres: Nieves Karla C.I:20.723.119 Suarez Reny C.I:20.120.563 Viera Urian C.I:20.004.322

I

ARBOLES

Árbol es el nombre que se le da a un grupo versátil de estructuras de dato. Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Se pueden utilizar para implementar un número de interfaces abstractas, incluida la interfaz List, pero las aplicaciones en las que resultan más útiles emplean estructuras de ramas de árboles para representar alguna propiedad de los elementos de los datos o para optimizar ciertos métodos Los arboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro AUTORES:

NIEVES

KARLA,SUAREZ

Existen cuatro tipos de árbol binario: Árbol Binario Distinto.

CLASIFICACION DE LOS ARBOLES

Árbol Binario Similares.

A

Árbol Binario Equivalentes.

B

D

C E

F

G

H

Árbol Binario Completos.

I

clic

AUTORES:

NIEVES

KARLA,SUAREZ

Árbol Binario Distinto: Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes Árbol Binario Similar: Dos arboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente. Árbol Binario Equivalente: Son aquellos arboles que son similares y que además los nodos contienen la misma información. Árbol Binario Completo: Son aquellos arboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbolB derecho. Subárbol Izquierdo

AUTORES:

NIEVES

KARLA,SUAREZ

HIJOS

A

Subárbol Derecho

D

C E

F HIJOS

G H

I

REPRESENTACION DE LOS ARBOLES

RAIZ HERMANOS

RAIZ RAMA NODOS HOJAS

PADRE HIJOS AUTORES:

NIEVES

KARLA,SUAREZ

HOJAS

OPERACIONES BÁSICAS DE LOS ARBOLES.

•Buscar un elemento. •Insertar un elemento. •Borrar un elemento. •Movimientos a través del árbol: Izquierda. Derecha. Raíz. •Información: Comprobar si un árbol está vacío. Calcular el número de nodos. Comprobar si el nodo es hoja. Calcular la altura de un nodo. Calcular la altura de un árbol. AUTORES:

NIEVES

KARLA,SUAREZ

S

E OL

D S O

E

B R A

TIP

Árbol AVL: Arboles balanceados o equilibrados: • Un árbol binario de búsqueda es k-equilibrado si cada nodo lo es. • Un nodo es k-equilibrado si las alturas de sus subárbol es izquierdo y derecho difieren en no más de k. Arboles AVL (Anderson, Vel’skii, Landis) • Un árbol binario de búsqueda 1-equilibrado se llama árbol AVL. Cabe destacar que un árbol AVL no es un Tipo de dato abstracto sino una estructura de datos.

Árbol B: Es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo. Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un árbol que satisface las siguientes propiedades: Cada nodo tiene como máximo M hijos. Cada nodo (excepto raíz y hojas) tiene como mínimo M/2 hijos. La raíz tiene al menos 2 hijos si no es un nodo hoja. Todos los nodos hoja aparecen al mismo nivel, y no tienen hijos. Un nodo no hoja con k hijos contiene k-1 elementos almacenados. Los hijos que cuelgan de la raíz (r1, • • • rm) tienen que cumplir ciertas condiciones: El primero tiene valor menor que r1. El segundo tiene valor mayor que r1 y menor que r2 etc. El último hijo tiene mayor que m . AUTORES:

NIEVES

KARLA,SUAREZ

CARACTERISTICOS DE LOS ARBOLES

•Nodos internos solo contienen las claves o

A

apuntadores. •Todas las hojas se encuentran al mismo nivel.

B

D

C E

•Nodos hojas se encuentran ligados como una lista

F

enlazada para permitir la búsqueda más eficiente. •El mínimo de claves es 2.

G H

I

•Otra

característica

que

normalmente

tendrán

nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.

AUTORES:

NIEVES

KARLA,SUAREZ

RECORRIDO DE LOS ARBOLES BINARIOS Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol. Los tres tipos son: Hay tres formas en in orden, pre orden y post orden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación: Pre orden •Examinar la raíz. •Recorrer el subárbol izquierdo en pre orden. •recorrer el subárbol derecho en pre In orden orden. •Recorrer el subárbol izquierdo en in orden. •Examinar la raíz. •Recorrer el subárbol derecho en in Post orden: orden. • Recorrer el subárbol izquierdo en post orden. •Recorrer el subárbol derecho en post AUTORES: NIEVES KARLA,SUAREZ orden.

TERMINILOGIA.

Raiz Hermanos

Raiz Rama

Padre

subarbol

Hijos AUTORES:

NIEVES

KARLA,SUAREZ

HOJAS

AUTORES:

NIEVES

KARLA,SUAREZ