Introduction to
Object-Oriented Programming
Using C++

Peter Müller
Introduction to Object-Oriented Programming Using C++

Tìm kiếm quick sort và heap sort

Quick Sort

Quick sort là phương pháp đổi chỗ từng phần (partition exchange), đây là phương pháp rất hiệu quả, rất thông dụng..
Nội dung của phương pháp này như sau:
Chọn một nút bất kỳ trong danh sách(Giả sử là nút đầu tiên) gọi là nút làm trục (pivot node), xác định vị trí hợp lệ của nút này trong danh sách (gọi là vị trí pivot).
Tiếp theo chúng ta phân hoạch các nút còn lại trong danh sách cần sắp xếp sao cho từ vị trí 0 đến vị trí pivot-1 đều có nội dung nhỏ hơn hoặc bằng nút làm trục, các nút từ vị trí pivot+1 đến n-1 đều có nội dung lớn hơn nút làm trục.
Quá trình lại tiếp tục như thế với hai danh sahs con từ trị trí 0 đến vị trí pivot-1 và từ vị trí pivot+1 đến vị trí n-1, ... Sau cùng chúng ta sẽ được danh sách có thứ tự.

Mô tả giải thuật Quick sort

Giai thuat: QuickSort(nodes[], low, up)
Mo Ta; Giair thuat QuickSort, dung phuong phap de qui sawp xep va cac nut trong danh sach giua hai vi tri
  low va up
Du Lieu nhap:
 - Danh sach cac nut chua sap xep (giua hai vi tri low va up)
       - low va up
Du Lieu Xuat:
 Danh sach cac nut (giua hai vi tri low va up) da duoc sap xep

Hanh dong
 if(low >= up) // dieu kien dung
   ket thuc giai thuat
  if(low < up)
   - Phan hoach: partition(nodes[], low, up, pivot)
      + partition phan danh sach thanh ba phan:
           * nut lam truc: nodes[low] tro thanh nodes[pivot]
           * danh sach con 1: nodes[i] <= nodes[pivot]
            (voi i < pivot)
           * danh sach con 2: nodes[i] > nodes[pivot]
            (voi i > pivot)
     - Goi de qui: QuickSort(nodes[], low, pivot-1)
     - Goi de qui: QuickSort(nodes[], pivot+1, up)
Ket Thuc

Giải thuật Partion
vấn đề tiếp theo là giải thuật partition giúp phân danh sách làm ba phần:

• Nút đầu (nút làm trục) đặt ở vị trí pivot
• Danh sách con 1 từ vị trí low đến pivot-1 có nội dung nhỏ hơn hay bằng nút làm trục.
• Danh sách con 2 từ vị trí low đến pivot+1 có nội dung lớn hơn hay bằng nút làm trục.

Người ta xử lý giải thuật partition theo mô tả như sau:
1. Chọn nodes[low] (nút đầu tiền) là nút làm trục.
2. Quét danh sách theo hai hướng để đổi chỗ các cặp nút "sai" vị trí, nơi gặp nhau của hai hướng quét chính là vị trí pivot:
Quét từ low lên: con trỏ l xuất phát từ vị trí low và tăng dần lên, dừng lại khi gặp nút có nội dung lớn hơn nút làm trục, ghi nhận vị trí l lúc này.

• Quét từ up xuống: con trỏ u xuất phát từ vị trí up và giảm dần xuống, dừng lại khi gặp nút có nội dung nhỏ hơn hay bằng nút làm trục, ghi nhận vị trí u lúc này.
• Đổi chỗ hai nút tại vi trí l và u.
• Cứ tiếp tục quét theo hai hướng và đổi chỗ các cặp nút "sai" vị trí, quá trình này dừng lại khi l = u (hai hướng quét gặp nhau), nợi gặp nhau chính là vị trí pivot (pivot = u = l).

3. Đổi chỗ hai nút tại vị trí low (nút làm trục) và nút tại vị trí pivot.

Sau đây là giải thuật partition

Giai Thuat: partition(nodes[], low, up, pivot)
Mo Ta: Giai thuat partition, phan danh sach thanh 3 phan ...
Du Lieu Nhap:
 Danh sach cac nut trong khoang vi tri tu low den up.
Du Lieu Xuat:
 Dua nut lam truc ve vi tri pivot, doi cho cac nut trong danh sach
  sao cho cac nut co noi dung nho hon hay bang nut lam truc duoc
  bo tri truoc nut lam truc, cac nut co noi dung lon hon nut lam
  truc duoc bo tri sau nut lam truc.
