← Estructuras de datos desde cero · Lección 21/32

Borrar, y por qué hay que balancear

1/8

Borrar: tres casos

Primero se busca el nodo, como siempre. Luego depende de cuántos hijos tenga:

Ninguno (una hoja): se quita y ya.
Uno: su hijo sube a ocupar su lugar.
Dos: no se puede quitar sin dejar dos ramas sueltas. Se reemplaza su valor por el de su sucesor, el menor de su subárbol derecho, y se borra el sucesor, que tiene a lo más un hijo.

El sucesor sirve porque es mayor que todo lo de la izquierda y menor que todo lo demás de la derecha: la regla sigue en pie.

leccion.js

1class Nodo {
2  constructor(valor) {
3    this.valor = valor;
4    this.izq = null;
5    this.der = null;
6  }
7}
8
9function insertar(raiz, valor) {
10  if (raiz === null) return new Nodo(valor);
11  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
12  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
13  return raiz;
14}
15
16function armar(valores) {
17  let raiz = null;
18  for (const v of valores) raiz = insertar(raiz, v);
19  return raiz;
20}
21
22function inorden(nodo, salida = []) {
23  if (nodo === null) return salida;
24  inorden(nodo.izq, salida);
25  salida.push(nodo.valor);
26  inorden(nodo.der, salida);
27  return salida;
28}
29
30function borrar(nodo, valor) {
31  if (nodo === null) return null;
32  if (valor < nodo.valor) nodo.izq = borrar(nodo.izq, valor);
33  else if (valor > nodo.valor) nodo.der = borrar(nodo.der, valor);
34  else {
35    if (nodo.izq === null) return nodo.der;   // hoja o sólo hijo derecho
36    if (nodo.der === null) return nodo.izq;   // sólo hijo izquierdo
37    let sucesor = nodo.der;                   // dos hijos
38    while (sucesor.izq !== null) sucesor = sucesor.izq;
39    nodo.valor = sucesor.valor;
40    nodo.der = borrar(nodo.der, sucesor.valor);
41  }
42  return nodo;
43}
44
45let raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
46raiz = borrar(raiz, 3);    // dos hijos: su sucesor es el 4
47console.log(inorden(raiz), raiz.izq.valor);
48raiz = borrar(raiz, 1);    // hoja
49console.log(inorden(raiz));
50raiz = borrar(raiz, 10);   // un hijo (el 14)
51console.log(inorden(raiz), raiz.der.valor);

class Nodo {
  constructor(valor) {
    this.valor = valor;
    this.izq = null;
    this.der = null;
  }
}

function insertar(raiz, valor) {
  if (raiz === null) return new Nodo(valor);
  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
  return raiz;
}

function armar(valores) {
  let raiz = null;
  for (const v of valores) raiz = insertar(raiz, v);
  return raiz;
}

function inorden(nodo, salida = []) {
  if (nodo === null) return salida;
  inorden(nodo.izq, salida);
  salida.push(nodo.valor);
  inorden(nodo.der, salida);
  return salida;
}

function borrar(nodo, valor) {
  if (nodo === null) return null;
  if (valor < nodo.valor) nodo.izq = borrar(nodo.izq, valor);
  else if (valor > nodo.valor) nodo.der = borrar(nodo.der, valor);
  else {
    if (nodo.izq === null) return nodo.der;   // hoja o sólo hijo derecho
    if (nodo.der === null) return nodo.izq;   // sólo hijo izquierdo
    let sucesor = nodo.der;                   // dos hijos
    while (sucesor.izq !== null) sucesor = sucesor.izq;
    nodo.valor = sucesor.valor;
    nodo.der = borrar(nodo.der, sucesor.valor);
  }
  return nodo;
}

let raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
raiz = borrar(raiz, 3);    // dos hijos: su sucesor es el 4
console.log(inorden(raiz), raiz.izq.valor);
raiz = borrar(raiz, 1);    // hoja
console.log(inorden(raiz));
raiz = borrar(raiz, 10);   // un hijo (el 14)
console.log(inorden(raiz), raiz.der.valor);

$ node leccion.js

Pulsa CORRER (o Ctrl+Enter).

Qué mirar

Al borrar el 3, su lugar lo ocupa el 4, su sucesor (lo resaltado en el dibujo): el hijo izquierdo del 8 ahora es 4.
El 1 era una hoja y se fue sin más; al borrar el 10, el 14 subió a ser el hijo derecho del 8.
Tras cada borrado el recorrido en orden sigue ordenado: el árbol sigue siendo BST.

Toda la lección en una página

Borrar: tres casos

Primero se busca el nodo, como siempre. Luego depende de cuántos hijos tenga:

Ninguno (una hoja): se quita y ya.
Uno: su hijo sube a ocupar su lugar.
Dos: no se puede quitar sin dejar dos ramas sueltas. Se reemplaza su valor por el de su sucesor, el menor de su subárbol derecho, y se borra el sucesor, que tiene a lo más un hijo.

El sucesor sirve porque es mayor que todo lo de la izquierda y menor que todo lo demás de la derecha: la regla sigue en pie.

