Skip List – Đối thủ của cây cân bằng

Mấy bữa nay khoái cái thằng Skip List này quá, hehe…

Sắp xếptìm kiếm, đó là hai công việc mà máy tính thường xuyên phải làm nhất! Vậy nên người ta đã bỏ công sức rất nhiều để nghiên cứu các thuật toán về chúng. Và đương nhiên, đi kèm với những thuật toán đó là cấu trúc dữ liệu.

Đầu tiên chúng ta bàn về cấu trúc mảng, mảng tự hào khoe ưu điểm: “cho tao một chỉ số, tao sẽ trả về giá trị cho mày cái bụp”. Ưu điểm đó giúp chúng ta tìm kiếm nhị phân trên một mảng sắp sẵn rất tốt bởi câu hỏi “phần tử chính giữa bằng bao nhiêu?” được trả lời cực nhanh. Nhưng dữ liệu luôn thay đổi, đòi hỏi phải chèn, xóa liên tục, mảng dĩ nhiên là yếu kém đối với những thao tác này.

Sử dụng con trỏ một cách linh hoạt, người ta tạo ra danh sách liên kết (DSLK). Mỗi một phần tử trong danh sách này không chỉ đơn thuần chứa dữ liệu về nó, mà còn chứa địa chỉ của một hoặc nhiều các phần tử khác, tương ứng ta có DSLK đơn, kép, đa. Ưu điểm của DSLK là có thể cấp phát động; chèn, xoá rất nhanh; nhưng truy xuất phần tử ngẫu nhiên thì lại chậm.

Nhận thấy danh sách liên kết dùng để biểu diễn cây khá phù hợp, người ta tiếp tục áp đặt sự chỉ trỏ của các phần tử sao cho chúng tạo thành mô hình cây (thực ra cây là một khái niệm ra đời trước đó rất lâu, nhưng thuộc lý thuyết đồ thị, một nhánh của toán rời rạc).

Không thể phủ nhận cây là cấu trúc quan trọng bậc nhất trong tin học, có rất nhiều các loại cây và thuật toán về cây. Cho dù thế nào thì tất cả đều nhằm một mục đích tối thượng: tìm kiếm sao cho nhanh!

Cây đơn giản nhất là cây nhị phân tìm kiếm, có điều trong trường hợp xấu nhất (các phần tử được thêm vào cây theo thứ tự đã sắp sẵn) thì cây này rất dở. Để hạn chế sự rủi ro ấy, người ta áp đặt tính cân bằng lên các cây, kết quả cho ra cây 2-3-4 từ trên xuống, cây đỏ đen, cây AVL, … và phải trả giá đắt cho sự cài đặt cho các thao tác chèn, xóa để luôn đảm bảo tính cân bằng đó.

Ngẫm nghĩ mà xem, tựu chung lại, tư tưởng chính để giải quyết bài toán tìm kiếm trên một dãy đã sắp sẵn – có quyền sắp sẵn vì mỗi khi chèn thêm một phần tử mới ta sẽ chèn sao cho dãy vẫn được sắp sẵn – là:

Phải có một cách gì đó cực nhanh để phân chia dãy đó thành các đoạn. Duyệt các đoạn từ trái qua phải để tìm ra đoạn chứa phần tử cần tìm. Kế đó đi sâu hơn vào đoạn này, lại chia nhỏ đoạn này ra, cứ thế… (*)

Các thuật toán thì chỉ khác nhau ở chỗ: khi chia đoạn thì chia làm mấy đoạn, các đoạn có đều nhau không? Đối với cây nhị phân tìm kiếm thì số đoạn được chia ở mỗi lần chia luôn là 2 đoạn, nhưng 2 đoạn ấy rất có thể không đều nhau, điển hình là khi thứ tự các phần tử thêm vào là sắp sẵn.

Tác giả của Skip List coi danh sách ban đầu vẫn là một DSLK thuần túy, chứ không nhìn vấn đề dưới khía cạnh cây. Ông có cái nhìn khá độc đáo: DSLK có nhiều tầng (level), mỗi một tầng đại diện cho một cách chia đoạn, tầng càng cao thì số đoạn càng ít. Có thể nói ông đã bám khá sát tư tưởng (*).

Nhìn vào cài đặt (rất đơn giản, dễ hiểu) của Skip List, ta thấy sự chia đoạn là ngẫu nhiên nhưng theo quy tắc, mấu chốt vấn đề này là ở hàm phát sinh ngẫu nhiên số tầng của một phần tử mới. Chỉ cần biết một chút về lý thuyết xác suất ta nhận ra số đoạn ở tầng k+1 thường sẽ bằng 25% (hoặc 50%, tùy, theo kinh nghiệm thì 25% là tốt) số đoạn ở tầng k.

Không những về cài đặt, về tốc độ trung bình thực thi chương trình, Skip List có thể cũng ăn đứt cây cân bằng.

Whatever you might want to do using Balanced Trees, you can do it faster and more simply using Skip Lists.

–William Pugh

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s