Giới thiệu
Qua các lượt bài trước, chúng ta đã thảo luận về thuật toán tìm kiếm nhị phân và ngăn (partition). Cả hai thuật toán này đều dựa trên cấu trúc dữ liệu mảng (array) vốn rất quen thuộc với chúng ta.
Ngoài ra, hai thuật toán trên được xếp vào nhóm thuật toán tất định (determistic algorithm). Các thuật toán thuộc nhóm này thỏa mãn hai điều kiện:
- Luôn trả về kết quả giống nhau nếu được cung cấp cùng một dữ liệu đầu vào.
- Các trạng thái (state) trong quá trình tính toán phải giống nhau với cùng một dữ liệu đầu vào.
Trong bài viết này tác giả đề cập đến cấu trúc dữ liệu "Danh Sách Nhảy Cóc" (Skip List), cơ chế hoạt động của cấu trúc dữ liệu này (bao gồm các thao tác Thêm, Xóa, Tìm Kiếm) phụ thuộc vào yếu tố ngẫu nhiên vì vậy nó được xếp vào nhóm thuật toán ngẫu tính (randomized algorithm), trái ngược với nhóm thuật toán tất định.
Mục đích
Một cấu trúc dữ liệu đơn giản nhưng hiệu quả trên các tác vụ cơ bản: Thêm, Xóa và Tìm Kiếm.
Định nghĩa
Danh sách nhảy cóc S là một tập hợp các danh sách S[0], S[1] ... S[N-1]. Để dễ hình dung chúng ta xem mỗi danh sách con tương ứng với một "tầng", trong đó 0 là tầng thấp nhất, cho đến N-1 là tầng cao nhất. Danh sách nhảy cóc luôn thỏa mãn các điều kiện:
- Mỗi danh sách con chứa các giá trị theo thứ tự tăng dần.
- Phần từ đầu và cuối mỗi danh sách con đều là NULL.
- Danh sách ở tầng cao hơn là dãy con của danh sách tầng dưới.
Ví dụ một trạng thái của danh sách nhảy cóc chứa dãy số 12, 23, 34, 46, 64, 78, 89:
S[3] NULL 23 NULL S[2] NULL 23 64 NULL S[1] NULL 23 34 64 78 NULL S[0] NULL 12 23 34 46 64 78 89 NULL
Tìm kiếm trong danh sách
Gọi K là giá trị cần tìm kiếm. Ý tưởng chính của thuật toán là cố gắng duyệt càng xa càng tốt trên tầng cao hơn và tiếp tục ở tầng thấp hơn cho đến khi không thể duyệt được nữa.
Thuật toán bắt đầu từ phần tử đầu tiên, tầng trên cùng của danh sách. Duyệt theo quy luật:
- Nhảy sang phần tử kế tiếp trên cùng tầng nếu phần tử tiếp theo đó khác NULL và bé hơn hoặc bằng K.
- Nếu không thể di chuyển trên cùng tầng được nữa:
- Dừng duyệt nếu như đang ở tầng thấp nhất.
- Ngược lại, nhảy xuống phần tử ngay bên dưới ở tầng tiếp theo.
Sau khi kết thúc duyệt danh sách, nếu phần tử hiện tại bằng K, thuật toán kết luận tìm được K, ngược lại K không tồn tại trong danh sách.
Ví dụ dưới đây minh họa việc tìm kiếm K = 85 trong danh sách S tại trạng thái được mô tả ở phần trước:
S[3] NULL -------> 23 NULL S[2] NULL 23 -----------> 64 NULL S[1] NULL 23 34 64 -> 78 -> 83 NULL S[0] NULL 12 23 34 46 64 78 83 90 NULL
Giải thích
| Bước | Tầng hiện tại | Phần tử hiện tại | Phần tử kế tiếp | Di chuyển |
|---|---|---|---|---|
| 1 | S[3] | NULL | 23 | Nhảy sang phần tử kế tiếp vì 23 <= K |
| 2 | S[3] | 23 | NULL | Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL |
| 3 | S[2] | 23 | 64 | Nhảy sang phần tử kế tiếp vì 64 <= K |
| 4 | S[2] | 64 | NULL | Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL |
| 5 | S[1] | 64 | 78 | Nhảy sang phần tử kế tiếp vì 78 <= K |
| 6 | S[1] | 78 | 83 | Nhảy sang phần tử kế tiếp vì 83 <= K |
| 7 | S[1] | 83 | NULL | Nhảy xuống tầng dưới vì phần tử kế tiếp bằng NULL |
| 8 | S[0] | 83 | 90 | Dừng thuật toán vì 90 > K |
Dựa vào giá trị của phần tử cuối cùng, chúng ta kết luận không tìm thấy giá trị 85 trong danh sách. Mặt khác, nếu chúng ta tìm K = 83, các bước duyệt trên danh sách sẽ giống hệt như vậy ngoại trừ việc thuật toán sẽ kết thúc ở bước thứ 7 và chúng ta tìm được K.
Để ý các bước duyệt, chúng ta thấy thuật toán đã nhảy cóc qua các phần tử 12, 34 và 46.
Thêm phần tử vào danh sách
Gọi H là giá trị của phần tử cần thêm vào danh sách S. Thuật toán được mô tả như sau:
- Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2], ..., p[1], p[0] tương ứng với tầng N-1, N-2, ..., 1, 0.
- Nếu H đã tồn tại trong danh sách S, kết thúc thuật toán.
- Thêm phần tử giá trị H vào sau p[0].
- Tung một đồng xu
- Nếu được mặt ngửa, di chuyển lên tầng trên và thêm phần tử giá trị H vào sau vị trí tương ứng ở tầng này. (p[1] nếu là tầng 1, p[2] nếu là tầng 2, ...).
- Nếu được mặt xấp, dừng thuật toán.
- Quay lại bước 4.
Lưu ý tại bước 4, thuật toán phải tạo tầng mới nếu đồng xu hiện mặt ngửa và chúng ta đang ở tầng trên cùng.
Xóa phần tử khỏi danh sách
Gọi H là giá trị của phần tử cần phải xóa khỏi danh sách S. Thuật toán khá tương tự với việc thêm phần tử:
- Thực hiện việc tìm kiếm H trong S và lưu lại các vị trí cuối cùng trên mỗi tầng trong khi duyệt: p[N-1], p[N-2], ..., p[1], p[0].
- Nếu không tìm thấy H, thuật toán kết thúc.
- Ngược lại, xóa tất cả các phần tử tại vị trí p[N-1], p[N-2], ..., p[1], p[0] khỏi danh sách.
- Xóa tất cả các tầng trống (tầng chỉ có hai phần tử NULL ở đầu và cuối).
Cài đặt
Chúng ta định nghĩa một phần tử của danh sách nhảy cóc như sau:
class SkipListNode(object):
def __init__(self, value):
self.value = value
self.next = None
self.down = None
Như các bạn thấy, với mỗi phần tử ngoài giá trị cần lưu, chúng ta chỉ quan tâm đến phần tử kế tiếp (bên phải) và phần tử tương ứng nằm ở tầng dưới.
Kế tiếp, định nghĩa danh sách nhảy cóc với hàm khởi tạo:
class SkipList(object):
def __init__(self):
self.head = SkipListNode(None)
Lớp SkipList sử dụng biến head để lưu phần tử đầu tiên của tầng cao nhất, đây luôn là vị trí bắt đầu khi chúng ta duyệt danh sách.
Dễ thấy rằng tác vụ Thêm và Tìm Kiếm đều cần phải duyệt qua danh sách với cùng một cách để tìm một giá trị, vì vậy chúng ta định nghĩa hàm _search để có thể dùng chung cho cả hai như sau:
#
def _search(self, value):
last_nodes = []
current_node = self.head
while True:
if current_node.next is not None and current_node.next.value <= value:
current_node = current_node.next
else:
last_nodes.append(current_node)
if current_node.down is not None:
current_node = current_node.down
else:
break
return last_nodes
Cách hoạt động của hàm này được mô tả ở mục Tìm kiếm trong danh sách, giá trị trả về là danh sách p[N-1], p[N-2], ..., p[0] tương ứng với phần tử cuối cùng được duyệt đến tại các tầng N-1, N-1, ..., 0.
Lúc này hàm search của chúng ta khá đơn giản, chỉ cần kiểm tra giá trị của phần tử cuối cùng được trả về bởi _search:
#
def search(self, value):
last_nodes = self._search(value)
if last_nodes[-1].value == value:
return value
return None
Hàm insert để thêm phần tử vào danh sách:
#
def insert(self, new_value):
last_nodes = self._search(new_value)
# Stop if the value is already there in the list
if last_nodes[-1].value == new_value:
return
last_created_node = None
while True:
new_node = SkipListNode(new_value)
if len(last_nodes) > 0:
last_node = last_nodes.pop()
new_node.next = last_node.next
last_node.next = new_node
else:
new_head = SkipListNode(None)
new_head.down = self.head
new_head.next = new_node
new_node.next = None
self.head = new_head
new_node.down = last_created_node
last_created_node = new_node
# We are flipping the coin now
if random.randint(0, 1) != 0:
break
Và cuối cùng là hàm remove để xóa phần tử khỏi danh sách:
#
def remove(self, value):
current_node = self.head
while True:
if current_node.next is not None and current_node.next.value <= value:
if current_node.next.value < value:
current_node = current_node.next
else:
current_node.next = current_node.next.next
if current_node.value is None and current_node.next is None\
and current_node.down is not None:
self.head = current_node.down
else:
if current_node.down is not None:
current_node = current_node.down
else:
break
Về cơ bản hàm này khá giống hàm _search: chúng ta vẫn duyệt từ head để tìm kiếm giá trị value. Điểm khác biệt là, nếu tìm thấy value ở bất kỳ tầng nào, chúng ta tiến hành xóa phần tử khỏi tầng đó đồng thời xóa luôn tầng này nếu không còn phần tử (khác NULL) nào khác.
Độ phức tạp
- Trung bình
- Bộ nhớ cần thiết: O(n)
- Thời gian tìm kiếm, thêm, xóa: O(logn)
- Tệ nhất
- Bộ nhớ cần thiết: O(n*logn)
- Thời gian tìm kiếm, thêm, xóa: O(n)
Bàn luận thêm
- Các bạn có thể thấy ở thao tác Thêm phần tử, danh sách không thay đổi nếu chúng ta thêm một phần tử vốn đã có sẵn trong danh sách. Điều này đồng nghĩa với việc chúng ta mặc định các phần tử là đôi một khác nhau. Hãy sửa lại các đoạn mã ở trên để danh sách nhảy cóc của chúng ta có thể hỗ trợ các phần tử giống nhau.
- Để ý rằng độ phức tạp của Danh Sách Nhảy Cóc tương đương với Cây Nhị Phân, ngoại trừ việc Danh Sách Nhảy Cóc sử dụng nhiều bộ nhớ hơn. Bạn đọc có thể chỉ ra điểm nhỉnh hơn của Danh Sách Nhảy Cóc không? (Gợi ý: chuyện gì xảy ra đối với hai danh sách khi có nhiều tiến trình muốn thêm phần tử vào danh sách cùng một lúc?)
- Hãy viết hàm in ra trạng thái của danh sách nhảy cóc.
- Hãy viết hàm in ra các phần tử của danh sách nhảy cóc.