Cây và binary search tree: thuật ngữ và bất biến

Giới thiệu

Bài này học từ vựng cây và cây tìm kiếm. Bạn dùng nó cho heap và treap sau này.

Kiến thức cần nhớ

Từ vựng cây

• Gốc là nút duy nhất không có cha.
• Lá là nút không có con nào.
• Anh em là 2 nút cùng cha.
• Ví dụ đời thường: cây gia phả có ông bà con cháu.
• Bậc của nút là số con trực tiếp.

Cây nhị phân và BST

• Cây nhị phân mỗi nút tối đa 2 con.
• BST thêm luật: trái nhỏ hơn, phải lớn hơn.
• Luật này đúng với mọi nút trong cây.
• Ví dụ đời thường: tủ hồ sơ xếp trái nhỏ phải lớn.
• Tìm kiếm thì so sánh rồi rẽ trái hoặc phải.

Cây lệch và cân bằng

• Chèn tăng dần tạo cây nghiêng như list.
• Cây lệch tìm kiếm tốn $O(n)$.
• Cây cân bằng tìm kiếm tốn $O(log n)$.
• Ví dụ đời thường: thang thẳng đứng và thang rộng.

Ví dụ

• Input: BST gốc 10, trái 5, phải 15, tìm 7. Output: thăm 10, 5 rồi báo không thấy.
• Giải thích: nhỏ hơn thì rẽ trái, lớn hơn thì rẽ phải.

💻 Bài tập

Ngôn ngữ: C++ (hoặc C). Nộp vào day-007/. Khóa là int, không trùng.

Bài 1: BST cơ bản

struct Node { int key; Node *left = nullptr, *right = nullptr; };
class BST {
 public:
  bool insert(int key);         // trả false nếu key đã có
  bool contains(int key) const;
  int  height() const;          // cây rỗng = -1, 1 nút = 0
  size_t size() const;
  std::vector<int> inorder() const;
  ~BST();                       // giải phóng mọi nút
};

insert 10, 5, 15, 3, 7, 12, 20  -> inorder = [3,5,7,10,12,15,20], height=2
insert 7 lần nữa                 -> false, size vẫn 7
contains(12) / contains(8)       -> true / false

Bài 2: Kiểm tra BST và đường tìm

1. Viết bool isBST(const Node *root). Mỗi nút phải nằm trong khoảng (min, max) do tổ tiên quy định, không chỉ so với con trực tiếp.
2. Viết std::vector<int> searchPath(int key) trả dãy khóa đã thăm.

Cây: 10 (trái 5 (phải 12), phải 15)   -> isBST = false (12 nằm bên trái 10)
Cây Bài 1, searchPath(8)               -> [10, 5, 7]
Cây Bài 1, searchPath(20)              -> [10, 15, 20]

Bài 3: Cây lệch và cây cân (nâng cao)

1. Chèn 1..1000 theo thứ tự tăng. In height().
2. Chèn cùng tập khóa theo thứ tự "giữa trước": viết void insertBalanced(std::vector<int> &sorted, int l, int r) chèn phần tử giữa rồi đệ quy hai nửa. In height().
3. Chèn 1000 khóa theo thứ tự ngẫu nhiên (seed cố định). In height().
4. Đo thời gian 10^5 lần contains ngẫu nhiên trên cả 3 cây.

Kỳ vọng: tăng dần -> height = 999; giữa trước -> height = 9; ngẫu nhiên -> khoảng 20

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

• Test mẫu pass, inorder luôn tăng dần.
• isBST bắt được ca vi phạm ở cháu, không chỉ ở con.
• Bảng chiều cao và thời gian của Bài 3 có số thật.
• Sanitizer sạch, destructor giải phóng hết nút.

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

• Gốc, lá, anh em là gì?
• BST khác cây nhị phân thường ở đâu?
• Tìm kiếm trên BST đi thế nào?
• Vì sao cây lệch lại chậm?

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