Treap: BST kết hợp heap và phép xoay
Khám phá cấu trúc lai giữa cây tìm kiếm và heap qua bài toán đa chỉ mục, phép xoay và tìm kiếm.
Trung bìnhCấu trúc dữ liệu ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học cây lai vừa tìm nhanh vừa lấy khẩn. Bạn quản kho tạp hóa 2 tiêu chí.
Kiến thức cần nhớ
Bài toán 2 tiêu chí
- Cần tìm hàng theo tên thật nhanh.
- Cần lấy món sắp hết hàng ngay.
- 1 cấu trúc đơn không cân cả 2.
- Ví dụ đời thường: tìm sách theo tên và theo lượt mượn.
Hai luật trong 1 cây
- Ngang theo tên: trái nhỏ, phải lớn.
- Dọc theo tồn: cha ít hàng hơn con.
- Món cạn nhất luôn nằm ở gốc.
- Ví dụ đời thường: xếp tên A-Z, ai gấp lên trước.
Phép xoay giữ thứ tự
- Xoay nâng con lên làm gốc cây con.
- Thứ tự tên trái-phải vẫn đúng nguyên.
- Quan hệ khẩn cha-con được sửa đúng.
- Ví dụ đời thường: đổi đội trưởng nhưng giữ hàng ngũ.
- Tìm kiếm đi hệt BST, tốn với là chiều cao.
- Ưu tiên theo tồn kho không đảm bảo cây cân bằng: có thể lệch tới . Ưu tiên ngẫu nhiên (ngày 65) mới cho chiều cao kỳ vọng .
| Chiều | Luật | Dùng để gì |
|---|---|---|
| Ngang | Trái nhỏ phải lớn | Tìm theo tên |
| Dọc | Cha khẩn hơn con | Lấy món cạn nhất |
| Xoay | Giữ ngang, sửa dọc | Sửa vi phạm |
Ví dụ
- Input: treap gốc Flour tồn 10, tìm Water. Output: rẽ phải tới đúng nút Water.
- Giải thích: tìm theo tên đi hệt cây tìm kiếm.
💻 Bài tập
Ngôn ngữ: C++. Nộp vào day-029/. Khóa là std::string (tên hàng), ưu tiên là int (số tồn kho). Min-treap: cha có tồn kho nhỏ hơn hoặc bằng con.
Bài 1: Phép xoay và tìm kiếm
struct TNode { std::string key; int priority; TNode *left = nullptr, *right = nullptr; };
TNode *rotateRight(TNode *y); // con trái lên làm gốc
TNode *rotateLeft(TNode *x); // con phải lên làm gốc
TNode *search(TNode *root, const std::string &key);
bool checkBST(const TNode *root);
bool checkHeap(const TNode *root);
Tự dựng tay cây 5 nút vi phạm luật heap ở 1 cạnh. Gọi xoay đúng một lần để sửa. In inorder trước và sau xoay: phải giống nhau.
inorder trước xoay == inorder sau xoay
checkHeap: false trước, true sau
Bài 2: Chèn vào treap
| Hàm | Yêu cầu |
|---|---|
TNode *insert(TNode *root, const std::string &key, int priority) | Chèn như BST rồi xoay ngược lên khi vi phạm heap. Khóa đã có thì cập nhật priority và sửa vị trí |
const TNode *top(const TNode *root) | Món có tồn kho ít nhất (, là gốc) |
int height(const TNode *root) |
insert (Flour,10) (Butter,76) (Water,32) (Sugar,47) (Eggs,9) (Milk,55) (Yeast,5)
-> top = Yeast(5); checkBST && checkHeap = true
search("Water") -> tìm thấy, priority 32
Bài 3: Treap ngẫu nhiên giữ cân bằng (nâng cao)
Dùng treap làm BST cân bằng: priority lấy ngẫu nhiên thay vì tồn kho.
Chèn 1..10^5 theo thứ tự tăng dần vào 2 cây: BST thường (ngày 7) và treap ngẫu nhiên. In chiều cao 2 cây. Chạy 5 seed khác nhau, in chiều cao treap mỗi lần.
Kỳ vọng: BST thường cao 99999; treap cao khoảng 30-45
✅ Tiêu chí hoàn thành
- Test mẫu pass,
checkBSTvàcheckHeapđúng sau mọi thao tác. - Vẽ tay được 1 phép xoay: trước, sau, và các con trỏ đổi.
- Bảng chiều cao Bài 3 có số thật từ 5 seed.
- Sanitizer sạch.
❓ Câu hỏi ôn tập
- Vì sao 1 cấu trúc đơn không đủ cho kho?
- Treap giữ 2 luật nào?
- Xoay để làm gì?
- Tìm kiếm trên treap đi thế nào?
🌕 Bạn đã hoàn thành ngày 29. Làm hết bài tập phía trên rồi sang ngày tiếp theo.