Introducció

Un arbre binari de cerca (BST, per les seves sigles en anglès) és una estructura de dades que manté els elements en un ordre específic, facilitant operacions com la cerca, inserció i eliminació. En un BST, cada node té com a màxim dos fills, i es compleixen les següents propietats:

Propietat de l'ordre: Per a qualsevol node N:
- Tots els nodes del subarbre esquerre de N tenen valors menors que el valor de N.
- Tots els nodes del subarbre dret de N tenen valors majors que el valor de N.

Propietats dels Arbres Binàries de Cerca

Cerca eficient: La propietat de l'ordre permet cercar elements de manera eficient.
Inserció i eliminació: També es poden fer de manera eficient mantenint la propietat de l'ordre.
Recorreguts: Es poden fer recorreguts en preordre, inordre i postordre per obtenir els elements en diferents ordres.

Operacions Bàsiques

Cerca

La cerca en un BST es fa comparant el valor cercat amb el valor del node actual i decidint si es continua pel subarbre esquerre o dret.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def search(root, key):
    # Base Cases: root is null or key is present at root
    if root is None or root.val == key:
        return root

    # Key is greater than root's key
    if root.val < key:
        return search(root.right, key)

    # Key is smaller than root's key
    return search(root.left, key)

Inserció

Per inserir un nou node, es compara el valor del nou node amb els nodes existents i es col·loca en la posició correcta mantenint la propietat de l'ordre.

def insert(root, key):
    # If the tree is empty, return a new node
    if root is None:
        return Node(key)

    # Otherwise, recur down the tree
    if key < root.val:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)

    # return the (unchanged) node pointer
    return root

Eliminació

L'eliminació d'un node en un BST és més complexa i depèn de si el node a eliminar té zero, un o dos fills.

def deleteNode(root, key):
    # Base Case
    if root is None:
        return root

    # If the key to be deleted is smaller than the root's key
    if key < root.val:
        root.left = deleteNode(root.left, key)

    # If the key to be deleted is greater than the root's key
    elif key > root.val:
        root.right = deleteNode(root.right, key)

    # If key is same as root's key, then this is the node to be deleted
    else:
        # Node with only one child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp
        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # Node with two children: Get the inorder successor
        temp = minValueNode(root.right)

        # Copy the inorder successor's content to this node
        root.val = temp.val

        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.val)

    return root

def minValueNode(node):
    current = node

    # Loop down to find the leftmost leaf
    while(current.left is not None):
        current = current.left

    return current

Recorreguts

Recorregut Inordre

El recorregut inordre visita els nodes en ordre ascendent.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

Recorregut Preordre

El recorregut preordre visita el node actual abans de visitar els seus fills.

def preorder(root):
    if root:
        print(root.val)
        preorder(root.left)
        preorder(root.right)

Recorregut Postordre

El recorregut postordre visita els fills abans de visitar el node actual.

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val)

Exercici Pràctic

Exercici 1: Implementació Bàsica

Implementa un BST en Python i realitza les operacions bàsiques de cerca, inserció i eliminació.

# Implementació completa del BST amb les operacions bàsiques
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

class BST:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert(self.root, key)

    def _insert(self, root, key):
        if key < root.val:
            if root.left is None:
                root.left = Node(key)
            else:
                self._insert(root.left, key)
        else:
            if root.right is None:
                root.right = Node(key)
            else:
                self._insert(root.right, key)

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

    def _search(self, root, key):
        if root is None or root.val == key:
            return root
        if key < root.val:
            return self._search(root.left, key)
        return self._search(root.right, key)

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, root, key):
        if root is None:
            return root
        if key < root.val:
            root.left = self._delete(root.left, key)
        elif key > root.val:
            root.right = self._delete(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            temp = self._minValueNode(root.right)
            root.val = temp.val
            root.right = self._delete(root.right, temp.val)
        return root

    def _minValueNode(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, root):
        if root:
            self._inorder(root.left)
            print(root.val, end=' ')
            self._inorder(root.right)

# Exemple d'ús
bst = BST()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("Inorder traversal of the given tree")
bst.inorder()

print("\n\nDelete 20")
bst.delete(20)
print("Inorder traversal of the modified tree")
bst.inorder()

print("\n\nDelete 30")
bst.delete(30)
print("Inorder traversal of the modified tree")
bst.inorder()

print("\n\nDelete 50")
bst.delete(50)
print("Inorder traversal of the modified tree")
bst.inorder()

Conclusió

Els arbres binaris de cerca són una estructura de dades fonamental que permeten operacions eficients de cerca, inserció i eliminació. Comprendre com implementar i utilitzar BSTs és essencial per a qualsevol programador que treballi amb dades estructurades. En el següent mòdul, explorarem arbres AVL, una variant dels BSTs que manté l'equilibri per assegurar una eficiència òptima.

Arbres Binàries de Cerca

Introducció

Propietats dels Arbres Binàries de Cerca

Operacions Bàsiques

Cerca

Inserció

Eliminació

Recorreguts

Recorregut Inordre

Recorregut Preordre

Recorregut Postordre

Exercici Pràctic

Exercici 1: Implementació Bàsica

Conclusió

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