Treap nâng cao: insert, delete và cân bằng kỳ vọng

Giới thiệu

Bài này học chèn xóa treap bằng xoay. Bạn dùng nó để giữ cây cân bằng khi dữ liệu vào xấu.

Kiến thức cần nhớ

Chèn: đặt lá rồi xoay lên

• Bước 1: đặt nút mới như lá theo luật cây tìm kiếm.
• Bước 2: nếu ưu tiên vượt cha thì xoay đẩy lên.
• Không đổi chỗ trực tiếp vì sẽ phá thứ tự khóa.
• Ví dụ đời thường: như nhân viên mới giỏi được thăng chức dần lên trên.

Xóa: dìm xuống lá rồi gỡ

• Muốn xóa nút trong thì xoay dìm nó xuống dần.
• Khi thành lá thì gỡ thẳng.
• Nút lá gỡ ngay không cần xoay.
• Ví dụ đời thường: như đẩy người cần rời xuống cuối hàng rồi mời ra.

# Ý tưởng chèn / xóa treap
# chèn: đặt lá theo khóa -> while ưu_tiên_con > ưu_tiên_cha: xoay(cha)
# xóa: while nút chưa là lá: xoay với con mạnh hơn -> gỡ lá

Treap ngẫu nhiên

• Định nghĩa: mỗi khóa rút 1 số ngẫu nhiên làm ưu tiên.
• Hình dạng cây do số ngẫu nhiên quyết định.
• Kẻ tấn công không đoán được dãy nào gây lệch.
• Ví dụ đời thường: như bốc thăm chỗ ngồi, không ai xếp được phe cánh.

Chiều cao kỳ vọng và ứng dụng

• Chiều cao trung bình là logarit theo số nút.
• Chỉ đảm bảo trung bình, không đảm bảo mọi cây cụ thể.
• Dùng mọi nơi cần từ điển có thứ tự mà chống tấn công.
• Ví dụ đời thường: quản lý gói tin IP, bảng băm dễ bị dồn xô còn treap thì khó.

Ví dụ

• Input: chèn nút ưu tiên thấp nhất. Output: nằm yên làm lá, không xoay.
• Giải thích: ưu tiên thấp thì không vượt cha nào cả.
• Input: chèn dãy đã sắp vào BST thuần và treap ngẫu nhiên. Output: BST cao như danh sách, treap thấp hơn hẳn.
• Giải thích: số ngẫu nhiên phá được đòn sắp xếp sẵn.

💻 Bài tập

Ngôn ngữ: C++. Dùng tiếp code ngày 29. Nộp vào day-065/. Treap dùng làm từ điển có thứ tự, priority ngẫu nhiên, max-heap theo priority.

Bài 1: Chèn và xóa đầy đủ

class Treap {
 public:
  explicit Treap(uint64_t seed);
  bool insert(int key);             // trả false nếu đã có
  bool erase(int key);              // xoay dìm nút xuống tới lá rồi gỡ
  bool contains(int key) const;
  size_t size() const; int height() const;
  bool check() const;               // BST + heap
};

insert 1..1000 tăng dần  -> check = true, height < 40
erase mọi số chẵn        -> size 500, check = true
erase(5000)              -> false

Viết test ngẫu nhiên: 10^5 thao tác insert/erase/contains trộn lẫn, so với std::set sau mỗi thao tác.

Bài 2: Split và merge

Viết lại insert và erase chỉ bằng split + merge. Kết quả phải giống Bài 1.

Bài 3: Thống kê thứ tự (nâng cao)

Mỗi nút lưu thêm size của cây con.

1. int kth(int k): khóa nhỏ thứ k (từ 1).
2. int rank(int key): số khóa nhỏ hơn key.
3. int countRange(int lo, int hi): số khóa trong [lo, hi].

khóa {10, 20, 30, 40, 50}: kth(2) = 20, rank(35) = 3, countRange(15, 45) = 3

Đo thời gian 10^6 thao tác trộn lẫn so với std::set (không có kth).

✅ Tiêu chí hoàn thành

• Test ngẫu nhiên so với std::set pass.
• Bản split/merge cho cùng kết quả bản xoay.
• kth, rank, countRange đúng, $O(\log n)$ kỳ vọng.
• Giải thích được vì sao priority ngẫu nhiên chống được dãy chèn xấu.

❓ Câu hỏi ôn tập

• Chèn treap gồm mấy bước?
• Xóa nút trong treap làm thế nào?
• Treap ngẫu nhiên gán ưu tiên bằng gì?
• Vì sao treap chống được dãy sắp sẵn?

🌕 Bạn đã hoàn thành ngày 65. Làm hết bài tập phía trên rồi sang ngày tiếp theo.