Presentacion De Arboles

República Bolivariana de Venezuela Ministerio del Poder Popular Para La Defensa Universidad Nacional Experimental Politécnica De La Fuerza Armada Bolivariana Nacional UNEFA – APURE

Lenguaje de programación (Arboles)

Facilitador: Lic. Laryenso Gutiérrez

Participante: Ramón A. Salas CI: V-19.152.049 Morales Adrian CI: V-19.992.115

Arbole s

Es una estructura de datos comúnmente usada que emula la estructura de un árbol con un conjunto de nodos conectados. Cada nodo tiene cero o más nodos hijos, que están por debajo de él (en ciencias de la computación, al contrario que en la naturaleza, los árboles crecen hacia abajo, no hacia arriba) A

B

D

Autores: Ramón Salas , Adrian Morales

E

C

F

A=

Padre

B,C=

Hijos del nodo A

D,E,F=

Hijos del nodo B

B,C=

Hermanos

Componentes de un Árbol Los componentes de un árbol son los siguientes: •Raíz: Nodo que constituye la única entrada a la estructura (por ello es necesario tener un puntero sobre él). •Ramas o Arcos: Conexión entre dos nodos del árbol que representa una relación de jerarquía. •Hojas: Nodo sin hijos.

Autores: Ramón Salas , Adrian Morales

Componentes de un Árbol

Autores: Ramón Salas , Adrian Morales

Componentes de un Árbol •Árboles Binarios •Árbol de búsqueda binario auto-balanceable •Árboles Rojo-Negro •Árboles AVL •Árboles B •Árbol-B+ •Árbol-B* •Árboles Multicamino

Autores: Ramón Salas , Adrian Morales

Ventajas de un Árbol Una de las ventajas de los árboles es que un subárbol tiene las mismas propiedades de un árbol, por lo que los algoritmos recursivos son muy naturales al trabajarlos con árboles

Autores: Ramón Salas , Adrian Morales

Árbol Binario Es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos o descendientes (de ahí el nombre "binario"). A= B= C= B,C=

A

B

Autores: Ramón Salas , Adrian Morales

C

Padre Hijo izquierdo Hijos derecho subárboles y hermanos

Tipos de Árbol Binario •Árbol binario: es un árbol con raíz en el que cada nodo tiene como máximo dos hijos. •Árbol binario lleno: es un árbol en el que cada nodo tiene cero o dos hijos. •Árbol binario perfecto: es un árbol binario lleno en el que todas las hojas están a la misma profundidad.

Autores: Ramón Salas , Adrian Morales

Árbol Binario de Búsqueda AutoBalanceable

Es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. La búsqueda en estos árboles son muy rápidas debido a que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales.

Autores: Ramón Salas , Adrian Morales

Árbol Rojo-Negro Es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación. La estructura original fue creada por Rudolf Bayer en 1972, que le dio el nombre de “árboles-B binarios simétricos”, pero tomó su nombre moderno en un trabajo de Leo J. Guibas y Robert Sedgewick realizado en 1978.

Autores: Ramón Salas , Adrian Morales

Árbol AVL Es un árbol binario de búsqueda que cumple con la condición de que la diferencia entre las alturas de los subárboles de cada uno de sus Nodos es, como mucho 1. La principal ventaja de este tipo de árboles consiste en que existen más nodos en un mismo nivel que en los árboles binarios con lo que se consigue que, si el árbol es de búsqueda, los accesos a los nodos sean más rápidos

Autores: Ramón Salas , Adrian Morales

Árbol AVL

Autores: Ramón Salas , Adrian Morales

Árbol B Son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles B mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado Este tipo de árbol representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos.

Autores: Ramón Salas , Adrian Morales

Árbol B+ Es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial.

Árbol B* Es otra de las variantes de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Este árbol tiene la particularidad de que cuando sus ambos nodos están llenos, entonces los dos nodos se transforman en tres.

Conclusión General

R R H

D

Autores: Ramón Salas , Adrian Morales

A

B

E

C

F

Gracias por su Tiempo   "Podrán morir las personas, pero jamás sus

ideas.“ Ernesto CHE Guevara

Autores: Ramón Salas , Adrian Morales