Arbol Binaio B

Actividad 1: ¿Qué es un Árbol Binario de Búsqueda?

Son estructuras de datos no lineales llamados también ABB que presentan un gran rendimiento cuando las funciones a realizar implican búsquedas, inserciones y eliminación de nodos. En el árbol binario los elementos mayores a él, se ubican en su rama derecha, mientras que los elementos menores van en su rama izquierda. Cada elemento se almacena una sola vez por lo que no existen elementos repetidos.

Indique las condiciones que debe cumplir un árbol binario de búsqueda.

Existe el árbol binario vacío y el no vacío, no obstante el árbol binario no vacío cumple con las siguientes condiciones.

 Todos los nodos están identificados por una clave y no existen dos elementos con la misma clave.

 Las claves de los nodos del subárbol izquierdo son menores que la clave del nodo raíz.

 Las claves de los nodos del subárbol derecho son mayores que la clave del nodo raíz.

 Los subárboles izquierdo y derecho son también árboles binarios de búsqueda.

Cuál es el orden que deben llevar sus nodos.

Cada elemento (nodo) de un árbol ABB cuenta con tres campos:

- Nodo raíz, dato (número, letra, palabra etc.).

- Puntero al nodo derecho.

- Puntero al nodo izquierdo.

Existen tres formas de manera recursiva de recorrer un árbol binario por cada nodo.

Inorden: Si visitamos primero hijo izquierdo, luego el padre y finalmente el hijo derecho

Preorden: Primero el padre, luego el hijo izquierdo y finalmente el hijo derecho.

Postorden: Primero hijo izquierdo, luego el hijo derecho y finalmente el padre.

Cuál es la utilidad de los ABB.

Recordemos que los ABB para poder implementarlos en el lenguaje C++ tenemos que tener conocimientos previos sobre listas enlazadas .

Operaciones con árboles binarios, búsqueda, inserción y borrado.

Búsqueda:

Suponga que se busca un elemento que posea una clave x. La búsqueda comenzará por el nodo raíz del árbol. La clave de ese nodo informará por dónde debe continuar la búsqueda, ya no es necesario recorrer exhaustivamente todos los nodos del árbol. Si la clave del nodo es igual a x, la búsqueda finaliza con éxito. Si la clave es menor que x, se sabe que si existe un nodo que posea como clave el valor x, deberá estar en el subárbol derecho, por lo tanto la búsqueda deberá continuar por esa parte del árbol. Si, por el contrario, la clave del nodo es mayor que x, entonces la búsqueda deberá continuar por el subárbol izquierdo. El proceso continuará hasta que se encuentre un nodo con clave igual a x o un subárbol vacío, en cuyo caso se puede asegurar que no existe ningún nodo con clave x en el árbol.

Inserción:

La inserción de un nuevo nodo en un árbol binario

...