Skip list là gì và nó đạt được tìm kiếm O(log n) như thế nào?

Question

Accepted Answer

**Skip list** là một linked list có thứ tự được bổ sung nhiều tầng **"làn tốc hành (express lane)"**. Các tầng cao hơn nhảy qua nhiều node, nên việc tìm kiếm đi xuống và di chuyển sang phải, đạt được **thời gian kỳ vọng O(log n)** — như một thay thế xác suất, đơn giản hơn cho một balanced tree. ## Cấu trúc ```text L3: head ------------------------> 30 -------> NIL L2: head ----------> 17 ---------> 30 -------> NIL L1: head ----> 9 --> 17 --> 25 --> 30 --> 42 -> NIL L0: head -> 3->9->12->17->25->30->39->42 ----> NIL (list đầy đủ) ``` Mỗi node được thăng cấp lên tầng cao hơn với xác suất `p` (thường 0.5), nên trung bình mỗi tầng có một nửa số node so với tầng bên dưới. ## Tìm kiếm ```text search(25): bắt đầu trên-cùng-bên-trái, di chuyển SANG PHẢI khi next <= target, nếu không thì XUỐNG một tầng. Lặp lại tới tầng 0. ``` ```python import random def random_level(p=0.5, max_level=16): lvl = 1 while random.random() < p and lvl < max_level: lvl += 1 # tung đồng xu quyết định chiều cao của một node return lvl ``` ## Độ phức tạp | Thao tác | Kỳ vọng | Không gian | |---|---|---| | search | O(log n) | O(n) | | insert / delete | O(log n) | — | ## Đánh đổi so với balanced tree - **Điểm mạnh:** đơn giản hơn nhiều để hiện thực so với red-black/AVL; không có phép xoay; dễ làm phiên bản đồng thời (concurrent) (dùng trong Redis sorted set, Java `ConcurrentSkipListMap`). - **Điểm yếu:** đảm bảo xác suất (không phải trường hợp tệ nhất); thêm pointer mỗi node. ## Tại sao điều này quan trọng Skip list cung cấp các thao tác có thứ tự O(log n) giống tree với ít code hơn nhiều và đồng thời lock-free dễ dàng, đó là lý do các hệ thống thực tế như Redis chọn chúng. Chúng là một ví dụ tuyệt vời về việc dùng **ngẫu nhiên hóa (randomization)** để thay thế logic cân bằng tất định phức tạp.