Cấu trúc dữ liệu và Giải thuật Bài 75: Tổ tiên chung gần nhất (LCA) với thuật toán Binary Lifting - Tìm điểm giao thoa trên đồ thị Cây.

Trong quản trị mạng lưới hoặc phân cấp dữ liệu, bài toán định vị điểm giao thoa giữa hai nhánh hoàn toàn tách biệt là một yêu cầu thường trực. Giả sử tại Hasaki, bạn cần tìm người quản lý chung cấp thấp nhất của hai nhân viên bất kỳ trong sơ đồ tổ chức, hoặc trong kiến trúc Git, bạn cần tìm commit gốc chung (Merge Base) giữa hai branch để thực hiện giải quyết xung đột (conflict resolution).

Bài toán này được định nghĩa chuẩn xác trong khoa học máy tính là Tổ tiên chung gần nhất (Lowest Common Ancestor - LCA).

Nếu chúng ta cho hai node từ từ bò lên từng bậc một (đỉnh sâu hơn bò lên trước cho bằng độ sâu, rồi cả hai cùng bò lên cho đến khi đụng nhau), thuật toán sẽ mất $O(N)$ thời gian. Khi hệ thống nhận hàng triệu truy vấn LCA mỗi giây, cách làm này lập tức sụp đổ. Để giải quyết, chúng ta sử dụng một kỹ thuật nhảy cóc dựa trên lũy thừa của 2, gọi là Binary Lifting (Nâng cấp nhị phân).

1. Nguyên lý của Binary Lifting (Nhảy cóc nhị phân)

Bất kỳ số nguyên nào (ví dụ: khoảng cách độ sâu giữa hai node) cũng có thể được biểu diễn dưới dạng tổng của các lũy thừa của 2 (Hệ nhị phân). Thay vì nhảy lên 1 bước, 2 bước, 3 bước... hệ thống sẽ được cấu hình để có thể nhảy một mạch $1, 2, 4, 8, 16 \dots$ bước.

Để làm được điều này, chúng ta cần một bước tiền xử lý (Preprocessing) bằng Lập trình động trên Cây. Ta định nghĩa bảng up[u][i], mang ý nghĩa là tổ tiên thứ $2^i$ của đỉnh $u$.

Công thức chuyển trạng thái là một kiệt tác của sự tối giản:

$$up[u][i] = up[up[u][i-1]][i-1]$$

(Tổ tiên thứ $2^i$ của tôi chính là tổ tiên thứ $2^{i-1}$ của người đang đứng ở vị trí tổ tiên thứ $2^{i-1}$ của tôi).

Với công thức này, ta có thể xây dựng bảng quy hoạch động cho toàn bộ cây trong thời gian $O(N \log N)$.

2. Chiến lược truy vấn LCA

Khi nhận được truy vấn tìm LCA của $u$ và $v$, thuật toán thực hiện 2 giai đoạn:

Giai đoạn 1: Cân bằng độ sâu (Leveling)

Nếu $u$ đang nằm sâu hơn $v$, ta phải kéo $u$ lên cho bằng độ sâu với $v$.

Gọi khoảng cách chênh lệch độ sâu là $K$. Ta duyệt qua các bit của $K$, nếu bit thứ $i$ bật sáng, ta cho $u$ nhảy lên $2^i$ bước: u = up[u][i]. Kết thúc giai đoạn này, $u$ và $v$ ở cùng một độ sâu. Nếu lúc này $u = v$, thì $v$ chính là LCA.

Giai đoạn 2: Nhảy song song (Simultaneous Jumping)

Khi $u$ và $v$ đã ngang hàng nhưng chưa trùng nhau, ta cho cả hai cùng nhảy lên trên. Ta xét các bước nhảy lớn nhất có thể ($2^{19}, 2^{18}, \dots, 2^0$).

• Nếu up[u][i] != up[v][i]: Nghĩa là bước nhảy này vẫn chưa chạm đến tổ tiên chung (hoặc đã chạm nhưng chưa phải là gần nhất), ta tự tin cho cả hai cùng nhảy lên: u = up[u][i] và v = up[v][i].

• Nếu up[u][i] == up[v][i]: Nghĩa là chúng đã nhảy quá xa lên phía trên tổ tiên chung, ta bỏ qua bước nhảy này.

Sau khi xét xong tới $2^0$, $u$ và $v$ sẽ dừng lại ngay bên dưới LCA đúng 1 bậc. Lúc này, LCA chính là up[u][0] (đỉnh cha trực tiếp của $u$).

3. Triển khai Binary Lifting LCA bằng Golang

Dưới đây là cài đặt chuẩn mực và tối ưu bộ nhớ cho bài toán LCA sử dụng Golang:

Go

package main

import (
	"fmt"
)

const LOG = 20 // Đủ để xử lý cây có kích thước lên tới 2^20 (hơn 1 triệu đỉnh)

type TreeLCA struct {
	n     int
	adj   [][]int
	depth []int
	up    [][]int
}

func NewTreeLCA(n int) *TreeLCA {
	t := &TreeLCA{
		n:     n,
		adj:   make([][]int, n),
		depth: make([]int, n),
		up:    make([][]int, n),
	}
	for i := range t.up {
		t.up[i] = make([]int, LOG)
	}
	return t
}

