Cấu trúc dữ liệu và Giải thuật Bài 83: Skip List - Danh sách liên kết nhảy cóc, sức mạnh xác suất thay thế Cây nhị phân cân bằng.

Khi thiết kế các hệ thống cơ sở dữ liệu trên RAM (In-memory Database), lập trình viên luôn khao khát một cấu trúc dữ liệu có thể Duyệt (Traverse), Tìm kiếm (Search), Thêm (Insert), và Xóa (Delete) trong thời gian $O(\log N)$.

Các Cây nhị phân cân bằng (như AVL Tree, Red-Black Tree) hoàn thành xuất sắc nhiệm vụ này. Tuy nhiên, việc cài đặt và gỡ lỗi Red-Black Tree là một cơn ác mộng. Bất kỳ thao tác thêm/xóa nào cũng có thể kích hoạt một chuỗi các phép "Xoay cây" (Tree Rotation) phức tạp để duy trì tính cân bằng, gây khó khăn cực lớn cho việc xử lý đa luồng (Concurrency/Locking).

Năm 1989, William Pugh đã phát minh ra một giải pháp thanh lịch đến ngỡ ngàng: Skip List (Danh sách nhảy cóc). Bằng cách sử dụng xác suất (Tung đồng xu) để xây dựng các tầng liên kết, Skip List đạt được hiệu năng $O(\log N)$ y hệt Red-Black Tree nhưng với mã nguồn ngắn gọn hơn hàng chục lần và khả năng hỗ trợ đa luồng tuyệt vời.

1. Ý tưởng cốt lõi: Nâng cấp Linked List bằng "Đường cao tốc"

Một danh sách liên kết đơn (Singly Linked List) đã được sắp xếp có nhược điểm chí mạng là thời gian tìm kiếm lên tới $O(N)$. Để tìm số 50, bạn phải đi bộ qua 10, 20, 30, 40...

Skip List giải quyết vấn đề này bằng cách xây dựng nhiều tầng (Levels) liên kết chồng lên nhau:

• Tầng 0 (Đường làng): Chứa tất cả các phần tử. Đây là một danh sách liên kết chuẩn.

• Tầng 1 (Đường quốc lộ): Chỉ chứa khoảng một nửa số phần tử của Tầng 0. Các con trỏ ở đây nhảy cóc qua 1 phần tử.

• Tầng 2 (Đường cao tốc): Chỉ chứa khoảng một phần tư số phần tử. Nhảy cóc qua 3 phần tử.

• ...

• Tầng Max (Đường hàng không): Chỉ chứa một vài phần tử mốc.

Thuật toán Tìm kiếm (Search):

Khi cần tìm số 50, bạn luôn xuất phát từ tầng cao nhất. Bạn đi dọc theo "đường cao tốc" cho đến khi gặp một số lớn hơn 50 (hoặc đụng cuối đường). Lúc đó, bạn rớt xuống một tầng và tiếp tục đi tới. Quá trình này lặp lại cho đến khi rớt xuống Tầng 0 và tìm đúng số 50. Nhờ việc nhảy cóc, thời gian tìm kiếm rút ngắn xuống đúng $O(\log N)$.

2. Bí mật của Skip List: Xác suất tung đồng xu (Coin Flip)

Làm sao để biết phần tử nào được phép xây bục nhô lên Tầng 1, Tầng 2, hay Tầng 3?

Nếu chúng ta duy trì một quy tắc cứng nhắc (ví dụ: cứ 2 phần tử Tầng 0 thì có 1 phần tử Tầng 1), mỗi khi Insert hoặc Delete, chúng ta lại phải tính toán dịch chuyển toàn bộ cấu trúc — lặp lại đúng nhược điểm của Red-Black Tree.

Skip List giải quyết bằng cách phó mặc hoàn toàn cho sự ngẫu nhiên:

Mỗi khi bạn chèn một Nút mới vào Tầng 0, hệ thống sẽ thực hiện thao tác "Tung đồng xu" (Coin Flip) ngẫu nhiên $50/50$:

• Nếu ra Ngửa (Heads): Nút này được phép xây thêm một tầng (lên Tầng 1). Sau đó, tiếp tục tung đồng xu.

• Nếu lại ra Ngửa: Xây tiếp lên Tầng 2. Tiếp tục tung...

• Nếu ra Sấp (Tails): Dừng lại. Cố định chiều cao của Nút đó.

Nhờ định luật số lớn của Xác suất Thống kê, cấu trúc tầng của Skip List sẽ tự động phân bổ theo tỷ lệ 1/2, 1/4, 1/8... tạo nên một cái cây cân bằng hoàn hảo về mặt xác suất mà không cần bất kỳ thao tác "Xoay cây" (Rotation) nào.

4. Triển khai Skip List bằng Golang

Đoạn code dưới đây cài đặt một Skip List cơ bản. Mấu chốt nằm ở hàm randomLevel() sử dụng math/rand và mảng update lưu trữ các vị trí cần "nối dây" ở mỗi tầng khi rớt xuống.

Go

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const MaxLevel = 16 // Chiều cao tối đa của Skip List
const P = 0.5       // Xác suất tung đồng xu ra "Ngửa"

type SkipNode struct {
	Value   int
	Forward []*SkipNode // Mảng con trỏ chứa các liên kết cho từng tầng
}

func newSkipNode(value, level int) *SkipNode {
	return &SkipNode{
		Value:   value,
		Forward: make([]*SkipNode, level),
	}
}

type SkipList struct {
	Head  *SkipNode
	Level int // Tầng cao nhất hiện tại đang được sử dụng
}

