Di ricerca

Un albero si dice binario di ricerca se $k = 2$ e soddisfa la proprietà di ricerca:

Ogni y nel sottoalbero sinistro di x ha y.info <= x.info e ogni y nel destro y.info >= x.info

che genera una stampa in ordine crescente con la visita in-order.

Operazioni

Dato che la maggior parte delle operazioni sono $O (h)$ dove $h$ è l'altezza, mantenere l'albero bilanciato permette di ottenere al meglio $T (n) = O (lo g n)$ invece che $O (n)$ nel caso peggiore.

Ricerca

search(Node x, Elem k) -> Node | NIL
  if x == NIL or x.info == k
    return x
  else
    if x.info > k
      return tree_search(x.left, k)
    else
      return tree_search(x.right, k)

oppure iterativamente:

search(Node x, Elem k) -> Node | NIL
  while x != NIL and x.info != k
    if k < x.info
      x = x.left
    else
      x = x.right
  return x

con $T (n) = O (h)$ perchè nel caso peggiore fa il cammino più lungo dell'albero, cioè l'altezza $h$ .

Massimo e minimo

maximum(Node x) -> Node
  while x.right != NIL
    x = x.right
  return x

minimum(Node x) -> Node
  while x.left != NIL
    x = x.left
  return x

anche in questo caso entrambi con $T (n) = O (h)$ .

Successore o predecessore

Il successore del nodo x in un albero di ricerca sarà il minimo del sottoalbero destro se ne possiede uno, altrimenti sarà l'antenato di x che lo contiene nel suo sottoalbero sinistro:
```
successor(Node x)
  if x.right != NIL
    return minimum(x.right)
  else
    y = x.parent
    while y != NIL and y.right == x
      x = y
      y = y.parent
    return y
```
con $T (n) = O (h)$ perchè sia minimum che il cammino per la radice sono al più $O (h)$ .

Il predecessore invece, è la versione specchiata del successore:
```
predecessor(Node x)
  if x.left != NIL
    return maximum(x.left)
  else
    y = x.parent
    while y != NIL and y.left == x
      x = y
      y = y.parent
    return y
```
sempre con $T (n) = O (h)$ .

Inserimento

insert(Tree T, Node z)
  y = NIL
  x = T.root
  while x != NIL  // Al più h volte
    y = x
    if z.info < x.info
      x = x.left
    else
      x = x.right
  z.parent = y
  if y == NIL   // Anche T.root è NIL
    T.root = z
  else
    if z.info < y.info
      y.left = z
    else
      y.right = z

con $T (n) = O (h)$ .

Cancellazione

Si può dimostrare che il successore di un nodo $x$ non ha figlio sinistro, dato che nella visita in-order precedono i nodi del sottoalbero sinistro di $x$ , poi $x$ e poi i nodi del sottoalbero destro.

Per assurdo se $s$ , i.e. il successore di $x$ , avesse un figlio sinistro $y$ , nella visita si avrebbe che $x ⇝ y ⇝ s$ che è una contraddizione dato che allora sarebbe $y$ il successore di $x$ e non $s$ .

Questo permetterà di formare un algoritmo corretto per la cancellazione, che richiederà però:

transplant(Tree T, Node u, Node v)  // Rimpiazza u con v
  if u.parent == NIL
    T.root = v
  else
    if u.parent.left == u
      u.parent.left = v
    else
      u.parent.right = v

  if v != NIL
    v.parent = u.parent

con $T (n) = Θ (1)$ , con cui si ottiene:

delete(Tree T, Node z)
  if z.left == NIL
    transplant(T, z, z.right)  // Rimpiazza z con z.right dato che z.left è vuoto
  else if z.right == NIL
    transplant(T, z, z.left)
  else

    // Trova il successore in tempo O(h) per metterlo al posto di z
    y = minimum(z.right)

    // Se z non è il padre di y si rimpiazza y con y.right così che z.right
    // sia di ricerca e si possa spostare y al posto di z
    if y.parent != z
      transplant(T, y, y.right)
      y.right = z.right
      z.right.parent = y

    // Si sostituisce z con y anche se z è padre di y perchè essendo successore
    // y non ha y.left e quindi come figli di y si mettono z.left e z.right
    transplant(T, z, y)
    y.left = z.left
    z.left.parent = y

