Cấu trúc dữ liệu và Giải thuật Bài 114: Cây liên kết cắt (Link-Cut Tree) - Quản lý động các cây thay đổi cấu trúc liên tục.

Trong các bài toán xử lý cây tĩnh, chúng ta đã có Heavy-Light Decomposition (HLD) hoặc Binary Lifting để giải quyết các truy vấn trên đường đi (Path Queries) với độ phức tạp $O(\log^2 N)$ hoặc $O(\log N)$. Tuy nhiên, các cấu trúc này có một tử huyệt: Cấu trúc của cây phải hoàn toàn tĩnh (không đổi).

Ngay khi hệ thống yêu cầu thêm một cạnh mới (link) hoặc xóa một cạnh cũ (cut) liên tục theo thời gian thực — chẳng hạn như quản lý mạng lưới định tuyến động, cập nhật liên kết trong biểu đồ mạng phân tán, hay các bài toán đồ thị động (Dynamic Graph Connectivity) — HLD sẽ hoàn toàn bất lực vì chi phí xây dựng lại (rebuild) mất $O(N)$.

Để chinh phục đỉnh cao cấu trúc dữ liệu này, Link-Cut Tree (LCT) do Daniel Sleator và Robert Tarjan phát minh chính là "vũ khí tối thượng" cho phép thao tác trên các cây động (Dynamic Trees) với độ phức tạp chỉ $O(\log N) amortized cho mọi thao tác.

1. Bản chất của Link-Cut Tree

Link-Cut Tree là sự kết hợp thiên tài giữa hai khái niệm:

1. Cây đại diện đường đi (Preferred Paths Decomposition): Thay vì giữ nguyên cấu trúc phân cấp phức tạp của cây, LCT phân rã cây thành một tập hợp các đường đi rời rạc gọi là Preferred Paths.

2. Splay Tree: Mỗi đường đi này được quản lý bởi một Splay Tree — một cây tìm kiếm nhị phân tự cân bằng có khả năng đưa một nút lên gốc thông qua phép xoay (splay), giúp giữ chiều cao cây luôn ở mức logarit.

Nhờ cấu trúc này, LCT có thể thực hiện 4 thao tác cốt lõi:

• access(v): Đưa đường đi từ gốc của cây lớn đến nút $v$ thành một đường đi liền mạch duy nhất (Preferred Path). Đây là thao tác nền tảng cho mọi tính năng khác.

• link(v, w): Nối cây chứa $v$ vào cây chứa $w$ bằng một cạnh mới.

• cut(v): Cắt đứt cạnh phía trên của nút $v$, tách cây thành hai phần.

• evert(v): Đảo ngược gốc của cây để $v$ trở thành gốc mới (Root of the represented tree).

2. Các thao tác cốt lõi trong LCT

A. Phép access(v)

Thao tác này làm cho $v$ và tất cả các nút trên đường đi từ gốc đến $v$ nằm chung trong một Splay Tree. Khi ta gọi access(v), các đường đi cũ bị ngắt kết nối và thay thế bằng đường đi mới trực tiếp đến $v$.

B. Phép evert(v) (Make Root)

Để thay đổi gốc của cây thành $v$, ta gọi access(v), sau đó splay(v). Cuối cùng, thực hiện đảo ngược thứ tự các nút trong Splay Tree bằng cơ chế Lazy Propagation (tương tự như đảo ngược mảng).

C. Phép link(v, w)

Nối cây chứa $v$ vào $w$:

1. Chuyển $v$ thành gốc (evert(v)).

2. Thiết lập cha của $v$ thành $w$.

D. Phép cut(v)

Cắt đứt cạnh nối giữa $v$ và cha trực tiếp của nó:

1. Gọi access(v) và splay(v).

2. Ngắt liên kết con trái của $v$ trong Splay Tree.

3. Hiện thực hóa Link-Cut Tree cơ bản bằng Golang

Đoạn code Golang dưới đây cài đặt bộ khung cốt lõi của một Link-Cut Tree, bao gồm cấu trúc nút Splay Tree, phép access, splay, evert, link và cut:

Go

package main

import (
	"fmt"
)

