Introducció als Arbres B

Els arbres B són una estructura de dades autoequilibrada que manté les dades ordenades i permet insercions, eliminacions i cerques en temps logarítmic. Són especialment útils en sistemes de bases de dades i sistemes de fitxers.

Característiques dels Arbres B

Equilibri: Els arbres B estan dissenyats per mantenir-se equilibrats, garantint que totes les fulles estiguin al mateix nivell.
Nodes amb múltiples claus: Cada node pot contenir múltiples claus i fills.
Ordenació: Les claus dins de cada node estan ordenades.
Capacitat de nodes: Cada node té un nombre mínim i màxim de claus, determinat per l'ordre de l'arbre B.

Definicions Clau

Ordre (m): L'ordre d'un arbre B és un paràmetre que determina el nombre màxim de fills que pot tenir un node. Un arbre B d'ordre m té les següents propietats:
- Cada node intern pot tenir com a màxim m fills.
- Cada node intern, excepte l'arrel, té com a mínim ⌈m/2⌉ fills.
- L'arrel té almenys dos fills si no és una fulla.
- Tots els nodes fulla estan al mateix nivell.

Estructura d'un Node en un Arbre B

Un node en un arbre B conté:

Un nombre variable de claus (dins d'un rang determinat).
Un nombre variable de fills (un més que el nombre de claus).

Node:
  - Claus: [k1, k2, ..., kn]
  - Fills: [c0, c1, c2, ..., cn]

Operacions en Arbres B

Inserció

La inserció en un arbre B implica trobar el lloc correcte per la nova clau i inserir-la. Si el node resultant excedeix el nombre màxim de claus, es divideix en dos nodes i la clau mitjana es puja al node pare.

Exemple d'Inserció

Suposem un arbre B d'ordre 3 i volem inserir la clau 10:

Trobar el lloc correcte: Busquem el node fulla on hauria d'anar la clau 10.
Inserir la clau: Inserim la clau 10 en el node fulla.
Divisió si és necessari: Si el node fulla excedeix el nombre màxim de claus, es divideix i la clau mitjana es puja al node pare.

Eliminació

L'eliminació en un arbre B és més complexa que la inserció. Pot implicar la fusió de nodes o el préstec de claus entre nodes veïns per mantenir les propietats de l'arbre B.

Exemple d'Eliminació

Suposem un arbre B d'ordre 3 i volem eliminar la clau 10:

Trobar la clau: Busquem el node que conté la clau 10.
Eliminar la clau: Eliminem la clau 10.
Reequilibrar l'arbre: Si el node resultant té menys claus del mínim permès, es pot necessitar la fusió amb un node veí o el préstec de claus.

Exemple Pràctic

Implementació Bàsica d'un Arbre B en Python

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t  # Mínim grau (t)
        self.leaf = leaf  # Si és fulla
        self.keys = []  # Claus en el node
        self.children = []  # Fills del node

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t, True)
        self.t = t

    def traverse(self):
        self._traverse(self.root)

    def _traverse(self, node):
        for i in range(len(node.keys)):
            if not node.leaf:
                self._traverse(node.children[i])
            print(node.keys[i], end=' ')
        if not node.leaf:
            self._traverse(node.children[len(node.keys)])

    def search(self, k):
        return self._search(self.root, k)

    def _search(self, node, k):
        i = 0
        while i < len(node.keys) and k > node.keys[i]:
            i += 1
        if i < len(node.keys) and k == node.keys[i]:
            return node
        if node.leaf:
            return None
        return self._search(node.children[i], k)

    # Mètodes d'inserció i eliminació s'implementen aquí

# Exemple d'ús
btree = BTree(3)
# Inserir claus i realitzar operacions

Exercicis Pràctics

Inserció en un Arbre B:
- Inseriu les claus [10, 20, 5, 6, 12, 30, 7, 17] en un arbre B d'ordre 3.
- Dibuixeu l'arbre resultant després de cada inserció.
Eliminació en un Arbre B:
- Elimineu les claus [6, 13, 7] d'un arbre B d'ordre 3 que conté les claus [10, 20, 5, 6, 12, 30, 7, 17].
- Dibuixeu l'arbre resultant després de cada eliminació.

Resum

Els arbres B són una estructura de dades eficient per a la gestió de grans quantitats de dades, especialment en sistemes de bases de dades i sistemes de fitxers. La seva capacitat per mantenir-se equilibrats i permetre operacions en temps logarítmic els fa molt útils en aplicacions on l'eficiència és crucial.

Arbres B

Introducció als Arbres B

Característiques dels Arbres B

Definicions Clau

Estructura d'un Node en un Arbre B

Operacions en Arbres B

Inserció

Exemple d'Inserció

Eliminació

Exemple d'Eliminació

Exemple Pràctic

Implementació Bàsica d'un Arbre B en Python

Exercicis Pràctics

Resum

Curs d'Estructures de Dades

Mòdul 1: Introducció a les Estructures de Dades

Mòdul 2: Llistes

Mòdul 3: Piles

Mòdul 4: Cues

Mòdul 5: Arbres

Mòdul 6: Grafs

Mòdul 7: Conclusions i Recursos Addicionals