Trong báo cáo của mình, tác giả khẳng định: Skip List là sự thay thế hiệu quả cho cấu trúc cây cân bằng (Balanced Trees). Một Cấu trúc dữ liệu nổi tiếng và cổ điển nhất trong các cây cân bằng, được đưa ra bởi Adelson Velsky và E.M.Landis là cây AVL. Nó cho phép thực hiện thuật toán tìm kiếm với độ phức tạp trung bình là O(log2n ). Tuy nhiên để duy trì tính “cân bằng” của cấu trúc cây, các phép toán bổ sung và loại bỏ trên Balanced Trees được thực hiện khá phức tạp, sự phân tích một cách toán học của chúng cho đến nay vẫn còn là một bài toán mở. Skip List đã giải quyết vấn đề này một cách hiệu quả mà không làm ảnh hưởng đến tốc độ của phép tìm kiếm. Cấu trúc này thể hiện tính cân bằng một cách tự nhiên theo xác suất hơn là tạo nên sự cân bằng hoàn toàn. Kết quả là các thuật toán chèn và loại bỏ phần tử trở nên đơn giản, và quan trọng hơn là chúng được thực hiện nhanh hơn so với các thuật toán tương đương trên Balanced Trees.

Skip List là một danh sách liên kết đơn mở rộng với mục đích tăng tốc độ của phép toán tìm kiếm. Để tìm kiếm một phần tử trên danh sách liên kết đơn đã được sắp xếp (hình1), ta phải duyệt từ đầu danh sách cho đến khi gặp được nút có khoá cần tìm hoặc có khoá lớn hơn khoá cần tìm. Trong trường hợp tồi nhất ta phải duyệt qua toàn bộ các phần tử của danh sách, do dó chi phí cho phép toán tìm kiếm này là O(n).

(hình 1 - danh sách liên kết đơn)

Để tăng tốc độ của phép tìm kiếm trên danh sách liên kết, William Pugh thêm vào các con trỏ ở một số nút cho phép trỏ đến nững nút nằm ở xa hơn. Chẳng hạn ta có thể thêm vào các con trỏ phụ ở các nút có thứ tự chẵn, các con trỏ này trỏ đến các nút kế tiếp thứ hai (hình 2). Với việc thêm vào các con trỏ phụ, danh sách bây giờ giống như có hai tầng (level). Tầng một là danh sách ban đầu, tầng hai là một danh sách với các phần tử là các nút có thứ tự chẵn trong danh sách ban đầu. Tương tự, ta có thể thêm vào các con trỏ để tạo ra Skip List có nhiều tầng (hình 3).

(hình 2 - Skip List 2 tầng)

(hình 3 - Skip List 3 tầng)

Trong Skip List, một nút có k con trỏ được gọi là nút có cấp k. Theo các nhà nghiên cứu thì số cấp lớn nhất của một nút hay số tầng tối đa (MaxLevel) của Skip List nên là Log2n, với n là số nút của danh sách. Trên thực tế MaxLevel=32 được dùng cho danh sách có 232 (~ 4 tỷ) nút là đủ dùng cho hầu hết các trường hợp. Khác với Balanced Trees, thao tác bổ xung và loai bỏ trên Skip List được thực hiện rất dễ dàng. Để bổ xung (Insert) một phần tử, ta phải phát sinh ngẫu nhiên cấp của nút đó, tìm vị trí của nút cần chèn, cập nhật các con trỏ cho nút mới. Hình 4, 5 mô tả trực quan các thao tác này. Thao tác xoá (Remove) phần tử được thực hiện bằng cách tìm nút cần xoá, ghi nhận các con trỏ trỏ đến nút này, loại bỏ nút, cập nhật lại các con trỏ và MaxLevel.

(hình 4 – Tìm vị trí cần chèn một nút mới trong Skip List)

(hình 5- Skip List sau khi chèn phần tử mới)

Skip List là cấu trúc dữ liệu có xác suất. Hiệu suất 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 để tìm kiếm bằng cách “nhả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ó khoá lơn hơn khoá cần tìm. Lúc đó ta giảm đi một tầng và tiếp tục thực hiện quá trình tìm kiếm. Nếu ở tầng đáy (tầng 1) mà nút kế tiếp có khoá lớn hơn khoá cần tìm, thì nút cần tìm không có trong Skip List. Hình 6 minh hoạ tác tìm kiếm phần tử có khoá bằng 21. Khi các nút của danh sách càng lớn, hiệu quả trung bình của Skip List càng tiệm cận với Balanced Trees.

(hình 6 - minh họa quá trình tìm kiếm trên Skip List)

Nếu ai đã từng cài đặt các thuật toán cây cân bằng, chắc hẳn đều có chung một nhận định: đó là việc “nói dễ hơn làm” [3]. Với Skip List, việc cài đặt trở nên rất đơn giản. Để dễ dàng sử dụng trong nhiều chương trình, dưới đây ta cài đặt Skip List như một thư viện trong ngôn ngữ C++. Với Borland C++, hay Microsoft Visual C++ bạn soạn thảo tệp SkipList.h với nội dung như sau.

