Giải Quyết Bài Toán Cấu Trúc Dữ Liệu Dạng Cây Và Đồ Thị Với Borrow Checker Trong Rust

Trong các ngôn ngữ có Garbage Collector (Java, Python) hay dùng con trỏ thô (C/C++), điều này rất dễ cài đặt. Tuy nhiên, trong Rust, mô hình Ownership quy định chặt chẽ:

• 🛡️ Một giá trị chỉ có một chủ sở hữu duy nhất.
• 🔒 Bạn có thể có nhiều tham chiếu bất biến (&T) HOẶC một tham chiếu khả biến (&mut T), chứ không thể có cả hai cùng lúc.

Khi dựng đồ thị hoặc cây có con trỏ trỏ ngược về nút cha (parent pointer), Borrow Checker sẽ báo lỗi ngay lập tức vì vi phạm các quy tắc an toàn này.

⚡ Giải pháp 1: Kết hợp Smart Pointers (Rc/Arc + RefCell/Mutex) Đây là hướng tiếp cận truyền thống để xây dựng các nút cây có tham chiếu ngược hoặc đồ thị có hướng.

• Rc<T> (hoặc Arc<T> cho đa luồng) giải quyết bài toán nhiều người cùng sở hữu một nút.
• RefCell<T> (hoặc Mutex<T>) cung cấp Interior Mutability, cho phép thay đổi dữ liệu bên trong nút dù đang nắm giữ tham chiếu bất biến.
• Weak<T> phá vỡ vòng lặp tham chiếu (reference cycle), tránh rò rỉ bộ nhớ khi nút con trỏ ngược về nút cha.

use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct Node {
    value: i32,
    // Weak pointer trỏ về cha để tránh vòng lặp tham chiếu gây leak bộ nhớ
    parent: RefCell<Weak<Node>>,
    // Rc pointer sở hữu các con
    children: RefCell<Vec<Rc<Node>>>,
}

fn main() {
    let parent = Rc::new(Node {
        value: 1,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

    let child = Rc::new(Node {
        value: 2,
        parent: RefCell::new(Rc::downgrade(&parent)),
        children: RefCell::new(vec![]),
    });

    // Thêm child vào danh sách con của parent
    parent.children.borrow_mut().push(Rc::clone(&child));

    println!("Giá trị nút cha: {}", parent.value);
    println!("Giá trị nút con: {}", child.value);
}

🛠️ Giải pháp 2: Mô hình Arena Allocation (Sử dụng Index/Vector) Mặc dù dùng Rc<RefCell<T>> giải quyết được bài toán, nó lại tốn chi phí quản lý bộ đếm runtime (runtime overhead) và dễ gây panic nếu dùng borrow_mut() không cẩn thận.

Một hướng tiếp cận chuẩn mực và idiomatic hơn trong Rust là Arena Allocation:

• Lưu trữ tất cả các nút trong một Vec<Node> duy nhất. Vec đóng vai trò là chủ sở hữu duy nhất của toàn bộ bộ nhớ.
• Thay vì dùng con trỏ (Rc hay &Node), các liên kết giữa nút cha-con hay các cạnh trong đồ thị sẽ sử dụng Chỉ số mảng (usize).

struct Node {
    value: i32,
    parent: Option<usize>, // Lưu index của nút cha trong Vector
    children: Vec<usize>,  // Lưu danh sách index của các nút con
}

struct Tree {
    nodes: Vec<Node>, // Vector đóng vai trò là Arena lưu trữ toàn bộ nút
}

impl Tree {
    fn new() -> Self {
        Tree { nodes: Vec::new() }
    }

    fn add_node(&mut self, value: i32, parent: Option<usize>) -> usize {
        let new_index = self.nodes.len();
        let node = Node {
            value,
            parent,
            children: Vec::new(),
        };
        self.nodes.push(node);

        // Nếu có nút cha, thêm index nút mới vào danh sách children của nút cha
        if let Some(p_index) = parent {
            self.nodes[p_index].children.push(new_index);
        }

        new_index
    }
}

fn main() {
    let mut tree = Tree::new();
    let root = tree.add_node(10, None);
    let child1 = tree.add_node(20, Some(root));
    let child2 = tree.add_node(30, Some(root));

    println!("Root ID: {}, Số con: {}", root, tree.nodes[root].children.len());
    println!("Child 1 value: {}", tree.nodes[child1].value);
}

📊 So sánh chi tiết các giải pháp

• 📌 Mô hình bộ nhớ (Memory Model)
• Rc<RefCell<T>> / Weak<T>: Phân tán rải rác trên vùng nhớ Heap.
• Arena Allocation (Vec<usize>): Tập trung liên tục trong một Memory Pool duy nhất.
• 📌 Hiệu năng & Tốc độ thực thi
• Rc<RefCell<T>> / Weak<T>: Chậm hơn do chi phí tra cứu con trỏ (pointer dereferencing) và quản lý bộ đếm runtime.
• Arena Allocation (Vec<usize>): Rất nhanh, tối ưu hóa triệt để bộ nhớ đệm CPU (CPU Cache Locality).
• 📌 Mức độ an toàn (Safety & Panic)
• Rc<RefCell<T>> / Weak<T>: Có nguy cơ bị panic ở runtime nếu vô tình mượn dữ liệu (borrow_mut()) vi phạm quy tắc.
• Arena Allocation (Vec<usize>): An toàn tuyệt đối ở compile-time, hoàn toàn tránh được rủi ro runtime panic của RefCell.
• 📌 Thao tác xóa nút (Node Deletion)
• Rc<RefCell<T>> / Weak<T>: Tự động giải phóng bộ nhớ khi bộ đếm strong_count giảm về 0.
• Arena Allocation (Vec<usize>): Phải tự quản lý việc dọn dẹp index (ví dụ: dùng danh sách slot trống / Free List).

💡 Tổng kết kinh nghiệm thực chiến Khi làm việc với cấu trúc Cây và Đồ thị trong Rust:

1. Nếu làm ứng dụng đơn giản hoặc cần các phần tử tự do giải phóng độc lập: Hãy cân nhắc sử dụng Rc<RefCell<T>> kết hợp Weak<T>.
2. Nếu tối ưu hiệu năng cho hệ thống lớn (Game Engine, Graph Processing, Compiler AST): Hãy ưu tiên sử dụng mô hình Arena Allocation dựa trên Index hoặc các thư viện cộng đồng uy tín như petgraph hay typed-arena.