che avrà complessità $T (n) = O (h)$ per via di minimum.

Costruzione

build(Array A) -> Tree
  Tree T = {root = NIL}
  for i = 1 to A.length  // n volte
    Node u = {key = A[i], left = NIL, right = NIL}
    insert(T, u)  // O(h) con h = i nel caso peggiore in cui A è ordinato
  return T

con $T (n) = i = 1 \sum n O (i) = O (i = 1 \sum n i) = O (\frac{n ( n + 1 )}{2}) = O (n^{2})$ .

Se sappiamo però che A è dato ordinato, allora si può ottimizzare:

build_ord(Array A) -> Tree
  Tree T = {root = build_ord_aux(A, 1, A.length, NIL)}
  return T

build_ord_aux(Array A, int inf, int sup, Node parent) -> Node
  if inf > sup
    return NIL
  else
    med = floor((inf + sup)/2)
    Node r = {key = A[med], parent = parent}
    r.left = build_ord_aux(A, inf, med-1, r)
    r.right = build_ord_aux(A, med+1, sup, r)
    return r

con $T (n) = Θ (n)$ perchè $T (n) = 2 T (\frac{n}{2}) + d$ se $n > 0$ per il teorema master.

Esempi

Restituire il numero massimo di ripetizioni in un albero binario di ricerca in $Θ (n)$ .

int massimo_ripetizioni(Tree t) {
  if (t.root == nullptr) {
    return 0;
  }

  int max = 1, count = 1;
  PNode iter = minimum(t.root);  // O(h)
  int value = iter->key;
  iter = successor(iter);
  while (iter != nullptr) {
    if (iter->key == value) {
      count++;
    } else {
      if (count > max) {
        max = count;
      }
      count = 1;
      value = iter->key;
    }
    iter = successor(iter);  // O(h)
  }

  if (count > max) {
    max = count;
  }
  return max;
}

con $T (n) = Θ (n)$ perchè chiamando minimum e poi $n$ volte successor si ha una visita in-order.

Verificare che un albero sia di ricerca.

bool is_bst(PNode r) {
  if (r == nullptr) {
    return true;
  }
  int min, max;
  return is_bst_aux(r, min, max);
}

bool is_bst_aux(PNode u, int& min, int& max) {
  int min_sx, min_dx, max_sx, max_dx;
  bool is_sx, is_dx;
  if (u->left == nullptr) {
    is_sx = true;
    min_sx = max_sx = u->key;
  } else {
    is_sx = is_bst_aux(u->left, min_sx, max_sx);
  }
  if (u->right == nullptr) {
    is_dx = true;
    min_dx = max_dx = u->key;
  } else {
    is_dx = is_bst_aux(u->right, min_dx, max_dx);
  }

  min = min_sx;
  max = max_dx;
  return is_sx && is_dx && max_sx <= u->key && min_dx >= u->key;
}

con $T (n) = Θ (n)$ per la decomposizione.

Verificare che dato un albero $T$ binario di ricerca $\forall k, k \in T \land k + 2 \in T \Rightarrow k + 1 \in T$ .

bool check(Tree t) {
  if (t.root == nullptr) {
    return true;
  }

  PNode iter = minimum(t.root), succ;
  bool valid = true;
  while (iter != nullptr && valid) {
    succ = successor(iter);
    if (succ != nullptr && succ->key >= iter->key+2) {
      valid = false;
    } else {
      iter = succ;
    }
  }
  return valid;
}

con $T (n) = O (n)$ dato che la visita in-order può terminare in anticipo se l'albero non è valido.

Computer Science

Di ricerca

Operazioni

Esempi