Estructura De Datos

ESTRUCTURAS NO LINEALES

Introducción

El siguiente trabajo trata sobre la estructura de datos no lineales llamada árbol. Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos. También hablaremos sobre los conceptos de grafos y todo lo que conlleva.

Contenido

ARBOLES

Los árboles son estructuras dinámicas no lineales, es decir a cada elemento de la estructura solo le sigue otro, en el caso de los árboles a estos les puede seguir uno o más elementos, es decir que un elemento de la estructura puede apuntar a varios, además de esto son dinámicos ya que se pueden crear elementos que conformen el árbol cuando se requiera y en cualquier parte del programa.

Estructuras estáticas Estructuras dinámicas

Arreglos Listas

Pilas Árboles

Colas

Estructuras lineales Estructuras no lineales

Arreglos Árboles

Pilas Árboles

Colas

Listas

CLASIFICACIÓN DE ARBOLES.

• Árbol de búsqueda perfectamente balanceado.

Definición: Para todo nodo, la cantidad de nodos de su subárbol izquierdo difiere como máximo en 1 de la cantidad de nodos del subárbol derecho.

En el peor caso, la búsqueda necesita O(log n).

La inserción puede necesitar reorganizar todo el árbol, O(n).

• Árbol balanceado ó AVL (Adelson-Velskii y Landis).

Es un árbol binario de búsqueda, con una condición de balanceo más débil que hace que no sea tan costoso el proceso de balancear un árbol.

Definición: Para todo nodo, la altura de sus subárboles difiere como máximo en 1. (Supondremos que la altura del árbol vacío es -1.)

• Árboles Binarios

Un árbol binario, es aquel que tiene como máximo 2 descendientes, es decir cada uno de los nodos del árbol tiene un máximo de 2 hijos; además si es binario de búsqueda se define de manera formal como: “Para todo nodo T del árbol debe cumplirse que todos los valores de los nodos del subárbol izquierdo de T serán menores o iguales al valor del nodo T. De forma similar, todos los valores de los nodos del subárbol derecho de T deben ser mayores o iguales al valor del nodo T”.

Por lo mismo se pueden realizar las operaciones de búsqueda, inserción y eliminación, de manera más eficiente en este tipo de árbol.

Por ejemplo si tenemos los siguientes valores para insertar en un árbol binario de búsqueda:

34-10-56-82--46-25

GRAFOS

Los grafos son un conjunto de puntos, de los cuales algún par de ellos está conectado por unas líneas. Si estas líneas son flechas, hablaremos de grafo dirigido (digrafo), mientras que si son simples líneas estamos ante un grafo no dirigido.

Las estructuras

...