Red-Black Tree

1. Giới thiệu

Red-Black Tree là một loại cây nhị phân tìm kiếm tự cân bằng, đảm bảo các thao tác cơ bản (chèn, xóa, tìm kiếm) có độ phức tạp O(log n). Mỗi node trong cây được tô màu đỏ hoặc đen theo các quy tắc đặc biệt để duy trì tính cân bằng.

2. Tính chất của Red-Black Tree

Mỗi node có màu đỏ hoặc đen
Node gốc luôn màu đen
Các node NULL (leaf) là màu đen
Node đỏ không thể có con màu đỏ
Mọi đường đi từ gốc đến leaf đều có cùng số node đen

3. Implementation

public class RedBlackTree<T extends Comparable<T>> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        T value;
        Node left, right;
        boolean color;
        int size;

        Node(T value, boolean color, int size) {
            this.value = value;
            this.color = color;
            this.size = size;
        }
    }

    private Node root;

    private boolean isRed(Node node) {
        if (node == null) return false;
        return node.color == RED;
    }

    private int size(Node node) {
        if (node == null) return 0;
        return node.size;
    }

    // Left rotation
    private Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.size = h.size;
        h.size = 1 + size(h.left) + size(h.right);
        return x;
    }

    // Right rotation
    private Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.size = h.size;
        h.size = 1 + size(h.left) + size(h.right);
        return x;
    }

    // Flip colors
    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    // Insert value
    public void insert(T value) {
        root = insert(root, value);
        root.color = BLACK;
    }

    private Node insert(Node h, T value) {
        if (h == null) {
            return new Node(value, RED, 1);
        }

        int cmp = value.compareTo(h.value);
        if (cmp < 0) h.left = insert(h.left, value);
        else if (cmp > 0) h.right = insert(h.right, value);
        else h.value = value;

        // Fix-up any right-leaning links
        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);

        h.size = 1 + size(h.left) + size(h.right);
        return h;
    }

    // Search
    public boolean contains(T value) {
        return contains(root, value);
    }

    private boolean contains(Node node, T value) {
        while (node != null) {
            int cmp = value.compareTo(node.value);
            if (cmp < 0) node = node.left;
            else if (cmp > 0) node = node.right;
            else return true;
        }
        return false;
    }
}

4. Ví dụ sử dụng

public class RedBlackTreeExample {
    public static void main(String[] args) {
        RedBlackTree<Integer> tree = new RedBlackTree<>();

        // Chèn các phần tử
        tree.insert(7);
        tree.insert(3);
        tree.insert(18);
        tree.insert(10);
        tree.insert(22);

        // Kiểm tra sự tồn tại
        System.out.println("Contains 10: " + tree.contains(10)); // true
        System.out.println("Contains 15: " + tree.contains(15)); // false
    }
}

5. Độ phức tạp

Tìm kiếm: O(log n)
Chèn: O(log n)
Xóa: O(log n)
Không gian: O(n)

6. Ứng dụng thực tế

Java TreeMap và TreeSet
Linux kernel's completely fair scheduler
Database indexes
File system implementation
Process scheduling

7. So sánh với các cấu trúc khác

AVL Tree: Red-Black Tree cho phép cân bằng lỏng lẻo hơn
Binary Search Tree: Red-Black Tree luôn cân bằng
B-Tree: Red-Black Tree tối ưu cho bộ nhớ trong
Skip List: Red-Black Tree có độ phức tạp được đảm bảo tốt hơn

8. Bài tập thực hành

Implement thao tác xóa node
Thêm phương thức duyệt cây (inorder, preorder, postorder)
Visualize Red-Black Tree
Implement iterator
Thêm các operation như findMin, findMax, floor, ceiling