Arboles De Busqueda

Contenido

Introducción 2

Aplicación de arboles binarios 2

Arboles binarios de búsqueda 3

Búsqueda 3

Inserción 3

Borrado 4

Conclusión 4

Bibliografía 5

Introducción

La mayoría de los árboles binarios son de búsqueda

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:

• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario de búsqueda.

• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario de búsqueda.

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo:

* No tiene hijos (hoja).

* Tiene un hijo izquierdo y un hijo derecho.

Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

Definición de teoría de grafos

Un árbol binario sencillo de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 2

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, a cíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.

Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si reusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.

Tipos de árboles binarios

* Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

* Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.

* Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)

* A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Aplicación de árboles binarios

De las estructuras de datos de tipo Árbol, la especie más utilizada es el Árbol Binario de Búsqueda. Los principales tipos de árboles binarios de búsqueda son los AVL, B* y balanceado.

Los árboles binarios de búsqueda se utilizan para localizar en forma rápida un elemento almacenado en ese árbol, a partir de una clave. Son una forma de implementar arreglos asociativos o mapas, en donde se almacenan elementos que son pares <clave, valor>.

En las bases de datos relacionales, para poder localizar en

...