Skip List

Mô tả

Skip list là cấu trúc dữ liệu do W.Pugh phát minh năm 1989 cho phép thêm, xoá và tìm kiếm nhanh trong một danh sách liên kết có trật tự (sorted linked list) với độ phức tạp mong đợi là O(log n).

Tại sao phải dùng skip list?

Như các bạn đã biết thời gian tìm kiếm trong một danh sách liên kết đã được sắp xếp trong trường hợp xấu nhất là O(n) bởi vì tính chất của linked list là chúng ta chỉ có thể lấy được element thông qua con trỏ của phần tử trước nó (pointer).

Vậy làm sao để ta có thể rút ngắn thời gian tìm kiếm mong đợi xuống còn O (log n)? Skip list ra đời để sẽ giải quyết vấn đề này.

Cách skip list làm việc

Rất đơn giản. Chúng ta tạo ra nhiều layer từ danh sách liên kết gốc bằng cách loại bỏ bớt một số node từ danh sách gốc.

Ở ví dụ trong ảnh ta có linked list với 16 node và 2 layer. Layer bên dưới sẽ làm việc như là một "normal lane (đường bình thường)" có nghĩa là nó sẽ liên kết toàn bộ node với nhau, còn layer phía trên sẽ hoạt động như là "express lane (đường cao tốc)" nó chỉ liên kết một số node quan trọng và các node này có liên kết với các node có giá trị tương ứng của layer bên dưới.

Bây giờ giả sử ta muốn tìm node có gía trị 50, chúng ta bắt đầu tại node đầu tiên của "express lane" cứ tiếp tục trỏ đến node tiếp theo cho đến khi node tiếp theo có giá trị lớn hơn 50, ở đây ta dừng lại ở node 30 vì node tiếp theo là 57, sau đó ta trỏ đến node 30 của normal lane nhờ vào liên kết đã tạo và tiếp tục tìm kiếm trên normal lane cho đến khi tìm thấy node có giá trị 50. Như vậy ta đã bỏ duyệt qua một số node như 20, 22, 23, 27, nó tiết kiệm thời gian phải không nào. Thêm mới node và xoá node cũng tương tự.

Tổng kết

  • Skip list là một cấu trúc dữ liệu cho phép thực thi việc thêm, xoá, tìm kiếm nhanh các node trong một danh sách liên kết có trật tự với thời gian mong đợi là O(log n).
  • Thời gian thực thi của skip list sẽ được giảm đi nếu như ta thêm nhiều layer.

Nguồn tham khảo

http://r.grokking.org/forum-wikipedia-skip-list
http://r.grokking.org/forum-youtube-skip-list