Variantes de arboles binarios de busqueda

INSTITUTO POLITECNICO NACIONAL
ESCUELA SUPERIOR DE CÓMPUTO



ALUMNA:

PROFESOR: EDGARDO
ADRIAN
FRANCO

MATERIA: ESTRUCTURAS
DE
DATOS

GRUPO: 2CV4

“VARIANTES DE ARBOLES BINARIOS DE BUSQUEDA”

Abril de 2010

INDICE

Introducción……………………………………………………………………………………………………………..02

Desarrollo………………………………………………………………………………………………………………..03

ÁrbolRojo-Negro……………………………………………………………………………………………...03

Funcionamiento……………………………………………………………………………………...04

Utilidad y ventajas.……………………………………………………………………….…………05

Árbol Biselado…………………………………………………………………………………………………06

Funcionamiento……………………………………………………………………………………...06

Ventajas y Desventajas…………………………………………………………..…………………07

Conclusión………………………………………………………………………………………………………………08Bibliografía………………………………………………………………………………………………………………09

INTRODUCCION

En ciencias de la computación un árbol binario es una estructura de datos que consta de un conjunto finito de elementos llamados nodos y un conjunto finito de líneas dirigidas llamadas ramas, que conectan a los nodos; en el que cada uno de los nodos del árbol puede tener de 0 a 2 subárboles, los cuales reciben un nombrede acuerdo al caso en que se encuentren:

* Si el nodo raíz (primer nodo del árbol) tiene 0 relaciones se llama hoja.
* Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo.
* Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.

La definición de un árbol binario esrecursiva, ya que esta se basa en si misma, es decir que de un caso base la cual seria la raíz podemos sacar un caso general la cual seria cada una de las ramas del árbol.

Un árbol puede estar ordenado o no, sin embargo son de mayor utilidad los arboles ordenados. Estos se conocen como arboles binarios de búsqueda, debido a que se pueden buscar en ellos un término a través de algoritmos. Podemosreconocer a un árbol de búsqueda porque cumple con la siguiente condición: dado un nodo, todos los datos del subárbol izquierdo son más pequeños que los datos contenidos en el nodo, mientras que los datos del subárbol derecho son mayores a los contenidos en el nodo especificado.

Como se menciono anteriormente en estos tipos de arboles existen ciertos algoritmos que te permiten recorrer el árbolpara buscar algún término en especial, existen 2 formas de hacerlo el recorrido a anchura y el recorrido a profundidad. En el primero se visitan los nodos por niveles, para ello se utiliza una estructura auxiliar tipo cola en la que después de mostrar el contenido de un nodo, empezando por el nodo raíz, se almacenan los punteros correspondientes a sus hijos izquierdo y derecho. De esta forma sirecorremos los nodos de un nivel, mientras mostramos su contenido, almacenamos en la cola los punteros a todos los nodos del nivel siguiente.

El recorrido en profundidad se realiza a través de uno de los siguientes métodos recursivos:
* Preorden. En este método primero se visita la raíz, luego el sub-árbol izquierdo y posteriormente el derecho.
* Inorden. En este método primero se visitael sub-árbol izquierdo, posteriormente la raíz y por ultimo el sub-árbol derecho.
* Postorden. En este método se comienza visitando el sub-árbol izquierdo, luego el sub-árbol derecho y finalmente la raíz.

Los arboles binarios de búsqueda son reconocidos por tener gran eficiencia en la inserción de elementos, la búsqueda de elementos y el borrado de los arboles en comparación con losarreglos.

Se dice que un árbol esta equilibrado cuando cada uno de sus nodos tiene un equilibrio de 1, 0, -1.

Existen variaciones sobre estos arboles como los AVL o Red-Black que sin cumplir al 100% el criterio de un árbol equilibrado, evitan problemas como el de obtener un lista degenerada; estas variaciones surgen con el objetivo de mantener la eficiencia en la operación de búsqueda, ya que...