type Node struct {
	ch      [2]*Node // Con trái (0) và con phải (1)
	p       *Node    // Cha trong Splay Tree
	rev     bool     // Cờ lật ngược (Lazy Propagation cho evert)
}

// Kiểm tra xem nút có phải là gốc của Splay Tree hiện tại không
func (x *Node) isRoot() bool {
	return x.p == nil || (x.p.ch[0] != x && x.p.ch[1] != x)
}

// Đẩy cờ lật ngược xuống các con (Lazy Push)
func (x *Node) pushDown() {
	if x.rev {
		x.ch[0], x.ch[1] = x.ch[1], x.ch[0]
		if x.ch[0] != nil {
			x.ch[0].rev = !x.ch[0].rev
		}
		if x.ch[1] != nil {
			x.ch[1].rev = !x.ch[1].rev
		}
		x.rev = false
	}
}

// Đẩy toàn bộ cờ từ trên gốc xuống đến x trước khi splay
func (x *Node) pushAll() {
	if !x.isRoot() {
		x.p.pushAll()
	}
	x.pushDown()
}

// Phép xoay cơ bản trong Splay Tree (Rotate)
func (x *Node) rotate() {
	p := x.p
	g := p.p
	dir := 0
	if p.ch[1] == x {
		dir = 1
	}

	if !p.isRoot() {
		if g.ch[0] == p {
			g.ch[0] = x
		} else {
			g.ch[1] = x
		}
	}
	x.p = g

	p.ch[dir] = x.ch[1-dir]
	if x.ch[1-dir] != nil {
		x.ch[1-dir].p = p
	}

	x.ch[1-dir] = p
	p.p = x
}

// Splay đưa nút x lên gốc của Splay Tree hiện tại
func (x *Node) splay() {
	x.pushAll()
	for !x.isRoot() {
		p := x.p
		g := p.p
		if !p.isRoot() {
			if (g.ch[0] == p) == (p.ch[0] == x) {
				p.rotate()
			} else {
				x.rotate()
			}
		}
		x.rotate()
	}
}

// Phép access: Đưa đường đi từ gốc đến x thành một Preferred Path
func (x *Node) access() {
	for t := (*Node)(nil); x != nil; t, x = x, x.p {
		x.splay()
		x.ch[1] = t
	}
}

// Đổi gốc của cây thành x (Evert)
func (x *Node) evert() {
	x.access()
	x.splay()
	x.rev = !x.rev
}

// Nối cây chứa v vào w
func Link(v, w *Node) {
	v.evert()
	v.access()
	v.p = w
}

// Cắt đứt cạnh phía trên của v
func Cut(v *Node) {
	v.access()
	v.splay()
	if v.ch[0] != nil {
		v.ch[0].p = nil
		v.ch[0] = nil
	}
}

func main() {
	// Khởi tạo các nút trong Link-Cut Tree
	nodes := make([]*Node, 5)
	for i := range nodes {
		nodes[i] = &Node{}
	}

	// 1. Nối các cạnh: 0-1, 1-2, 2-3
	Link(nodes[0], nodes[1])
	Link(nodes[1], nodes[2])
	Link(nodes[2], nodes[3])

	fmt.Println("Đã khởi tạo và liên kết cấu trúc cây động thành công bằng Link-Cut Tree.")

	// 2. Cắt đứt liên kết giữa 1 và 2
	Cut(nodes[2])
	fmt.Println("Đã thực hiện cắt đứt (Cut) thành công giữa các nút.")
}

4. Ứng dụng thực tế

• Định tuyến mạng động (Dynamic Network Routing): Cập nhật liên kết cáp quang hoặc tuyến truyền dẫn liên tục khi các trạm chuyển mạch bật/tắt, giúp kiểm tra nhanh tính liên thông giữa hai nút bất kỳ trong thời gian thực.

• Thuật toán Spanning Tree động: Duy trì cây khung nhỏ nhất (Dynamic Minimum Spanning Tree) khi trọng số các cạnh thay đổi hoặc khi có cạnh mới được thêm vào đồ thị.

Link-Cut Tree là đỉnh cao của sự linh hoạt trong cấu trúc dữ liệu, cho phép cấu trúc cây biến hóa khôn lường mà vẫn duy trì độ phức tạp logarit cực kỳ hiệu quả.