Algoritmos y estructuras de datos en Rust: guía práctica

Introducción: ¿por qué Rust para algoritmos?

Rust es un lenguaje de programación de sistemas moderno que combina el alto rendimiento de C/C++ con la seguridad de memoria. Para el estudio de algoritmos y estructuras de datos, Rust es especialmente bueno porque:

• Control de propiedad (ownership) obliga a pensar explícitamente en la gestión de memoria
• Seguridad — el compilador no permite muchos errores en tiempo de ejecución
• Velocidad — Rust se compila a código máquina, lo cual es importante para algoritmos de alto rendimiento

En este artículo analizaremos la implementación de cuatro estructuras y algoritmos básicos en Rust con ejemplos prácticos de código.

1. Lista enlazada (Linked List)

Una de las estructuras de datos clásicas. En Rust, su implementación requiere el uso de Box para asignar memoria en el heap y Option para representar la ausencia de un nodo.

Implementación de una lista simplemente enlazada

// Definimos el nodo de la lista#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

// La lista en sí#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,}

impl<T> LinkedList<T> {    // Creamos una lista vacía    fn new() -> Self {        LinkedList { head: None }    }

    // Agregamos un elemento al inicio    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);    }

    // Eliminamos un elemento del inicio    fn pop_front(&mut self) -> Option<T> {        self.head.take().map(|node| {            self.head = node.next;            node.value        })    }}

fn main() {    let mut list = LinkedList::new();    list.push_front(10);    list.push_front(20);    list.push_front(30);    println!("{:?}", list); // LinkedList { head: Some(Node { value: 30, next: ... }) }        let popped = list.pop_front();    println!("Eliminado: {:?}", popped); // Eliminado: Some(30)    println!("Ahora la lista: {:?}", list);}

¿Qué sucede aquí?

• Box<Node> — puntero a un nodo en el heap
• Option — o hay un nodo (Some) o no (None)
• take() — toma el valor de Option, dejando None

2. Árbol binario de búsqueda (Binary Search Tree)

Un árbol es una estructura jerárquica. En un árbol binario de búsqueda, cada nodo tiene un hijo izquierdo y uno derecho, donde el izquierdo es menor que la raíz y el derecho es mayor.

Implementación de BST

use std::cmp::Ordering;

#[derive(Debug)]struct TreeNode<T> {    value: T,    left: Option<Box<TreeNode<T>>>,    right: Option<Box<TreeNode<T>>>,}

#[derive(Debug)]struct BinarySearchTree<T> {    root: Option<Box<TreeNode<T>>>,}

impl<T: Ord> BinarySearchTree<T> {    fn new() -> Self {        BinarySearchTree { root: None }    }

    // Inserción de un elemento    fn insert(&mut self, value: T) {        let mut current = &mut self.root;        while let Some(node) = current {            match value.cmp(&node.value) {                Ordering::Less => current = &mut node.left,                Ordering::Greater => current = &mut node.right,                Ordering::Equal => return, // ignoramos duplicados            }        }        *current = Some(Box::new(TreeNode {            value,            left: None,            right: None,        }));    }

    // Búsqueda de un elemento    fn contains(&self, value: &T) -> bool {        let mut current = &self.root;        while let