1class Nodo {
2  constructor(valor) {
3    this.valor = valor;
4    this.izq = null;
5    this.der = null;
6  }
7}
8
9function insertar(raiz, valor) {
10  if (raiz === null) return new Nodo(valor);
11  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
12  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
13  return raiz;
14}
15
16function armar(valores) {
17  let raiz = null;
18  for (const v of valores) raiz = insertar(raiz, v);
19  return raiz;
20}
21
22function inorden(nodo, salida = []) {
23  if (nodo === null) return salida;
24  inorden(nodo.izq, salida);
25  salida.push(nodo.valor);
26  inorden(nodo.der, salida);
27  return salida;
28}
29
30function borrar(nodo, valor) {
31  if (nodo === null) return null;
32  if (valor < nodo.valor) nodo.izq = borrar(nodo.izq, valor);
33  else if (valor > nodo.valor) nodo.der = borrar(nodo.der, valor);
34  else {
35    if (nodo.izq === null) return nodo.der;   // hoja o sólo hijo derecho
36    if (nodo.der === null) return nodo.izq;   // sólo hijo izquierdo
37    let sucesor = nodo.der;                   // dos hijos
38    while (sucesor.izq !== null) sucesor = sucesor.izq;
39    nodo.valor = sucesor.valor;
40    nodo.der = borrar(nodo.der, sucesor.valor);
41  }
42  return nodo;
43}
44
45let raiz = armar([8, 3, 10, 1, 6, 14, 4, 7]);
46raiz = borrar(raiz, 3);    // dos hijos: su sucesor es el 4
47console.log(inorden(raiz), raiz.izq.valor);
48raiz = borrar(raiz, 1);    // hoja
49console.log(inorden(raiz));
50raiz = borrar(raiz, 10);   // un hijo (el 14)
51console.log(inorden(raiz), raiz.der.valor);

Al borrar el 3, su lugar lo ocupa el 4, su sucesor (lo resaltado en el dibujo): el hijo izquierdo del 8 ahora es 4.
El 1 era una hoja y se fue sin más; al borrar el 10, el 14 subió a ser el hijo derecho del 8.
Tras cada borrado el recorrido en orden sigue ordenado: el árbol sigue siendo BST.

Con datos ordenados se vuelve lista

El BST no se acomoda solo. Si insertas 1, 2, 3, 4… en orden, cada número es mayor que todos los anteriores y siempre va a la derecha: sale una vara torcida, que en realidad es una lista enlazada. Su altura es n y buscar vuelve a costar O(n).

Y los datos ordenados no son raros: fechas, folios, ids que van creciendo. Aquí se ven los mismos 15 números insertados en orden y en un orden que reparte bien. La altura (los nodos del camino más largo de la raíz a una hoja) cuenta la diferencia.

1class Nodo {
2  constructor(valor) {
3    this.valor = valor;
4    this.izq = null;
5    this.der = null;
6  }
7}
8
9function insertar(raiz, valor) {
10  if (raiz === null) return new Nodo(valor);
11  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
12  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
13  return raiz;
14}
15
16function armar(valores) {
17  let raiz = null;
18  for (const v of valores) raiz = insertar(raiz, v);
19  return raiz;
20}
21
22function altura(nodo) {
23  if (nodo === null) return 0;
24  return 1 + Math.max(altura(nodo.izq), altura(nodo.der));
25}
26
27const enOrden = [];
28for (let i = 1; i <= 15; i++) enOrden.push(i);
29const repartido = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15];
30
31console.log(altura(armar(enOrden)));
32console.log(altura(armar(repartido)));
33
34const mil = [];
35for (let i = 1; i <= 1000; i++) mil.push(i);
36console.log(altura(armar(mil)));

En orden: altura 15, uno por nivel.
Bien repartido: altura 4, porque 15 = 1 + 2 + 4 + 8 nodos caben en cuatro niveles.
Mil números en orden dan altura 1000: buscar el último es recorrerlos todos. Bien balanceado serían 10.

Rotar para balancear

Los árboles balanceados arreglan esto solos: después de cada inserción o borrado revisan las alturas y, si un lado creció de más, hacen una rotación. Una rotación cambia quién es padre de quién en dos o tres nodos, sin romper la regla del BST, y baja la altura.

El AVL exige que en cada nodo las alturas de sus dos lados difieran a lo más en 1.
El rojinegro es más relajado y rota menos; es el que usan por dentro el TreeMap de Java y el std::map de C++.

JavaScript no trae un árbol balanceado: Map y Set son tablas hash, sin orden por valor. Aquí está la rotación a la izquierda, la pieza básica.

1class Nodo {
2  constructor(valor) {
3    this.valor = valor;
4    this.izq = null;
5    this.der = null;
6  }
7}
8
9function insertar(raiz, valor) {
10  if (raiz === null) return new Nodo(valor);
11  if (valor < raiz.valor) raiz.izq = insertar(raiz.izq, valor);
12  else if (valor > raiz.valor) raiz.der = insertar(raiz.der, valor);
13  return raiz;
14}
15
16function armar(valores) {
17  let raiz = null;
18  for (const v of valores) raiz = insertar(raiz, v);
19  return raiz;
20}
21
22function inorden(nodo, salida = []) {
23  if (nodo === null) return salida;
24  inorden(nodo.izq, salida);
25  salida.push(nodo.valor);
26  inorden(nodo.der, salida);
27  return salida;
28}
29
30function altura(nodo) {
31  if (nodo === null) return 0;
32  return 1 + Math.max(altura(nodo.izq), altura(nodo.der));
33}
34
35// x tiene un hijo derecho y que sube a su lugar; x baja a la izquierda de y
36function rotarIzq(x) {
37  const y = x.der;
38  x.der = y.izq;   // lo que y tenía a la izquierda pasa a ser de x
39  y.izq = x;
40  return y;        // la nueva raíz de este pedazo
41}
42
43let raiz = armar([1, 2, 3]);   // 1 -> 2 -> 3, todo a la derecha
44console.log(raiz.valor, altura(raiz), inorden(raiz));
45raiz = rotarIzq(raiz);
46console.log(raiz.valor, altura(raiz), inorden(raiz));

Antes: raíz 1, altura 3. Después: raíz 2, altura 2, como en el dibujo. El recorrido en orden es el mismo [1, 2, 3]: la rotación no rompe la regla, sólo reacomoda.

Para leer más

Árbol rojo-negro (Wikipedia) ↗