Algoritmo de borrado de claves

Borrar nodos es algo más complicado, como veremos ahora. También se trata de un algoritmo iterativo, aunque puede implementarse recursivamente.

  • Buscar el nodo donde está la clave que queremos borrar.
  • Si la clave no está en el árbol, salimos sin hacer nada.
  • Buscamos la posición que ocupa la clave dentro del nodo.
  • ¿Se trata de un nodo hoja o terminal?
    • SI:
      • hoja = nodo
    • NO:
      • Intercambiar clave con la clave siguiente. Se trata de la primera clave del nodo hoja obtenido al seguir la rama izquierda a partir del nodo derecho de la clave actual.
      • hoja = nodo de la siguiente clave
  • Eliminar clave, se consigue rotando las claves siguientes dentro del nodo y decrementando el número de claves usadas del nodo.
  • Si el número de claves usadas es cero y hoja es el nodo de entrada:
    • SI:
      • Entrada = NULL
      • Borrar hoja
      • Salir.
  • Hoja es el nodo de entrada o el número de claves usadas es mayor del número mínimo de claves por nodo:
    • SI:
      • Salir.
  • Bucle:
    • Buscar el puntero que apunta a hoja en nodo padre: posClavePadre.
    • Localizar los nodos izquierdo y derecho del nodo hoja.
    • Si existe el nodo derecho y contiene más claves que el número mínimo.
      • SI:
        • Pasar una clave del nodo derecho a padre, en posClavePadre y la clave que había allí al nodo hoja.
        • Salir.
    • Si existe el nodo izquierdo y contiene más claves que el número mínimo.
      • SI:
        • Pasar una clave del nodo izquierdo a padre, en posClavePadre y la clave que había allí al nodo hoja.
        • Salir.
    • Si existe el nodo derecho.
      • SI:
        • Fundir en hoja los nodos hoja y derecho junto con la clave del nodo padre posClavePadre. Borrar nodo derecho.
        • Si padre es el nodo de entrada y no tiene claves.
          • SI:
            • entrada = hoja
            • borrar nodo padre
            • salir
      • NO: (Entonces debe existir un nodo izquierdo)
        • Fundir en izquierdo los nodos hoja y izquierdo junto con la clave del nodo padre posClavePadre. Borrar nodo hoja.
        • Si padre es el nodo de entrada y no tiene claves.
          • SI:
            • entrada = izquierdo
            • borrar nodo padre
            • salir
    • hoja = padre
    • Si hoja no es NULL, ni hoja es el nodo de entrada ni el número de claves en hoja es menos que el mínimo.
      • SI:
        • cerrar bucle.
      • NO:
        • Salir.

Veremos ahora algunos ejemplos.

Clave en nodo hoja y número de claves mayor que el mínimo

Borraremos la clave 65. Es uno de los casos más sencillos, la clave está en un nodo hoja, y el número de claves del nodo después de eliminarla es mayor del mínimo.

Borrado en nodo hoja (1)
Borrado en nodo hoja (1)

Tan sólo tendremos que eliminar la clave:

Borrado en nodo hoja (2)
Borrado en nodo hoja (2)

Clave en nodo intermedio

Eliminaremos ahora la clave 20.

Borrado en intermedio (1)
Borrado en nodo intermedio (1)

Según el algoritmo debemos intercambiar la clave por el siguiente valor, es decir, el 25. En general será la primera clave del nodo más a la izquierda a de la rama derecha de la clave a borrar.

Borrado en intermedio (2)
Borrado en nodo intermedio (2)

Ahora estamos en el mismo caso que antes, sólo hay que borrar la clave 20 del nodo hoja:

Borrado en intermedio (3)
Borrado en nodo intermedio (3)

Borrar clave cuando el número de claves es menor que el mínimo

Eliminaremos el nodo 12 del árbol:

Borrado con claves menor mínimo (1)
Borrado con claves menor del mínimo (1)

La primera parte es fácil, bastará eliminar la clave, pero el resultado es que sólo queda una clave en el nodo, y debe haber al menos dos claves en un nodo de cuatro.

Borrado con claves menor mínimo (2)
Borrado con claves menor del mínimo (2)

Según el algoritmo, buscaremos los nodos izquierdo y derecho. Si el número de claves en el nodo derecho es mayor que el mínimo, pasaremos una clave del nodo derecho al padre y de éste al nodo hoja. Si no, lo intentaremos con el izquierdo. En este caso nos vale el nodo derecho:

Borrado con claves menor mínimo (3)
Borrado con claves menor del mínimo (3)

Borrar clave cuando implica borrar nodos

Vamos a ver el caso en que tanto el nodo derecho como el izquierdo no tienen claves suficientes para transferir una al nodo hoja. Borraremos la clave 5:

Borrado con borrado de nodo (1)
Borrado con borrado de nodo(1)

La primera parte es igual que el caso anterior, eliminamos la clave 5. Pero ahora el nodo derecho tiene el número mínimo de claves, y el izquierdo no existe.

Borrado con borrado de nodo (2)
Borrado con borrado de nodo(2)

Según el algoritmo, debemos fundir en el nodo hoja, las claves del nodo hoja, la clave del padre y las del nodo derecho. Y después eliminar el nodo derecho.

Borrado con borrado de nodo (3)
Borrado con borrado de nodo(3)

La cosa no termina ahí, ahora debemos comprobar el nodo padre, ya que también ha podido quedar con menos claves que el mínimo exigido. En este caso sucede eso, pero es un caso especial, ya que ese nodo es el de entrada y puede contener menos claves que número mínimo.

Caso de reducción de altura

Veamos cómo sería el proceso en un caso general, que implica la reducción de altura del árbol.

Borraremos la clave 65 de este árbol:

Borrado con reducción de altura (1)
Borrado con reducción de altura (1)

El primer paso es intercambiar la clave 65 por la siguiente, la 67. Y hacer que el nodo al que pertenece sea el nodo hoja:

Borrado con reducción de altura (2)
Borrado con reducción de altura (2)

A continuación eliminamos la clave 65 del nodo hoja, y comprobamos que el nodo tiene menos claves del mínimo. Buscamos el nodo derecho e izquierdo.

Borrado con reducción de altura (3)
Borrado con reducción de altura (3)

El nodo izquierdo no existe, y el derecho tiene justo el número mínimo de claves, por lo tanto tenemos que fusionar hoja con derecho y con una clave de padre. Y eliminamos el nodo derecho.

Borrado con reducción de altura (4)
Borrado con reducción de altura (4)

Ahora el nodo hoja es el padre del anterior nodo hoja. De nuevo comprobamos que tiene menos claves que el mínimo, así que buscamos los nodos derecho e izquierdo. Y de nuevo comprobamos que el nodo derecho no existe y que el izquierdo tiene justo el número mínimo de claves.

Ahora fusionamos en el nodo izquierdo con el nodo hoja y con una clave del nodo padre, y eliminamos el nodo hoja, como además el nodo padre es el de entrada y ha quedado vacío, lo eliminaremos y el nodo de entrada será el izquierdo:

Borrado con reducción de altura (5)
Borrado con reducción de altura (5)

Programa en C++


  Nombre Fichero Fecha Tamaño Contador Descarga
D Ejemplo Arbol-B Btree.zip 2001-08-01 11735 bytes 1566



suministrado por FreeFind
Valid HTML 4.0! Valid CSS!