SkipList được giáo sư William Pugh thuộc trường đại học MaryLand giới thiệu vào khoảng tháng 8 năm 1989 trong một bài báo tham dự hội nghị về thuật toán và cấu trúc dữ liệu tại Ottawa Canada.
Skip List là một danh sách liên kết đơn mở rộng
Skip List chỉ là một mở rộng của danh sách liên kết đơn mà chúng ta đã rất quen thuộc. Hình bên dưới minh họa một danh sách liên kết đơn được sắp xếp tăng dần theo khóa.
Để tìm vị trí của một phần tử x trong danh sách liên kết đơn (đã được sắp xếp), ta phải duyệt từ đầu danh sách cho đến khi gặp nút có khóa cần tìm hoặc gặp nút có khóa lớn hơn khóa cần tìm. Trường hợp xấu nhất là phải duyệt qua tất cả nút trong danh sách (trong trường hợp khóa cần tìm lớn hơn tất cả các khóa trong danh sách).
Ý tưởng sơ khởi của Skip List là: để tăng hiệu quả của phép tìm kiếm, ta sẽ thêm vào các con trỏ tại một vài nút cho phép trỏ đến những nút nằm ở “xa” hơn. Chẳng hạn như ở hình dưới đây, các nút 5, 9, 16, 25 sẽ có các con trỏ phụ trỏ đến nút kế tiếp thứ hai (hay nói cách khác là “nhảy” – skip – hai nút một lần)
Với cấu trúc kiểu này, bạn có thể dễ dàng cảm nhận được là trung bình ta sẽ tiết kiệm được một nửa số bước tìm kiếm so với danh sách liên kết đơn bình thường. Nhìn vào hình ảnh, bạn sẽ thấy danh sách của ta bây giờ giống như có hai tầng (level). Tầng 1 là danh sách bình thường. Tầng 2 ở trên cũng là một danh sách liên kết đơn gồm có 5, 9, 16, 25 (nhảy 2 nút).
Dĩ nhiên là chúng ta có thể thêm vào một tầng nữa gồm các phần tử 9,25 (nhảy 4 nút) như hình dưới đây:
Để tìm kiếm một phần tử, ta xuất phát từ tầng cao nhất, duyệt qua các nút ở tầng hiện tại cho đến khi nút kế tiếp có khóa lớn hơn nút cần tìm. Lúc đó ta sẽ giảm đi một tầng. Nếu tầng hiện tại là 1 mà nút kế tiếp có giá trị lớn hơn nút cần tìm thì có nghĩa là nút cần tìm không có trong danh sách.
Hình trên minh họa cho quá trình tìm kiếm giá trị khóa 18. Ta khởi đầu với tầng 3, ta lần theo các nút ở tầng 3 cho đến khi gặp nút 9. Ta thấy nút kế tiếp là 25 lớn hơn 18 nên ta sẽ “xuống” tầng 2. Theo con trỏ ở tầng 2, ta sẽ đến nút 16. Nút kế tiếp là 25 lớn hơn 18 nên ta sẽ “xuống” tầng 1. Theo con trỏ ở tầng 1 ta gặp nút 18 chính là khóa cần tìm.
Một cách cảm tính là nếu như mỗi tầng ta giảm đi một nửa số phần tử thì cấu trúc này sẽ cho thời gian tìm kiếm y hệt như cây nhị phân tìm kiếm. Tuy nhiên, cấu trúc mở rộng này cũng gặp cùng một vấn đề như cây nhị phân là khi chèn một phần tử mới vào, ta lại phải mất công biến đổi để đảm bảo được “cấu trúc” của nó.
Skip List là cấu trúc dữ liệu có xác suất
Điểm chính giúp tốc độ tìm kiếm trung bình được tăng lên là do chúng ta giảm số nút ở mỗi tầng (để thực hiện phép tìm kiếm bằng cách nhảy). Tính chất “cách đều” chỉ đảm bảo được hiệu quả tìm kiếm lúc nào cũng như nhau.
Như vậy ta chỉ cần đảm bảo một tính chất là: số phần tử ở tầng trên phải xấp xỉ bằng một nửa (không cần chính xác) của tầng dưới. Nếu có 3 tầng, 100% phần tử ở tầng 1, khoảng 50% phần tử ở tầng 2, khoảng 25% phần tử ở tầng 3 và cứ thế. (Số nút ở hai tầng cao nhất sẽ xấp xỉ bằng nhau)
Sự đơn giản hóa này sẽ khiến việc chèn một phần tử vào danh sách trở nên rất đơn giản. Quan trọng nhất là chúng ta sẽ không cần phải sắp xếp lại danh sách nữa.
Tuy nhiên, để tiện cài đặt, ta sẽ dùng thuật ngữ khác đi một tí. Thay vì nhìn danh sách theo tầng, ta sẽ dùng khái niệm cấp của nút. Nếu một nút chỉ có một con trỏ, nó sẽ có cấp 1, nếu có hai con trỏ, nó có cấp 2 và cứ thế. Một cách tổng quát, sẽ có khoảng 50% số nút có cấp 1, 25% số nút có cấp 2, 12.5% số nút có cấp 3 và cứ thế.
Để chèn một nút vào danh sách, ta phát sinh ngẫu nhiên cấp của nó theo nguyên tắc là 50% khả năng có cấp 1, 25% có cấp 2, 12.5% có cấp 3 và cứ thế. Sau đó, tìm vị trí cần chèn (theo thuật toán tìm kiếm) rồi chỉ việc điều chỉnh lại các con trỏ là xong.
Phát sinh ngẫu nhiên cấp của một nút
int GenerateLevel(int max_level)
{
level=1;
while ((rand() < level =" 1" level =" 2," level =" 1" level =" 2." level =" 1" level =" 2" level =" 2" level =" 3," level =" 1" level =" 2" level =" 3." max_level =" 32" x =" list-">head;
// điều kiện dừng: (x->forward[i]->key >= searchKey) và (level=1)
for (i=list->level;i>1;i--)
while (x->forward[i]->key < x =" x-">forward[i];
x = x->forward[1];
if (x->key == searchKey)
return x;
else
return 0;
}
Chèn nút vào danh sách
void Insert(SkipList *list, int searchKey, int newValue)
{
SkipListNode* update[max_level+1];
//tìm vị trí nút cần chèn và ghi nhận các nút
//trỏ đến vị trí này
x = list->head;
for (i=list->level;i>1;i--)
{
while (x->forward[i]->key < x =" x-">forward[i];
update[i] = x; //ghi nhận nút trỏ đến vị trí chèn
}
x = x->forward[1];
if (x->key == searchKey)
x->value = newValue; //cập nhật giá trị nút nếu khóa đã tồn tại
else
{
newLevel = GenerateLevel(max_level);
if (newLevel > list->level)
{
for (i=list->level + 1;i<=newLevel;i++) update[i] = list->head;
list->level = newLevel;
}
// tạo một nút mới với cấp =
x = makeNode(newLevel,searchKey,value);
// cập nhật các nút trỏ đến nút mới và các con trỏ forward của nút mới
for (i=1;i<=newLevel;i++) { x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
}
}
Khởi tạo SkipList
SkipList rỗng bao gồm hai nút đặc biệt. Một nút head và nút tail (hay NI
. Cấp của SkipList lúc khởi tạo là 1. Khóa của tail phải luôn luôn lớn hơn khóa của tất cả các nút.Xóa một nút
void Delete(SkipList * list, int searchKey)
{
SkipListNode* update[max_level+1];
//tìm nút cần xóa và ghi nhận các nút
//trỏ đến nút này
SkipListNode *x = list->head;
for (i=list->level;i>1;i--)
{
while (x->forward[i]->key < x =" x-">forward[i];
update[i] = x; //ghi nhận các nút trỏ đến nút cần xóa
}
x = x->forward[1];
if (x->key == searchKey)
{
for (i=1;i<=list->level;i++)
{
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
free(x);
while ( (list->level > 1) && (list->head->forward[list->level] == 0) )
list->level--;
}
}
Một số bàn luận
Thay vì giới hạn ở hằng số 50% cho biết số lượng nút cấp i+1 bằng khoảng 50% số lượng nút cấp i. Pugh đề nghị kết hợp một giá trị p < p="0.5," p="0.25," p="1/4," p="0.5," p="0.25" p="0.5." p="0.25,">
- William Pugh, A Skip List Cook Book, 6/1990, Department of Computer Science, University of MaryLand, College Park.
- Thomas A. Anastasio, Skip Lists, 22/12/1999,
No comments:
Post a Comment