Trong bài viết này, chúng ta sẽ tìm hiểu về cấu trúc dữ liệu FHQ Treap, một dạng cây cân bằng không sử dụng phép xoay. Thay vào đó, nó dựa trên hai thao tác chính là "phân chia" (split) và "hợp nhất" (merge) để thực hiện các hoạt động trên cây.

Ưu nhược điểm

FHQ Treap không dễ dàng được sử dụng làm cây hỗ trợ cho LCT, nhưng có thể thực hiện tính năng bền vững hóa (persistent). Theo một số nguồn thông tin, FHQ Treap có hằng số nhỏ hơn Splay trong nhiều trường hợp, mặc dù điều này còn phụ thuộc vào cách triển khai cụ thể. Tuy nhiên, mã nguồn của FHQ Treap thường ngắn gọn hơn và dễ hiểu hơn so với Splay, đặc biệt khi cần duy trì tập hợp bằng cây cân bằng.

Thực hiện

Phân chia (Split)

Phương thức cốt lõi của FHQ Treap. Nó tách một cây thành hai phần dựa trên giá trị (k), một phần chứa các nút nhỏ hơn hoặc bằng (k) và phần còn lại chứa các nút lớn hơn (k).

void phanChia(int nutHienTai, int k, int &phanNho, int &phanLon) {
	if (!nutHienTai)	return phanNho = phanLon = 0, void();
	if (giaTri[nutHienTai] <= k)	phanNho = nutHienTai, phanChia(phai[nutHienTai], k, phai[nutHienTai], phanLon);
	else	phanLon = nutHienTai, phanChia(trai[nutHienTai], k, phanNho, trai[nutHienTai]);
	tinhTong(nutHienTai);
}

Hợp nhất (Merge)

Một thao tác tương tự như việc hợp nhất cây đoạn (segment tree) hoặc cây thiên vị trái (leftist heap).

int hopNhat(int phanNho, int phanLon) {
	if (!phanNho || !phanLon)	return phanNho ^ phanLon;
	int p = 0;
	if (ngauNhien[phanNho] > ngauNhien[phanLon])	phai[phanNho] = hopNhat(phai[phanNho], phanLon), p = phanNho;
	else	trai[phanLon] = hopNhat(phanNho, trai[phanLon]), p = phanLon;
	tinhTong(p);
	return p;
}

Các thao tác khác

Các hoạt động khác hầu hết đều dựa trên việc sử dụng linh hoạt split và merge. Một số hàm cơ bản như tạo nút mới, thêm và xóa nút cũng được triển khai.

inline int taoNutMoi(int giaTriMoi) {
	int nutMoi = ++soNutToiDa;
	giaTri[nutMoi] = giaTriMoi; kichThuoc[nutMoi] = 1; trai[nutMoi] = phai[nutMoi] = 0;
	ngauNhien[nutMoi] = rand();
	return nutMoi;
}

inline void them(int giaTriCanThem) {
	int nutMoi = taoNutMoi(giaTriCanThem);
	int A = 0, B = 0;
	phanChia(goc, giaTriCanThem, A, B);
	goc = hopNhat(hopNhat(A, nutMoi), B);
}

Vấn đề mẫu

P3369: Cây cân bằng cơ bản

Đây là bài mẫu, không cần giải thích thêm.

P3835: Cây cân bằng bền vững hóa

Bền vững hóa là một lợi thế của FHQ Treap so với Splay. Để đạt được điều này, hãy sao chép trước khi sửa đổi bất kỳ nút nào.

int phienBanHienTai;
int trai[NN], phai[NN], giaTri[NN], ngauNhien[NN], kichThuoc[NN], goc[N], soNutToiDa;

inline int saoChep(int nutHienTai) {
	if (!nutHienTai)	return 0;
	int p = ++soNutToiDa;
	giaTri[p] = giaTri[nutHienTai], trai[p] = trai[nutHienTai], phai[p] = phai[nutHienTai], kichThuoc[p] = kichThuoc[nutHienTai];
	ngauNhien[p] = ngauNhien[nutHienTai];
	return p;
}

P3987: Yêu thích mãi mãi

FHQ Treap cũng có thể hỗ trợ các hoạt động bảo trì chuỗi, nhờ vào việc sử dụng linh hoạt các thao tác split và merge cùng với lazy tag.

Sai lầm đã từng mắc phải

Sai lầm 1

int layGiaTri(int nutHienTai, int thuTu) {
	if (kichThuoc[trai[nutHienTai]] == thuTu - 1)	return nutHienTai;
	if (thuTu - 1 < kichThuoc[trai[nutHienTai]])	return layGiaTri(trai[nutHienTai], thuTu);
	return layGiaTri(phai[nutHienTai], thuTu - kichThuoc[trai[nutHienTai]] - 1);
}