|
Skip List - đối thủ của cây cân bằng
Khi đề cập đến bài toán tìm kiếm chắc bạn đã ít nhiều biết đến cấu trúc cây cân bằng (balanced tree). Cấu trúc này cho phép thực hiện tìm kiếm với độ phức tạp trung bình là O(log2n). Tuy nhiên, để tránh tình trạng cây suy biến, ta phải cân bằng cây mỗi khi chèn một nút mới. Nói chung, cân bằng cây là một thao tác tương đối phức tạp do phải hoán chuyển nhiều nút và do đó cũng ảnh hưởng đến hiệu suất. Skip List giải quyết vấn đề này khá hiệu quả mà vẫn không ảnh hưởng đáng kể đến tốc độ của phép tìm kiếm.
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() < 0.5) && (level < max_level))
level++;
return level;
}
Để hiểu hoạt động của hàm này, ta chú ý đến biểu thức
rand() < 0.5
Hàm rand() phát sinh một số thực không âm ngẫu nhiên nhỏ hơn một. Nghĩa là 0≤rand() <1. Xác suất để biểu thức rand()<0.5 đúng hoặc sai đều là 50%.
Dễ dàng thấy được là xác suất để (level = 1 là đúng) là 50%.
Để có level = 2, biểu thức rand()<0.5 phải sai với level = 1 và đúng với level = 2. Xác suất để có level = 1 là sai là 50% và xác suất để có level = 2 là đúng cũng là 50%. Vậy xác suất để có level = 2 là đúng là : 50%×50% = 25%.
Tương tự, để có level = 3, biểu thức rand()<0.5 phải sai với level = 1 và sai với level = 2 và đúng với level = 3. Xác suất để có điều này là: 50%×50%×50% = 12.5%.
Hàm này phụ thuộc vào giá trị max_level (số tầng tối đa của SkipList). Một cách cảm tính, từ cây nhị phân cân bằng, ta thấy rằng max_level nên là log2(n) với n là tổng số nút của danh sách. Để tránh bị phụ thuộc vào số lượng nút, ta có thể dùng hằng số log2(N) trong đó N là chặn trên của n. Trên thực tế max_level = 32 (cho một list có tối đa khoảng 2^32 ~ 4 tỷ nút) là đủ dùng cho hầu hết các trường hợp.
Tìm kiếm
SkipListNode* Search(SkipList *list, int searchKey)
{
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 < searchKey)
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 < searchKey)
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 = <newLevel>, khóa = <searchKey>
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 NIL). 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 < searchKey)
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 < 1 vào SkipList để quy định tỷ lệ nút giữa các tầng. Nếu p=0.5, tầng i+1 sẽ có số nút bằng khoảng ½ so với tầng i. Nếu p=0.25, tầng i+1 sẽ có số nút bằng khoảng ¼ so với tầng i (nếu p=1/4, số nút cấp 1 sẽ là 75%, số nút cấp 2 là 25%×75% = 18.75%, số nút cấp 3 sẽ là: 25%×25%×75% = 4.6875%).
Rõ ràng là vì các nút không cách đều nhau nên hiệu suất tìm kiếm sẽ không là hằng số. Nếu quá xui, chẳng hạn như trường hợp tất cả nút đều có cùng cấp, thì hiệu suất tìm kiếm sẽ bị giảm đáng kể. Tuy nhiên, bằng toán học, giáo sư Pugh đã tính ra được ràng khả năng xảy ra những trường hợp xấu như vậy là rất thấp. Chẳng hạn với một SkipList có 4096 nút, p=0.5, khả năng để một thời gian tìm kiếm chậm hơn 3 lần (so với thời gian tìm kiếm trung bình) là một phần 200 triệu !
Một điểm cần lưu ý nữa là khi số lượng nút càng lớn (điều thường xảy ra trong thực tế), hiệu quả trung bình của SkipList càng sát với hiệu suất của cây cân bằng. Pugh cũng đề nghị nên sử dụng p=0.25 trong đa số trường hợp. Nếu như chúng ta đặt nặng tính ổn định của SkipList thì Pugh đề nghị nên dùng p=0.5. Điểm thú vị là với p=0.25, một nút trung bình chỉ có 1.33 con trỏ (trong khi đó cây cân bằng có 2 con trỏ). Điều này làm cho SkipList sử dụng ít bộ nhớ hơn cây cân bằng.
Tài liệu tham khảo
1) William Pugh, A Skip List Cook Book, 6/1990, Department of Computer Science, University of MaryLand, College Park.
|