Hanh Dong
 1. Chon nodes[low] la nut lam truc
  Gan: l = low;
        u = up;
  2. while(l < u) // vong lap xu ly hai huong quet
   {
          Quet huong tu low len, dung lai khi gap nut lon hon nut lam truc,
          ghi nhan vi tri l luc nay

          Quet huong tu up xuong, dung lai khi gap nut nho hon hay bang
          nut lam truc, ghi nhan vi tri u luc nay

          Doi cho hai nut tai hai vi tri l va u
     }

  3. Doi cho hai nut tai hai vi tri low va u (luc nay pivot = u)
Ket Thuc

Cài đặt giải thuật QuickSort
Sau đây là hàm QuickSort() dùng phương pháp đệ qui, hàm này có gọi hàm partition() để phân hoạch danh sách con thành 3 phần.
Hàm QuickSort()

void QuickSort(int nodes[], int low, int up)
{
int pivot;
if(low >= up) // dieu kien dung
return;

if(low < up)
{
partition(nodes, low, up, &pivot);
QuickSort(nodes, low, pivot - 1);
QuickSort(nodes, pivot + 1, up);
}
}

Hàm partition():

void partition(int nodes [], int low, int up, int *pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon nut dau lam nut truoc
l = low;
u = up;
while(l < u)
{
while(nodes[l] <= nuttruc && l < up)
l++;
while(nodes[u] > nuttruc)
u--;
if(l < u)
{
// doi cho cap nut sai vi tri
temp = nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
nodes[low] = nodes[u];
nodes[u] = nuttruc;
*pivot = u;
}

Nhận xét, so sánh

• Quick Sort phức tạp hơn Bubble Sort nhưng hiệu quả hơn.
• Quick Sort thích hợp cho danh sách ban đầu chưa có thứ tự.
• Quick Sort kém hiệu quả khi danh sách ban đầu gần có thứ tự. Đặc biệt với danh sách dã có thứ tự (lớn dần hoặc nhở dần) lại là trường hợp xấu nhất của giải thuật Quick Sort.

Chương trình minh họa sắp xếp một mảng kiểu int

#include
#include
void partition(int nodes [], int low, int up, int *pivot);
void QuickSort(int nodes[], int low, int up)
{
int pivot;
if(low >= up) // dieu kien dung
return;
if(low < up)
{
partition(nodes, low, up, &pivot);
QuickSort(nodes, low, pivot - 1);
QuickSort(nodes, pivot + 1, up);
}
}

void partition(int nodes [], int low, int up, int *pivot)
{
int nuttruc, l, u, temp;
nuttruc = nodes[low]; // Chon nut dau lam nut truoc
l = low;
u = up;
while(l < u)
{
while(nodes[l] <= nuttruc && l < up)
l++;
while(nodes[u] > nuttruc)
u--;
if(l < u)
{
// doi cho cap nut sai vi tri
temp = nodes[l];
nodes[l] = nodes[u];
nodes[u] = temp;
}
}
// doi cho hia nut tai low va u (luc nay u la vi tri nut truc)
nodes[low] = nodes[u];
nodes[u] = nuttruc;
*pivot = u;
}


void main()
{
int mang[7];
for(int i = 0;i < 7;i++)
{
cout<<"Nhap vao phan tu thu "<<(i+1)<<": ";
cin>>mang[i];
}
cout<<endl;
for(int i = 0;i < 7;i++)
{
cout<<mang[i]<<" ";
}
QuickSort(mang, 0, 7);
cout<<endl<<endl<<"danh sach sau khi da sap xep: ";
for(int i = 0;i < 7;i++)
{
cout<<mang[i]<<" ";
}
getch();
}

Heap Sort

Sắp xếp vun đống (heapsort) là một trong các phương pháp sắp xếp chọn. Ở mỗi bước của sắp xếp chọn ta chọn phần tử lớn nhất (hoặc nhỏ nhất) đặt vào cuối (hoặc đầu) danh sách, sau đó tiếp tục với phần còn lại của danh sách. Thông thường sắp xếp chọn chạy trong thời gian O(n2). Nhưng heapsort đã giảm độ phức tạp này bằng cách sử dụng một cấu trúc dữ liệu đặc biệt được gọi là đống (heap). Đống là cây nhị phân mà trọng số ở mỗi đỉnh cha lớn hơn hoặc bằng trọng số các đỉnh con của nó. Một khi danh sách dữ liệu đã được vun thành đống, gốc của nó là phần tử lớn nhất, thuật toán sẽ giải phóng nó khỏi đống để đặt vào cuối danh sách. Sắp xếp vun đống chạy trong thời gian O(n log n).
Xem thêm chi tiết tại đây.
http://www.uit.edu.vn/data/gtrinh/TH103/Htm/Bai04.htm

#include <>
#include <>
int heapSize = 10;
void print(int a[])
{
for (int i = 0; i <= 9; i++)
{
cout << a[i] << "-";
}
cout << endl;
}

int parent(int i)
{
if(i==1)
return 0;

if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}

int left(int i)
{
return (2 * i) + 1;
}

int right(int i)
{
return (2 * i) + 2;
}

void heapify(int a[], int i)
{
int l = left(i), great;
int r = right(i);
if ( (a[l] > a[i]) && (l < heapSize))
{
great = l;
}
else {
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize))
{
great = r;
}
if (great != i)
{
int temp = a[i];
a[i] = a[great];
a[great] = temp;
heapify(a, great);
}
}

void BuildMaxHeap(int a[])
{
for (int i = (heapSize - 1) / 2; i >= 0; i--)
{
heapify(a, i);
print(a);
}
}

void HeapSort(int a[]) {
BuildMaxHeap(a);
for (int i = heapSize; i > 0; i--)
{
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize - 1;
heapify(a, 0);
}

}

void main()
{
int arr[] = {2, 9, 3, 6, 1, 4, 5, 7, 0, 8};
HeapSort(arr);
print(arr);
}

Cấu trúc dữ liệu chương 2 b Tìm kiếm

3. Các phương pháp tìm kiếm nội

Có 2 giải thuật thường được áp dụng để tìm kiếm dữ liệu là tìm tuyến tính và tìm nhị phân

3.1 Tìm kiếm tuyến tính

Giải thuật
Tìm tuyến tính là một kỹ thuật tìm kiếm rất đơn giản và cổ điển. Thuật toán tiến hành so sánh x lần lượt với phần tử thứ nhất, thứ hai, ... của mảng a cho đến khi gặp được phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x. Các bước tiến hành như sau :
Bước 1:
i = 1; // bắt đầu từ phần tử đầu tiên của dãy
Bước 2: So sánh a[i] với x, có 2 khả năng :
a[i] = x : Tìm thấy. Dừng
a[i] != x : Sang Bước 3.
Bước 3 :
i = i+1; // xét tiếp phần tử kế trong mảng
Nếu i >N: Hết mảng, không tìm thấy.Dừng
Ngược lại: Lặp lại Bước 2.
Ví dụ : cho dãy số a: 12 2 8 5 1 6 4 15
Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau :
Hình 2.2
i = 1
Hình 2.3
i = 2
i = 3 Dừng

Cài đặt
Từ mô tả trên đây của thuật toán tìm tuyến tính , có thể cài đặt hàm LinearSearch để xác định vị trí của phần tử có khoá x trong mảng a :

int LinearSearch(int a[], int N, int x)
{ int i=0;
while ((i<N) && (a[i]!=x )) i++;
if(i==N) return -1; // tìm hết mảng nhưng không có x
else return i; // a[i] là phần tử có khoá x
}

Trong cài đặt trên đây, nhận thấy mỗi lần lặp của vòng lặp while phải tiến thành kiểm tra 2 điều kiện (i<N) - điều kiện biên của mảng - và (a[i]!=x )- điều kiện kiểm tra chính. Nhưng thật sự chỉ cần kiểm tra điều kiện chính(a[i] !=x), để cải tiến cài đặt, có thể dùng phương pháp "lính canh" - đặt thêm một phần tử có giá trị x vào cuối mảng, như vậy bảo đảm luôn tìm thấy x trong mảng, sau đó dựa vào vị trí tìm thấy để kết luận. Cài đặt cải tiến sau đây của hàm LinearSearch giúp giảm bớt một phép so sánh trong vòng lặp :

int LinearSearch(int a[],int N,int x)
{ int i=0; // mảng gồm N phần tử từ a[0]..a[N-1]
a[N] = x; // thêm phần tử thứ N+1
while (a[i]!=x ) i++;
if (i==N)
return -1; // tìm hết mảng nhưng không có x
else
return i; // tìm thấy x tại vị trí i
}

Ðánh giá giải thuật
Có thể ước lượng độ phức tạp của giải thuật tìm kiếm qua số lượng các phép so sánh được tiến hành để tìm ra x. Trường hợp giải thuật tìm tuyến tính, có:
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử đầu tiên có giá trị x
Xấu nhất n+1 Phần tử cuối cùng có giá trị x
Trung bình (n+1)/2 Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau.
Vậy giải thuật tìm tuyến tính có độ phức tạp tính toán : T(n) = O(n)

Nhận xét

• Giải thuật tìm tuyến tính không phụ thuộc vào thứ tự của các phần tử mảng, do vậy đây là phương pháp tổng quát nhất để tìm kiếm trên một dãy số bất kỳ.
• Một thuật toán có thể được cài đặt theo nhiều cách khác nhau, kỹ thuật cài đặt ảnh hưởng đến tốc độ thực hiện của thuật toán.

3.2 Tìm kiếm nhị phân

Giải thuật
Ðối với những dãy số đã có thứ tự ( giả sử thứ tự tăng ), các phần tử trong dãy có quan hệ ai -1 £ ai £ ai+1, từ đó kết luận được nếu x > ai thì x chỉ có thể xuất hiện trong đoạn
[ai+1 ,aN] của dãy , ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1 ,ai-1] của dãy . Giải thuật tìm nhị phân áp dụng nhận xét trên đây để tìm cách giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Ý tưởng của giải thuật là tại mỗi bước tiến hành so sánh x với phần tử nằm ở vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy tìm kiếm hiện hành. Giả sử dãy tìm kiếm hiện hành bao gồm các phần tử aleft .. aright , các bước tiến hành như sau :

Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử
Bước 2:
mid = (left+right)/2; // lấy mốc so sánh
So sánh a[mid] với x, có 3 khả năng :
a[mid] = x: Tìm thấy. Dừng
a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1 :
right =midle - 1;
a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright :
left = mid + 1;
Bước 3:
Nếu left  right //còn phần tử chưa xét, tìm tiếp.
Lặp lại Bước 2.
Ngược lại: Dừng; //Ðã xét hết tất cả các phần tử.
Ví dụ : Cho dãy số a gồm 8 phần tử:
1 2 4 5 6 8 12 15

