Mọi nút đều phải thỏa cùng điều kiện
Cây tìm kiếm nhị phân (BST) trong phần cơ bản có các khóa khác nhau từng đôi. Tại mỗi nút, **mọi khóa trong cây con trái nhỏ hơn khóa nút ấy; mọi khóa trong cây con phải lớn hơn**. Điều kiện áp dụng ở tất cả các nút.
Cây mẫu [8,4,12,2,6,10,14] là BST. So với gốc 8, cả 4,2,6 đều nhỏ hơn; cả 12,10,14 đều lớn hơn. Trong cây con gốc 4, lại có 2<4<6.
Cây nhị phân chỉ giới hạn số con; BST còn giới hạn cách sắp khóa. Một cây hoàn chỉnh chưa chắc là BST, và một BST chưa chắc hoàn chỉnh.
Con trực tiếp đúng chưa đủ
Xét `T=[8,4,12,None,9]`. Hai con trực tiếp của gốc thỏa 4<8<12. Nút 9 là con phải của 4 nên cũng thỏa 4<9. Tuy nhiên 9 nằm trong **cây con trái của 8** mà 9>8. Vì vậy cây này không phải BST.
Muốn kiểm bằng sơ đồ, xét cả vùng giá trị mà mỗi nhánh được phép chứa. Nhánh phải của 4 nằm trong nhánh trái của 8 nên mọi khóa ở đó phải đồng thời lớn hơn 4 và nhỏ hơn 8.
Thứ tự chèn ảnh hưởng hình dáng
Chèn 8,4,12 tạo cây có gốc 8 và hai con 4,12. Chèn cùng ba khóa theo thứ tự 4,8,12 tạo một nhánh phải từ 4 đến 8 rồi 12. Cả hai đều là BST nhưng chiều cao khác nhau.
Cây suy biến chỉ còn một đường đi qua các nút, có thể làm tìm kiếm phải qua gần hết cây. Cây có chiều cao nhỏ giúp giảm số nút cần xét trên một đường tìm; thao tác chèn thông thường không tự cân bằng cây.
Bài luyện
Vì sao [8,4,12,None,9] không phải BST khóa khác nhau?
BST không yêu cầu gốc nhỏ nhất.
Hình dáng hoàn hảo không phải điều kiện BST.
Con phải phải lớn hơn 4.
Đúng. Vi phạm điều kiện với toàn bộ cây con trái.
Lời giải
9 ở chỉ số 4, là con phải của 4 thuộc nhánh trái của gốc 8. Do đó cần 4<9<8, điều không thỏa. Chỉ kiểm 4<8<12 và 4<9 sẽ bỏ sót lỗi này.
Bài luyện
Khẳng định nào đúng với BST cơ bản trong bài?
Một nút có thể có 0,1 hoặc 2 con.
Đúng. Điều kiện áp dụng tại từng nút.
Mảng ghi theo vị trí, không phải thứ tự sắp khóa.
Cây hoàn chỉnh chỉ là điều kiện hình dáng.
Lời giải
BST khóa khác nhau phải thỏa điều kiện nhỏ hơn ở toàn bộ cây con trái và lớn hơn ở toàn bộ cây con phải của mỗi nút. Số con và việc ghi mảng không tự bảo đảm điều kiện này.
Bài luyện
Chèn lần lượt 4,8,12 vào BST rỗng tạo hình dáng nào?
Gốc được tạo bởi khóa chèn đầu tiên là 4.
12 không phải khóa đầu.
Đúng. Mỗi khóa sau lớn hơn các khóa đã đi qua.
Khóa lớn hơn đi sang phải.
Lời giải
4 tạo gốc. 8>4 nên làm con phải của 4. 12>4 rồi 12>8 nên làm con phải của 8. Không có bước tự đổi gốc hoặc cân bằng.
Đang học