← Data structures from scratch · Lesson 21/32

Deleting, and why balancing matters

1/8

Deleting: three cases

First you find the node, as usual. Then it depends on how many children it has:

None (a leaf): just remove it.
One: its child moves up to take its place.
Two: you can't remove it without leaving two loose branches. Replace its value with its successor's, the smallest in its right subtree, and delete the successor, which has at most one child.

The successor works because it's bigger than everything on the left and smaller than everything else on the right: the rule still holds.

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;   // leaf or only a right child
36    if (nodo.der === null) return nodo.izq;   // only a left child
37    let sucesor = nodo.der;                   // two children
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);    // two children: its successor is 4
47console.log(inorden(raiz), raiz.izq.valor);
48raiz = borrar(raiz, 1);    // leaf
49console.log(inorden(raiz));
50raiz = borrar(raiz, 10);   // one child (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;   // leaf or only a right child
    if (nodo.der === null) return nodo.izq;   // only a left child
    let sucesor = nodo.der;                   // two children
    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);    // two children: its successor is 4
console.log(inorden(raiz), raiz.izq.valor);
raiz = borrar(raiz, 1);    // leaf
console.log(inorden(raiz));
raiz = borrar(raiz, 10);   // one child (14)
console.log(inorden(raiz), raiz.der.valor);

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

Deleting 3 puts 4 in its place, its successor (highlighted in the drawing): 8's left child is now 4.
1 was a leaf and simply went away; deleting 10 moved 14 up as 8's right child.
After each deletion the in-order walk is still sorted: the tree is still a BST.

The whole lesson on one page

Deleting: three cases

First you find the node, as usual. Then it depends on how many children it has:

None (a leaf): just remove it.
One: its child moves up to take its place.
Two: you can't remove it without leaving two loose branches. Replace its value with its successor's, the smallest in its right subtree, and delete the successor, which has at most one child.

The successor works because it's bigger than everything on the left and smaller than everything else on the right: the rule still holds.

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;   // leaf or only a right child
36    if (nodo.der === null) return nodo.izq;   // only a left child
37    let sucesor = nodo.der;                   // two children
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);    // two children: its successor is 4
47console.log(inorden(raiz), raiz.izq.valor);
48raiz = borrar(raiz, 1);    // leaf
49console.log(inorden(raiz));
50raiz = borrar(raiz, 10);   // one child (14)
51console.log(inorden(raiz), raiz.der.valor);

Deleting 3 puts 4 in its place, its successor (highlighted in the drawing): 8's left child is now 4.
1 was a leaf and simply went away; deleting 10 moved 14 up as 8's right child.
After each deletion the in-order walk is still sorted: the tree is still a BST.

With sorted data it turns into a list

A BST doesn't rearrange itself. If you insert 1, 2, 3, 4… in order, each number is bigger than all before it and always goes right: you get a crooked stick that is really a linked list. Its height is n and searching costs O(n) again.

And sorted data isn't unusual: dates, invoice numbers, ids that keep growing. Here are the same 15 numbers inserted in order and in an order that spreads them well. The height (the nodes on the longest path from the root to a leaf) tells the difference.

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)));

In order: height 15, one per level.
Well spread: height 4, because 15 = 1 + 2 + 4 + 8 nodes fit in four levels.
A thousand numbers in order give height 1000: finding the last one means walking all of them. Well balanced, it would be 10.

Rotating to rebalance

Balanced trees fix this on their own: after each insert or delete they check the heights and, if one side grew too much, they do a rotation. A rotation changes who is whose parent among two or three nodes, without breaking the BST rule, and lowers the height.

AVL requires that at every node the heights of its two sides differ by at most 1.
Red-black is more relaxed and rotates less; it's what Java's TreeMap and C++'s std::map use inside.

JavaScript doesn't ship a balanced tree: Map and Set are hash tables, with no ordering by value. Here's the left rotation, the basic building block.

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 has a right child y that moves up to its place; x goes down to y's left
36function rotarIzq(x) {
37  const y = x.der;
38  x.der = y.izq;   // whatever y had on its left now belongs to x
39  y.izq = x;
40  return y;        // the new root of this piece
41}
42
43let raiz = armar([1, 2, 3]);   // 1 -> 2 -> 3, all to the right
44console.log(raiz.valor, altura(raiz), inorden(raiz));
45raiz = rotarIzq(raiz);
46console.log(raiz.valor, altura(raiz), inorden(raiz));

Before: root 1, height 3. After: root 2, height 2, as in the drawing. The in-order walk is the same [1, 2, 3]: the rotation doesn't break the rule, it just rearranges.

Deleting, and why balancing matters

Deleting: three cases

Deleting: three cases

With sorted data it turns into a list

Rotating to rebalance

Further reading