Operaciones con árboles binarios de búsqueda

Ahora que ya sabemos como funcionan los árboles binarios de búsqueda, vamos a estudiar como trabajar con ellos. Las operaciones con árboles binarios de búsqueda que podemos realizar son: Búsqueda, inserción y eliminación de un nodo.

Búsqueda de un nodo

Cuando queremos recuperar datos de nuestra estructura de árbol binario de búsqueda, sacaremos provecho de que estas estructuras están ordenadas. Básicamente, empezaríamos comprobando el nodo raíz, y si este es el que buscamos, ya hemos acabado. Si no lo es, nos moveríamos a su hijo izquierdo o al derecho, dependiendo de si el dato que buscamos es menor o mayor del que contiene el nodo padre. Y así proseguiríamos hasta encontrar el dato o terminar de recorrer el árbol sin encontrarlo.

Este proceso es recursivo, ya que cuando nos movemos a un nodo hijo, podemos considerar a este como el nodo raíz de un nuevo árbol. El proceso de búsqueda podría expresarse como:

Flujo para la búsqueda de un nodo
Flujo para la búsqueda de un nodo

Que también podríamos representar en seudocódigo de la siguiente manera:

Encontrado (Arbol, buscado){
Si no existe Arbol -> No encontrado
Si existe Arbol {
   Si valor Raiz= buscado ->Encontrado
   Si valor Raiz <> buscado{
       Si valor Raiz >buscado{
           árbol = nodo izquierdo
           Encontrado(Arbol, buscado)
           }
       Si valor Raiz < buscado{
           árbol = nodo derecho
           Encontrado(Arbol, buscado)
           }
       }
   }
}
Sigue leyendo Operaciones con árboles binarios de búsqueda

Árboles binarios de búsqueda

Un árbol binario de búsqueda es una estructura ordenada de datos donde cada registro puede estar relacionado con otros dos registros. Vamos a prestar especial atención a los árboles binarios de búsqueda, ya que son muy populares y ampliamente utilizados en BBDD. Como ya adelantaba en el post anterior, los arboles binarios son de orden 2, es decir, sus nodos pueden tener un máximo de dos hijos. Y si además es de búsqueda, tiene que cumplir las siguientes condiciones para todos los nodos:

  • Si el nodo tiene un hijo izquierdo, este tiene que ser menor que él.
  • Si el nodo tiene un hijo derecho, este tiene que ser mayor que él.
Sigue leyendo Árboles binarios de búsqueda