Cây Treap là một loại cây tìm kiếm nhị phân tự cân bằng, kết hợp các tính chất của cây tìm kiếm nhị phân (Binary Search Tree - BST) và heap (đống). Mỗi nút trong cây Treap không chỉ chứa một khóa (key) mà còn có một giá trị ưu tiên (priority) ngẫu nhiên. Treap đảm bảo rằng về mặt khóa, nó tuân theo quy tắc của một cây tìm kiếm nhị phân (khóa con trái nhỏ hơn khóa nút cha, khóa con phải lớn hơn khóa nút cha), và về mặt ưu tiên, nó tuân thủ thuộc tính của một min-heap hoặc max-heap (ví dụ, ưu tiên của nút cha luôn lớn hơn hoặc bằng ưu tiên của các nút con).
1. Tính duy nhất của cấu trúc Treap
Một tính chất quan trọng của cây Treap là nếu tất cả các giá trị ưu tiên (priority) của các nút là duy nhất, thì cấu trúc của cây Treap sẽ là duy nhất, không phụ thuộc vào thứ tự chèn các phần tử. Điều này đảm bảo rằng với cùng một tập hợp khóa và ưu tiên, cây sẽ luôn có hình dạng giống nhau.
2. Vấn đề cân bằng và ưu tiên ngẫu nhiên
Để ngăn chặn cây nhị phân bị thoái hóa thành một danh sách liên kết (linked list) trong trường hợp xấu nhất (ví dụ, khi các phần tử được chèn theo thứ tự tăng dần hoặc giảm dần), Treap sử dụng các giá trị ưu tiên được gán ngẫu nhiên cho mỗi nút. Cách tiếp cận ngẫu nhiên này không đảm bảo cây luôn cân bằng hoàn hảo trong mọi trường hợp, nhưng nó đảm bảo rằng kỳ vọng về độ phức tạp thời gian cho các thao tác chèn, xóa và tìm kiếm là O(log n), nơi n là số lượng nút trong cây. Điều này giúp Treap trở thành một lựa chọn hiệu quả trong nhiều ứng dụng.
3. Cấu trúc dữ liệu nút
Dưới đây là định nghĩa cho một nút trong cây Treap, bao gồm khóa, ưu tiên, và kích thước của cây con mà nút đó làm gốc:
struct NutTreap {
int kichThuocNhanh; // Số lượng nút trong cây con có gốc là nút này
int doUuTien; // Giá trị ưu tiên ngẫu nhiên của nút
int giaTriKhoa; // Giá trị khóa của nút, dùng cho thuộc tính BST
NutTreap *con[2]; // con[0] là con trái (khóa nhỏ hơn), con[1] là con phải (khóa lớn hơn)
// Toán tử so sánh ưu tiên: dùng để xác định thứ tự ưu tiên trong heap.
// Nếu ưu tiên của nút hiện tại nhỏ hơn nút khác, trả về true.
bool operator < (const NutTreap& khac) const {
return doUuTien < khac.doUuTien;
}
// Hàm so sánh giá trị khóa với một giá trị cho trước 'k'.
// Trả về -1 nếu 'k' bằng khóa hiện tại.
// Trả về 0 nếu 'k' nhỏ hơn khóa hiện tại (nên đi xuống con trái).
// Trả về 1 nếu 'k' lớn hơn khóa hiện tại (nên đi xuống con phải).
int soSanhKhoa(int k) const {
if (k == giaTriKhoa) return -1;
return (k < giaTriKhoa) ? 0 : 1;
}
// Cập nhật kích thước của cây con mà nút này làm gốc.
// Kích thước là 1 (chính nút này) cộng với kích thước của các cây con trái và phải (nếu có).
void capNhatKichThuoc() {
kichThuocNhanh = 1;
if (con[0] != nullptr) kichThuocNhanh += con[0]->kichThuocNhanh;
if (con[1] != nullptr) kichThuocNhanh += con[1]->kichThuocNhanh;
}
};
4. Thao tác chèn (Insert)
Khi chèn một nút mới vào cây Treap, quá trình này được thực hiện qua hai bước chính:
Chèn theo thuộc tính BST: Nút mới được chèn vào vị trí thích hợp trong cây dựa trên giá trị khóa của nó, giống như trong một cây tìm kiếm nhị phân thông thường. Điều này đảm bảo rằng thuộc tính BST được duy trì.
Khôi phục thuộc tính Heap: Một giá trị ưu tiên ngẫu nhiên được gán cho nút mới. Sau đó, cây được kiểm tra để đảm bảo rằng thuộc tính heap vẫn đúng. Nếu ưu tiên của nút mới cao hơn ưu tiên của nút cha, nút mới sẽ được "xoay" lên trên (thực hiện các phép quay) để khôi phục thuộc tính heap, cho đến khi nó đạt đến vị trí mà ưu tiên của nó phù hợp với quy tắc heap.
void chenNut(NutTreap*& gocHienTai, int giaTriMoi) {
if (gocHienTai == nullptr) { // Nếu vị trí trống, tạo nút mới
gocHienTai = new NutTreap();
gocHienTai->con[0] = gocHienTai->con[1] = nullptr;
gocHienTai->doUuTien = rand(); // Gán ưu tiên ngẫu nhiên
gocHienTai->giaTriKhoa = giaTriMoi;
gocHienTai->kichThuocNhanh = 1;
} else { // Vị trí không trống, tìm vị trí thích hợp trong cây con
int huong = gocHienTai->soSanhKhoa(giaTriMoi);
// Trong trường hợp giá trị đã tồn tại (huong == -1), có thể không làm gì hoặc cập nhật
// Bài toán này giả định chèn các giá trị duy nhất hoặc chấp nhận trùng lặp.
chenNut(gocHienTai->con[huong], giaTriMoi); // Chèn đệ quy vào cây con
gocHienTai->capNhatKichThuoc(); // Cập nhật kích thước sau khi cây con đã thay đổi
// Kiểm tra và khôi phục thuộc tính heap: nếu ưu tiên của cha nhỏ hơn ưu tiên của con
if (*gocHienTai < *gocHienTai->con[huong]) {
quay(gocHienTai, huong ^ 1); // Thực hiện phép quay ngược hướng chèn
}
}
}
5. Phép quay (Rotation)
Phép quay là một thao tác cơ bản và quan trọng trong các cây tự cân bằng như Treap. Mục đích của phép quay là thay đổi cấu trúc của cây để khôi phục thuộc tính heap (hoặc BST) mà không làm mất đi thuộc tính còn lại. Có hai loại quay: quay trái và quay phải. Trong đoạn mã dưới đây, huongQuay = 0 thường là quay phải và huongQuay = 1 là quay trái.
void quay(NutTreap*& nutGoc, int huongQuay) { // huongQuay = 0: quay phải, huongQuay = 1: quay trái
// huongQuay^1 là hướng ngược lại của huongQuay (ví dụ: 0^1=1, 1^1=0).
// Nếu huongQuay là 0 (quay phải), thì lấy con phải của nutGoc.
// Nếu huongQuay là 1 (quay trái), thì lấy con trái của nutGoc.
NutTreap* nutCon = nutGoc->con[huongQuay ^ 1]; // Lấy nút con sẽ trở thành nút gốc mới
// Nút con của nutGoc (theo hướng ngược lại của huongQuay)
// sẽ nhận cây con của nutCon (theo hướng huongQuay) làm cây con mới của mình.
nutGoc->con[huongQuay ^ 1] = nutCon->con[huongQuay];
// Nút gốc cũ (nutGoc) trở thành con của nút con mới (nutCon) theo hướng huongQuay.
nutCon->con[huongQuay] = nutGoc;
nutGoc->capNhatKichThuoc(); // Cập nhật kích thước của nút gốc cũ
nutCon->capNhatKichThuoc(); // Cập nhật kích thước của nút gốc mới
nutGoc = nutCon; // Nút con trở thành nút gốc mới của cây con hiện tại
}
6. Tìm kiếm phần tử thứ K (theo thứ tự giảm dần) - O(log n)
Hàm này tìm phần tử có giá trị lớn thứ K trong cây. Hạng (rank) được tính từ lớn nhất (hạng 1) đến nhỏ nhất.
int timPhanTuThuK(NutTreap* nutHienTai, int thuTuK) {
// Trả về -1 nếu cây rỗng, thuTuK không hợp lệ (âm hoặc lớn hơn kích thước cây).
if (nutHienTai == nullptr || thuTuK <= 0 || thuTuK > nutHienTai->kichThuocNhanh) {
return -1;
}
// Kích thước của cây con bên phải, chứa các giá trị lớn hơn nút hiện tại.
int kichThuocPhai = (nutHienTai->con[1] == nullptr) ? 0 : nutHienTai->con[1]->kichThuocNhanh;
if (thuTuK == kichThuocPhai + 1) {
// Nếu thuTuK đúng bằng số lượng phần tử lớn hơn nó + 1, thì đây chính là nút hiện tại.
return nutHienTai->giaTriKhoa;
} else if (thuTuK <= kichThuocPhai) {
// Nếu thuTuK nằm trong phạm vi của cây con bên phải, tìm kiếm đệ quy bên phải.
return timPhanTuThuK(nutHienTai->con[1], thuTuK);
} else {
// Nếu thuTuK nằm trong phạm vi của cây con bên trái,
// điều chỉnh thuTuK bằng cách trừ đi số phần tử ở cây con phải và nút hiện tại.
return timPhanTuThuK(nutHienTai->con[0], thuTuK - kichThuocPhai - 1);
}
}
7. Tìm kiếm hạng (Rank) của một giá trị - O(log n)
Hàm này trả về hạng của một giá trị cụ thể trong cây. Hạng 1 là phần tử có giá trị lớn nhất. Hàm này được thiết kế để hoạt động hiệu quả khi giá trị cần tìm được đảm bảo có trong cây. Nếu giá trị không tồn tại, hành vi có thể không được định nghĩa rõ ràng (ví dụ: trả về hạng nếu nó được chèn).
int timHangCuaGiaTri(NutTreap* nutHienTai, int giaTriCanTim) {
// Hàm này giả định 'giaTriCanTim' CÓ MẶT trong cây.
// Do đó, không cần kiểm tra 'nutHienTai == nullptr' khi gọi từ main.
int huongSoSanh = nutHienTai->soSanhKhoa(giaTriCanTim);
// Kích thước của cây con bên phải, chứa các phần tử lớn hơn nút hiện tại.
int kichThuocPhai = (nutHienTai->con[1] == nullptr) ? 0 : nutHienTai->con[1]->kichThuocNhanh;
if (huongSoSanh == -1) { // Giá trị tìm thấy tại nút hiện tại
return kichThuocPhai + 1; // Hạng của nó là số phần tử lớn hơn nó + 1
} else if (huongSoSanh == 1) { // Giá trị cần tìm lớn hơn nút hiện tại, tìm bên phải
return timHangCuaGiaTri(nutHienTai->con[1], giaTriCanTim);
} else { // Giá trị cần tìm nhỏ hơn nút hiện tại, tìm bên trái
// Hạng của giá trị sẽ là hạng tìm được trong cây con trái, cộng với số phần tử lớn hơn nó
// (bao gồm tất cả các phần tử trong cây con phải và chính nút hiện tại).
return timHangCuaGiaTri(nutHienTai->con[0], giaTriCanTim) + kichThuocPhai + 1;
}
}
8. Ví dụ ứng dụng: Tìm phần tử gần nhất (Competitive Programming)
Dưới đây là một ví dụ minh họa cách sử dụng Treap để giải quyết bài toán tìm phần tử có giá trị gần nhất, thường gặp trong các cuộc thi lập trình (ví dụ: HDU 4585). Bài toán yêu cầu chèn các cặp (ID, giá trị) và sau mỗi lần chèn, tìm ra ID của giá trị đã được chèn hoặc ID của giá trị gần nhất với giá trị vừa chèn.
#include <iostream>
#include <cstdio> // Cho scanf, printf
#include <cstdlib> // Cho rand, srand
#include <ctime> // Cho time
#include <map> // Cho std::map
// Sử dụng namespace std để rút gọn code trong môi trường competitive programming
using namespace std;
// Map để lưu ID của mỗi giá trị, cho phép truy xuất ID từ giá trị
map<int, int> danhSachID;
// Định nghĩa cấu trúc nút Treap
struct NutTreap {
int kichThuocNhanh;
int doUuTien;
int giaTriKhoa;
NutTreap *con[2];
bool operator < (const NutTreap& khac) const {
return doUuTien < khac.doUuTien;
}
int soSanhKhoa(int k) const {
if (k == giaTriKhoa) return -1;
return (k < giaTriKhoa) ? 0 : 1;
}
void capNhatKichThuoc() {
kichThuocNhanh = 1;
if (con[0] != nullptr) kichThuocNhanh += con[0]->kichThuocNhanh;
if (con[1] != nullptr) kichThuocNhanh += con[1]->kichThuocNhanh;
}
};
// Hàm quay (rotation)
void quay(NutTreap*& nutGoc, int huongQuay) {
NutTreap* nutCon = nutGoc->con[huongQuay ^ 1];
nutGoc->con[huongQuay ^ 1] = nutCon->con[huongQuay];
nutCon->con[huongQuay] = nutGoc;
nutGoc->capNhatKichThuoc();
nutCon->capNhatKichThuoc();
nutGoc = nutCon;
}
// Hàm chèn nút
void chenNut(NutTreap*& gocHienTai, int giaTriMoi) {
if (gocHienTai == nullptr) {
gocHienTai = new NutTreap();
gocHienTai->con[0] = gocHienTai->con[1] = nullptr;
gocHienTai->doUuTien = rand();
gocHienTai->giaTriKhoa = giaTriMoi;
gocHienTai->kichThuocNhanh = 1;
} else {
int huong = gocHienTai->soSanhKhoa(giaTriMoi);
chenNut(gocHienTai->con[huong], giaTriMoi);
gocHienTai->capNhatKichThuoc();
if (*gocHienTai < *gocHienTai->con[huong]) {
quay(gocHienTai, huong ^ 1);
}
}
}
// Hàm tìm phần tử thứ K (theo thứ tự giảm dần)
int timPhanTuThuK(NutTreap* nutHienTai, int thuTuK) {
if (nutHienTai == nullptr || thuTuK <= 0 || thuTuK > nutHienTai->kichThuocNhanh) {
return -1;
}
int kichThuocPhai = (nutHienTai->con[1] == nullptr) ? 0 : nutHienTai->con[1]->kichThuocNhanh;
if (thuTuK == kichThuocPhai + 1) {
return nutHienTai->giaTriKhoa;
} else if (thuTuK <= kichThuocPhai) {
return timPhanTuThuK(nutHienTai->con[1], thuTuK);
} else {
return timPhanTuThuK(nutHienTai->con[0], thuTuK - kichThuocPhai - 1);
}
}
// Hàm tìm hạng (rank) của một giá trị (hạng 1 là lớn nhất)
int timHangCuaGiaTri(NutTreap* nutHienTai, int giaTriCanTim) {
int huongSoSanh = nutHienTai->soSanhKhoa(giaTriCanTim);
int kichThuocPhai = (nutHienTai->con[1] == nullptr) ? 0 : nutHienTai->con[1]->kichThuocNhanh;
if (huongSoSanh == -1) {
return kichThuocPhai + 1;
} else if (huongSoSanh == 1) {
return timHangCuaGiaTri(nutHienTai->con[1], giaTriCanTim);
} else {
return timHangCuaGiaTri(nutHienTai->con[0], giaTriCanTim) + kichThuocPhai + 1;
}
}
int main() {
int soLuongThaoTac;
// Đọc số lượng thao tác cho đến khi đọc được 0
while (scanf("%d", &soLuongThaoTac) == 1 && soLuongThaoTac != 0) {
srand(time(NULL)); // Khởi tạo bộ sinh số ngẫu nhiên cho ưu tiên
int ID_khoa, giaTri;
scanf("%d %d", &ID_khoa, &giaTri);
// Khởi tạo nút gốc đầu tiên của Treap
NutTreap *cayGoc = new NutTreap();
cayGoc->con[0] = cayGoc->con[1] = nullptr;
cayGoc->doUuTien = rand();
cayGoc->giaTriKhoa = giaTri;
cayGoc->kichThuocNhanh = 1;
danhSachID[giaTri] = ID_khoa; // Lưu ID tương ứng với giá trị
printf("%d %d\n", ID_khoa, 1); // Phần tử đầu tiên luôn có hạng 1
for (int i = 2; i <= soLuongThaoTac; ++i) {
scanf("%d %d", &ID_khoa, &giaTri);
danhSachID[giaTri] = ID_khoa; // Lưu ID cho giá trị mới
chenNut(cayGoc, giaTri); // Chèn giá trị mới vào Treap
int hangCuaGiaTri = timHangCuaGiaTri(cayGoc, giaTri); // Tìm hạng của giá trị vừa chèn
int giaTriLonHonGanNhat = -1; // Giá trị lớn hơn gần nhất
// Nếu giá trị vừa chèn không phải là lớn nhất (hạng 1), thì có phần tử lớn hơn nó
if (hangCuaGiaTri > 1) {
giaTriLonHonGanNhat = timPhanTuThuK(cayGoc, hangCuaGiaTri - 1);
}
int giaTriNhoHonGanNhat = -1; // Giá trị nhỏ hơn gần nhất
// Nếu giá trị vừa chèn không phải là nhỏ nhất (hạng = kích thước cây), thì có phần tử nhỏ hơn nó
if (hangCuaGiaTri < cayGoc->kichThuocNhanh) {
giaTriNhoHonGanNhat = timPhanTuThuK(cayGoc, hangCuaGiaTri + 1);
}
int giaTriGanNhatDeChon;
if (giaTriLonHonGanNhat != -1 && giaTriNhoHonGanNhat != -1) {
// Nếu cả hai láng giềng (lớn hơn và nhỏ hơn) đều tồn tại, chọn cái gần hơn.
// Nếu khoảng cách bằng nhau, ưu tiên giá trị nhỏ hơn.
if (giaTriLonHonGanNhat - giaTri >= giaTri - giaTriNhoHonGanNhat) {
giaTriGanNhatDeChon = giaTriNhoHonGanNhat;
} else {
giaTriGanNhatDeChon = giaTriLonHonGanNhat;
}
} else if (giaTriLonHonGanNhat != -1) {
giaTriGanNhatDeChon = giaTriLonHonGanNhat; // Chỉ có láng giềng lớn hơn
} else { // Chỉ còn trường hợp giaTriNhoHonGanNhat != -1 (vì nếu cả 2 là -1 thì if đầu đã xử lý)
giaTriGanNhatDeChon = giaTriNhoHonGanNhat; // Chỉ có láng giềng nhỏ hơn
}
printf("%d %d\n", ID_khoa, danhSachID[giaTriGanNhatDeChon]);
}
// Để tránh rò rỉ bộ nhớ trong các bài toán lặp đi lặp lại nhiều test case,
// cần giải phóng bộ nhớ của cây Treap (ví dụ: dùng hàm xóa cây đệ quy)
// và xóa sạch map danhSachID. Tuy nhiên, trong nhiều cuộc thi lập trình,
// việc này thường được bỏ qua vì hệ điều hành sẽ tự giải phóng khi chương trình kết thúc.
danhSachID.clear(); // Quan trọng để xóa map cho mỗi test case mới
}
return 0;
}