#include "stdio.h"
#include "conio.h"
#ifdef _WIN32 // Microsoft Visual C++
#include "BASETSD.H"
#define MAX_OF_KEY MAXINT_PTR
#else // Borland C++
#include "values.h"
#define MAX_OF_KEY MAXINT
#endif
#include "stdlib.h"
#define MAXLEVEL 15
#define Less(a,b) (a < b)
#define Equal(a,b) (a == b)
typedef int KeyType; /*kieu cua truong khoa */
typedef int RecType; /* kieu cua truong info*/
typedef struct NodeType
{
KeyType key; /* truong khoa */
RecType info; /* truong thong tin */
struct NodeType *forward[1];
};
typedef struct SkipList
{
NodeType *head; // nut dau danh sach
NodeType *tail; // nut cuoi danh sach
int ListLevel;
;
SkipList list;
/*** ham khoi tao ******************/
void init( SkipList &list)
{
if ((list.head =(NodeType *) malloc(sizeof(NodeType) + MAXLEVEL*sizeof(NodeType *))) == NULL)
{
printf(" loi cap phat!");
exit(EXIT_FAILURE);
}
if ((list.tail =(NodeType *) malloc(sizeof(NodeType) + sizeof(NodeType *))) == NULL)
{
printf(" loi cap phat!");
exit(EXIT_FAILURE);
}
list.tail->key=MAX_OF_KEY; //nut cuoi phai co gia tri khoa lon nhat
list.ListLevel=1;
for (int i=1;i<=MAXLEVEL;i++)
list.head->forward[i]=list.tail;
}
/*** ham phat sinh ngau nhien cap cua mot nut ***/
int generate_level(void)
{
int level=1;
while ((rand()< RAND_MAX/2) && (level level=level+1;
return level;
}
/*** ham chen mot nut vao Skip List *******/
void insert(SkipList &list, int key, RecType newvalue)
{
int i, newLevel;
NodeType *update[MAXLEVEL+1];
NodeType *x;
x=list.head;
for (i = list.ListLevel; i >0; i--)
{
while (Less(x->forward[i]->key, key))
x = x->forward[i];
update[i] = x;
}
x = x->forward[1];
if (Equal(x->key, key))
x->info=newvalue;
else
{
newLevel = generate_level();
if (newLevel>list.ListLevel)
{
for (i=list.ListLevel+1;i<=newLevel;i++)
update[i]=list.head;
list.ListLevel=newLevel;
}
// tao nut
if ((x =(NodeType *) malloc(sizeof(NodeType) + newLevel*sizeof(NodeType *))) == NULL)
{
printf(" loi cap phat!");
exit(EXIT_FAILURE);
}
x->key=key; x->info=newvalue;
// cap nhat cac con tro
for (i=1;i<=newLevel;i++)
{
x->forward[i]=update[i]->forward[i];
update[i]->forward[i]=x;
}
}
}
/*** ham xoa mot nut trong Skip List *********/
void remove(SkipList &list, int key)
{
int i;
NodeType *update[MAXLEVEL+1], *x;
x = list.head;
for (i = list.ListLevel; i >= 1; i--)
{
while Less(x->forward[i]->key, key)
x = x->forward[i];
update[i] = x;
}
x = x->forward[1];
if (Equal(x->key, key)) // nut can xoa
{
for (i = 1; i <= list.ListLevel; i++)
{
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
free (x);
while ((list.ListLevel > 1)&&(list.head->forward[list.ListLevel] == list.tail))
list.ListLevel--;
}
}
/*** ham tim kiem mot nut co gia tri khoa bang key trong Skip List ****/
NodeType * search(SkipList list, int key)
{
int i;
NodeType *x = list.head;
for (i = list.ListLevel; i > 1; i--)
{
while Equal(x->forward[i]->key, key)
x = x->forward[i];
}
x = x->forward[1];
if Equal(x->key, key)
return x ;
else
return NULL;
}

Nhằm mục đích khảo sát, xo sánh và khẳng định sức mạnh của Skip List. Các nhà nghiên cứu đã tiến hành thực nghiệm với các kỹ thuật tìm kiếm khác nhau như Skip List, AVL Trees, 2-3 Trees, self-adjusting trees. Chương trình được cài đặt bằng ngôn ngữ C, thao tác tìm kiếm được thực hiện trên cấu trúc dữ liệu chứa 216 phần tử, trường khoá của các phần tử có kiểu Integer. Kết quả thực nghiệm thu được như bảng sau:

(bảng 1- khảo sát thời gian thực hiện các thao tác với các kỹ thuật tìm kiếm khác nhau) Trong cài đặt trên, hàm generate_level() sẽ phát sinh ngẫu nhiên cấp của một nút. Vì hàm rand() trả lại giá trị từ 0 đến RAND_MAX, nên số lượng nút ở cấp i+1 sẽ bằng khảng 50% ở cấp i. Gọi p là tỷ lệ giữa số nút ở cấp i+1và số nút cấp i, ta có thể thay đổi tỷ lệ này theo từng trường hợp cụ thể. William Pugh đề nghị nên sử dụng p=25% trong đa số trường hợp. Nếu ứng dụng yêu cầu tính ổn định cao thì nên sử dụng p=50%. Điều rất thú vị là với p=25%, một nút của Skip List trung bình chỉ có 1.33 con trỏ, trong khi đó Balanced Trees cần tới 2 con trỏ cho mỗi nút. Rõ ràng trong trường hợp này, Skip List tiết kiệm bộ nhớ hơn so với Balanced Trees và diều này một lần nữa chứng minh Skip List là một sự lựa chọn tốt cho các ứng dụng tìm kiếm. Xin được trích dẫn khẳng định của William Pugh để thay cho lời kết: “Whatever you might want to do using Balanced Trees, you can do it faster and more simply using Skip Lists”.

Tài liệu tham khảo

[1] William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Proceedings of the Workshop on Algorithms and Data Structures, Ottawa Canada, August 1989 (to appear in Comm. ACM).

[2] Pugh, W., Whatever you might want to do using Balanced Trees, you can do it faster and more simply using Skip Lists, Tech Report CS-TR-2286, Dept. of Computer Science, University of Maryland, College Park, July 1989.

[3] Robert Sedgewick. Cẩm nang thuật toán (bản dịch). NXB Khoa học và Kỹ thuật, Hà Nội, 1994.