func NewSkipList() *SkipList {
	rand.Seed(time.Now().UnixNano())
	return &SkipList{
		Head:  newSkipNode(-1, MaxLevel),
		Level: 1, // Bắt đầu với tầng thấp nhất là 1 (chỉ số 0)
	}
}

// Giả lập tung đồng xu để quyết định số tầng (level) cho nút mới
func (sl *SkipList) randomLevel() int {
	level := 1
	for rand.Float32() < P && level < MaxLevel {
		level++
	}
	return level
}

// Thao tác Thêm (Insert) O(log N)
func (sl *SkipList) Insert(value int) {
	// update lưu các nút cuối cùng ở mỗi tầng trước khi 'rớt' xuống
	update := make([]*SkipNode, MaxLevel)
	current := sl.Head

	// 1. Tìm vị trí chèn và ghi lại lịch sử rớt tầng
	for i := sl.Level - 1; i >= 0; i-- {
		// Đi ngang trên tầng hiện tại cho đến khi gặp giá trị lớn hơn hoặc nil
		for current.Forward[i] != nil && current.Forward[i].Value < value {
			current = current.Forward[i]
		}
		update[i] = current
	}

	// Tránh chèn trùng lặp (Tùy logic bài toán, ở đây cho phép chèn hoặc bỏ qua)
	if current.Forward[0] != nil && current.Forward[0].Value == value {
		return // Đã tồn tại
	}

	// 2. Tung đồng xu xác định độ cao cho nút mới
	lvl := sl.randomLevel()

	// Nếu độ cao mới vượt quá đỉnh hiện tại của Skip List, cập nhật mảng update để nối từ Head
	if lvl > sl.Level {
		for i := sl.Level; i < lvl; i++ {
			update[i] = sl.Head
		}
		sl.Level = lvl
	}

	// 3. Tạo nút mới và Nối dây (Wiring)
	newNode := newSkipNode(value, lvl)
	for i := 0; i < lvl; i++ {
		// Nối phần thân của nút mới với nút tiếp theo
		newNode.Forward[i] = update[i].Forward[i]
		// Nút phía trước sẽ trỏ vào nút mới
		update[i].Forward[i] = newNode
	}
}

// Thao tác Tìm kiếm (Search) O(log N)
func (sl *SkipList) Search(value int) bool {
	current := sl.Head
	// Bắt đầu từ tầng cao nhất
	for i := sl.Level - 1; i >= 0; i-- {
		// Trượt ngang
		for current.Forward[i] != nil && current.Forward[i].Value < value {
			current = current.Forward[i]
		}
		// Đụng tường hoặc gặp số lớn hơn -> Rớt xuống tầng i-1 (vòng lặp for giảm i)
	}
	
	// Khi rớt xuống hết tầng 0, phần tử tiếp theo chính là mục tiêu nếu nó tồn tại
	current = current.Forward[0]
	return current != nil && current.Value == value
}

func main() {
	list := NewSkipList()
	
	// Chèn dữ liệu
	values := []int{3, 6, 7, 9, 12, 19, 17, 26, 21, 25}
	for _, v := range values {
		list.Insert(v)
	}

	// Truy vấn
	target := 19
	if list.Search(target) {
		fmt.Printf("Đã tìm thấy %d trong Skip List!\n", target)
	} else {
		fmt.Printf("Không tìm thấy %d.\n", target)
	}
}

5. Phân tích Hiệu năng và Ứng dụng Thực tế

• Thời gian Truy vấn / Thêm / Xóa (Time Complexity): Trung bình là $O(\log N)$. Trong trường hợp xấu nhất (xác suất tung đồng xu ra Sấp toàn bộ), nó suy thoái về $O(N)$ — nhưng với thuật toán sinh ngẫu nhiên chuẩn, xác suất xảy ra điều này trên tập dữ liệu $10^6$ phần tử là vô cùng nhỏ (tương đương trúng số độc đắc nhiều lần liên tiếp).

• Không gian (Space Complexity): $O(N)$. Mỗi Nút trung bình chỉ chứa $\frac{1}{1-P} = 2$ con trỏ (với $P = 0.5$). Do đó tổng số con trỏ của Skip List chỉ gấp đôi Linked List bình thường, rất tiết kiệm RAM.

Ứng dụng cốt lõi ở tầng Enterprise:

Lý do Skip List nổi tiếng không nằm ở độ khó, mà nằm ở tính ứng dụng của nó trong siêu hệ thống phân tán và Caching:

1. Redis (Sorted Sets - ZSET): Dưới mui xe, Redis sử dụng Skip List kết hợp với Hash Map để cài đặt cấu trúc Sorted Set. Tại sao không dùng Red-Black Tree? Tác giả Redis (Salvatore Sanfilippo) đã chia sẻ rằng: Skip List cài đặt dễ hơn rất nhiều, dùng ít RAM hơn (có thể cấu hình $P = 0.25$), và đặc biệt là thao tác Range Query (lấy Top 10 bảng xếp hạng) cực kỳ nhanh vì Tầng 0 bản chất là một Doubly Linked List.

2. LevelDB / RocksDB (LSM-Tree): Ở Bài 79, MemTable trên RAM của cấu trúc LSM-Tree được Google và Facebook cài đặt mặc định bằng Skip List. Vì cấu trúc mảng ngẫu nhiên của Skip List hỗ trợ Lock-Free hoặc Fine-Grained Locking cho lập trình đa luồng (Concurrency) cực tốt, cho phép hàng nghìn luồng (Goroutines/Threads) ghi dữ liệu đồng thời mà không bị treo hệ thống do Xoay cây.

Skip List là minh chứng hoàn hảo cho triết lý thiết kế hệ thống hiện đại: Đôi khi, sự ngẫu nhiên và đơn giản (Simplicity) lại chiến thắng sự chặt chẽ và phức tạp của toán học thuần túy.