func (t *TreeLCA) AddEdge(u, v int) {
	t.adj[u] = append(t.adj[u], v)
	t.adj[v] = append(t.adj[v], u)
}

// Hàm DFS tiến hành tiền xử lý mảng depth và mảng up
func (t *TreeLCA) dfs(v, p, d int) {
	t.depth[v] = d
	t.up[v][0] = p // Tổ tiên thứ 2^0 (tức là cha trực tiếp)

	// Quy hoạch động xây dựng bảng tổ tiên
	for i := 1; i < LOG; i++ {
		if t.up[v][i-1] != -1 {
			t.up[v][i] = t.up[t.up[v][i-1]][i-1]
		} else {
			t.up[v][i] = -1
		}
	}

	for _, to := range t.adj[v] {
		if to != p {
			t.dfs(to, v, d+1)
		}
	}
}

func (t *TreeLCA) Build(root int) {
	t.dfs(root, -1, 0)
}

// Truy vấn Tổ tiên chung gần nhất (LCA) trong thời gian O(log N)
func (t *TreeLCA) GetLCA(u, v int) int {
	// Đảm bảo u luôn là đỉnh sâu hơn để tiện xử lý
	if t.depth[u] < t.depth[v] {
		u, v = v, u
	}

	// Giai đoạn 1: Kéo u lên cho ngang bằng độ sâu với v
	diff := t.depth[u] - t.depth[v]
	for i := 0; i < LOG; i++ {
		if (diff & (1 << i)) != 0 {
			u = t.up[u][i]
		}
	}

	if u == v {
		return u
	}

	// Giai đoạn 2: Cho cả u và v cùng nhảy lên sát tới LCA
	for i := LOG - 1; i >= 0; i-- {
		if t.up[u][i] != -1 && t.up[u][i] != t.up[v][i] {
			u = t.up[u][i]
			v = t.up[v][i]
		}
	}

	// Kết quả là cha trực tiếp của vị trí hiện tại
	return t.up[u][0]
}

func main() {
	// Xây dựng cây mẫu 9 đỉnh
	n := 9
	tree := NewTreeLCA(n)
	tree.AddEdge(0, 1)
	tree.AddEdge(0, 2)
	tree.AddEdge(1, 3)
	tree.AddEdge(1, 4)
	tree.AddEdge(2, 5)
	tree.AddEdge(4, 6)
	tree.AddEdge(4, 7)
	tree.AddEdge(5, 8)

	tree.Build(0) // Gốc cây là 0

	fmt.Printf("LCA của 6 và 7 là: %d\n", tree.GetLCA(6, 7)) // Mong đợi: 4
	fmt.Printf("LCA của 6 và 3 là: %d\n", tree.GetLCA(6, 3)) // Mong đợi: 1
	fmt.Printf("LCA của 7 và 8 là: %d\n", tree.GetLCA(7, 8)) // Mong đợi: 0
}

4. Phân tích Hiệu năng (Big-O)

• Thời gian Tiền xử lý (Preprocessing): $O(N \log N)$. Lượt chạy DFS tốn $O(N)$, và tại mỗi đỉnh, ta thực hiện quy hoạch động lấp đầy bảng kích thước $\log_2(N)$.

• Thời gian Truy vấn (Query Time): $O(\log N)$. Vòng lặp cân bằng độ sâu và vòng lặp nhảy song song đều chạy qua đúng $\log_2(N)$ bit cố định, biến LCA trở thành một thuật toán phản hồi siêu tốc.

• Không gian (Space Complexity): $O(N \log N)$ để lưu trữ bảng 2D chứa các con trỏ tổ tiên của từng Node.

5. Ứng dụng Thực tế trong Kỹ thuật Phần mềm

LCA giải quyết triệt để các bài toán truy xuất quan hệ chéo trong mạng lưới phân cấp:

• Kiến trúc Hệ thống Quản lý Phiên bản (Git): Khi bạn thực hiện lệnh git merge branch_B, thuật toán cốt lõi của Git phải nhanh chóng tìm ra commit LCA (Merge base) giữa branch hiện tại và branch_B để đối chiếu các dòng code bị thay đổi (Three-way merge).

• Event Bubbling trong DOM (Frontend/Fullstack): Khi tính toán sự kiện nhấp chuột (click event) lan truyền qua cấu trúc HTML, trình duyệt phải xác định node chung gần nhất của các vùng giao thoa để kích hoạt Event Listener hợp lý.

• Truy vấn Khoảng cách trên Cây (Distance on Tree): Khoảng cách từ đỉnh $u$ đến đỉnh $v$ trên bất kỳ cái Cây nào có thể được tính ngay lập tức bằng công thức: $\text{Dist}(u, v) = \text{Depth}(u) + \text{Depth}(v) - 2 \times \text{Depth}(\text{LCA}(u, v))$.

Chúng ta đã chinh phục hoàn toàn các cấu trúc dữ liệu khổng lồ trên Cây. Ở bài học tiếp theo, chúng ta sẽ kết nối lại sức mạnh của Chuỗi và Đồ thị để tạo ra một cỗ máy trạng thái hữu hạn có thể tìm kiếm hàng ngàn từ khóa cùng lúc trong một văn bản.