Nếu giá trị cần tìm là 8, giải thuật được tiến hành như sau:
left = 1, right = 8, midle = 4

left = 5, right = 8, midle = 6 Dừng

Cài đặt
Thuật toán tìm nhị phân có thể được cài đặt thành hàm BinarySearch:

int BinarySearch(int a[],int N,int x )
{ int left =0; right = N-1;
int midle;
do {
mid = (left + right)/2;
if (x = a[midle]) return midle;//Thấy x tại mid else
if (x < a[midle]) right = midle -1;
else left = midle +1;
}while (left <= right);
return -1; // Tìm hết dãy mà không có x
}

Ðánh giá giải thuật
Trường hợp giải thuật tìm nhị phân, có bảng phân tích sau :
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử giữa của mảng có giá trị x
Xấu nhất log 2 n Không có x trong mảng
Trung bình log 2 (n/2) Giả sử xác suất các phần tử trong mảng nhận giá trị x là như nhau
Vậy giải thuật tìm nhị phân có độ phức tạp tính toán : T(n) = O(log 2 n)

Nhận xét

• Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp dụng được cho những dãy đã có thứ tự.

• Giải thuật tìm nhị phân tiết kiệm thời gian hơn rất nhiều so với giải thuật tìm tuyến tính do Tnhị phân (n) = O(log2n) <>

Tuy nhiên khi muốn áp dụng giải thuật tìm nhị phân cần phải xét đến thời gian sắp xếp dãy số để thỏa điều kiện dãy số có thứ tự. Thời gian này không nhỏ, và khi dãy số biến động cần phải tiến hành sắp xếp lại . Tất cả các nhu cầu đó tạo ra khuyết điểm chính cho giải thuật tìm nhị phân. Ta cần cân nhắc nhu cầu thực tế để chọn một trong hai giải thuật tìm kiếm trên sao cho có lợi nhất

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() < 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 = , khóa =
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,">

1. William Pugh, A Skip List Cook Book, 6/1990, Department of Computer Science, University of MaryLand, College Park.


2. Thomas A. Anastasio, Skip Lists, 22/12/1999,

Theo http://vnoi.info