Skip List

1. Giới thiệu

Skip List là một cấu trúc dữ liệu cho phép tìm kiếm nhanh như cây nhị phân cân bằng (O(log n)) nhưng dễ implement hơn và có khả năng cập nhật hiệu quả hơn trong nhiều trường hợp.

2. Đặc điểm chính

• Độ phức tạp trung bình: O(log n) cho tìm kiếm, chèn và xóa
• Cấu trúc phân tầng
• Sử dụng xác suất để cân bằng
• Dễ implement và maintain hơn so với cây cân bằng

3. Cấu trúc cơ bản

public class SkipList<T extends Comparable<T>> {
    private static final double PROBABILITY = 0.5;
    private static final int MAX_LEVEL = 16;

    private class Node {
        T value;
        Node[] next;

        @SuppressWarnings("unchecked")
        Node(T value, int level) {
            this.value = value;
            next = new Node[level];
        }
    }

    private Node head;
    private int level;
    private Random random;

    public SkipList() {
        head = new Node(null, MAX_LEVEL);
        level = 1;
        random = new Random();
    }

    private int randomLevel() {
        int lvl = 1;
        while (random.nextDouble() < PROBABILITY && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    public void insert(T value) {
        Node[] update = new Node[MAX_LEVEL];
        Node current = head;

        // Tìm vị trí chèn ở mỗi level
        for (int i = level - 1; i >= 0; i--) {
            while (current.next[i] != null && 
                   current.next[i].value.compareTo(value) < 0) {
                current = current.next[i];
            }
            update[i] = current;
        }

        // Tạo node mới với level ngẫu nhiên
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }

        Node newNode = new Node(value, newLevel);

        // Cập nhật các con trỏ
        for (int i = 0; i < newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    public boolean search(T value) {
        Node current = head;

        for (int i = level - 1; i >= 0; i--) {
            while (current.next[i] != null && 
                   current.next[i].value.compareTo(value) < 0) {
                current = current.next[i];
            }
        }

        current = current.next[0];
        return current != null && current.value.equals(value);
    }

    public void delete(T value) {
        Node[] update = new Node[MAX_LEVEL];
        Node current = head;

        for (int i = level - 1; i >= 0; i--) {
            while (current.next[i] != null && 
                   current.next[i].value.compareTo(value) < 0) {
                current = current.next[i];
            }
            update[i] = current;
        }

        current = current.next[0];

        if (current != null && current.value.equals(value)) {
            for (int i = 0; i < level; i++) {
                if (update[i].next[i] != current) {
                    break;
                }
                update[i].next[i] = current.next[i];
            }

            // Cập nhật level nếu cần
            while (level > 1 && head.next[level - 1] == null) {
                level--;
            }
        }
    }
}

4. Ví dụ sử dụng

public class SkipListExample {
    public static void main(String[] args) {
        SkipList<Integer> list = new SkipList<>();

        // Chèn phần tử
        list.insert(3);
        list.insert(6);
        list.insert(7);
        list.insert(9);
        list.insert(12);

        // Tìm kiếm
        System.out.println("Search 6: " + list.search(6));  // true
        System.out.println("Search 10: " + list.search(10)); // false

        // Xóa
        list.delete(7);
        System.out.println("Search 7 after delete: " + list.search(7)); // false
    }
}

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

1. In-memory database indexes
2. Hệ thống file
3. Cache implementation
4. Peer-to-peer systems
5. Concurrent data structures

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

1. AVL Tree: Skip List dễ implement hơn
2. Red-Black Tree: Skip List có performance tương đương nhưng code đơn giản hơn
3. Linked List: Skip List nhanh hơn nhiều trong tìm kiếm
4. Binary Search Tree: Skip List tự cân bằng tốt hơn

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

1. Implement Skip List với generic type
2. Thêm phương thức in cấu trúc Skip List
3. Tối ưu việc chọn level cho node mới
4. Implement iterator cho Skip List
5. Thêm các operation như findMin, findMax

8. Tài liệu tham khảo

1. Skip Lists: A Probabilistic Alternative to Balanced Trees
2. Wikipedia - Skip List