Cho dãy số: 10, 6, 17, 3, 1, 5, 8, 9, 7, 15, 21, 19, 25
a. Vẽ cây nhị phân tìm kiếm cân bằng (AVL) tạo thành khi nhập lần lượt các số ở dãy trên.
b. Vẽ lại cây AVL khi xóa node có key 8.
Trả lời:
Đáp án đúng:
Câu hỏi này yêu cầu thực hiện hai thao tác trên cây nhị phân tìm kiếm cân bằng (AVL): chèn một dãy số và sau đó xóa một phần tử. Để trả lời, cần thực hiện các bước sau:
**Phần a: Chèn các số vào cây AVL.**
Ta sẽ chèn lần lượt các số vào cây và thực hiện các phép quay (LL, RR, LR, RL) khi cần thiết để duy trì tính cân bằng (hiệu độ cao giữa hai cây con của mỗi nút không quá 1).
1. **Chèn 10:** Cây có gốc là 10.
2. **Chèn 6:** 6 < 10, đặt 6 làm con trái của 10. Cây cân bằng.
3. **Chèn 17:** 17 > 10, đặt 17 làm con phải của 10. Cây cân bằng.
4. **Chèn 3:** 3 < 6, đặt 3 làm con trái của 6. Nút 10 mất cân bằng (hệ số cân bằng +2). Thực hiện phép quay Right trên 10. Cây mới có gốc là 6, con trái là 3, con phải là 10. Con phải của 10 là 17.
5. **Chèn 1:** 1 < 3, đặt 1 làm con trái của 3. Nút 10 mất cân bằng (hệ số cân bằng +2). Nút 6 mất cân bằng (hệ số cân bằng +2). Thực hiện phép quay Right trên 6. Cây mới có gốc là 3, con trái là 1, con phải là 6. Con phải của 6 là 10, con phải của 10 là 17.
6. **Chèn 5:** 5 > 3 và 5 < 6, đặt 5 làm con phải của 3. Nút 10 mất cân bằng (hệ số cân bằng -2). Nút 6 mất cân bằng (hệ số cân bằng -2). Thực hiện phép quay Left trên 10. Sau đó, nút 6 mất cân bằng (hệ số cân bằng -2). Thực hiện phép quay Left trên 6. Cây có gốc là 5, con trái là 3 (con trái là 1), con phải là 6 (con phải là 10, con phải của 10 là 17).
7. **Chèn 8:** 8 > 6 và 8 < 10, đặt 8 làm con trái của 10. Nút 10 mất cân bằng (hệ số cân bằng -2). Thực hiện phép quay Left trên 10. Cây có gốc là 8, con trái là 6 (con trái là 5, con trái của 5 là 3, con trái của 3 là 1), con phải là 17 (con trái là 15, con phải là 21).
8. **Chèn 9:** 9 > 8 và 9 < 10, đặt 9 làm con phải của 10. Nút 17 mất cân bằng (hệ số cân bằng +2). Nút 10 mất cân bằng (+2). Thực hiện phép quay Right trên 10. Cây có gốc là 9, con trái là 8 (con trái là 6, con trái của 6 là 5, con trái của 5 là 3, con trái của 3 là 1), con phải là 17 (con trái là 15, con phải là 21).
9. **Chèn 7:** 7 > 6 và 7 < 8, đặt 7 làm con phải của 6. Nút 10 mất cân bằng (-2). Nút 17 mất cân bằng (-2). Thực hiện phép quay Left trên 17. Cây có gốc là 9, con trái là 8 (con trái là 6, con trái của 6 là 5, con trái của 5 là 3, con trái của 3 là 1, con phải của 6 là 7), con phải là 15.
10. **Chèn 15:** 15 > 9 và 15 < 17, đặt 15 làm con trái của 17. Nút 17 mất cân bằng (+2). Nút 9 mất cân bằng (+2). Thực hiện phép quay Right trên 9. Cây có gốc là 15, con trái là 8 (con trái là 6, con trái của 6 là 5, con trái của 5 là 3, con trái của 3 là 1, con phải của 6 là 7), con phải là 17 (con trái là 16, con phải là 21).
11. **Chèn 21:** 21 > 15 và 21 > 17, đặt 21 làm con phải của 17. Nút 17 mất cân bằng (-2). Nút 15 mất cân bằng (-2). Thực hiện phép quay Left trên 17. Cây có gốc là 15, con trái là 8 (...), con phải là 21 (con trái là 17, con phải là 25).
12. **Chèn 19:** 19 > 17 và 19 < 21, đặt 19 làm con trái của 21. Nút 21 mất cân bằng (+2). Nút 17 mất cân bằng (+2). Thực hiện phép quay Right trên 21. Cây có gốc là 15, con trái là 8 (...), con phải là 19 (con trái là 17, con phải là 21, con phải của 21 là 25).
13. **Chèn 25:** 25 > 19 và 25 > 21, đặt 25 làm con phải của 21. Nút 19 mất cân bằng (-2). Nút 15 mất cân bằng (-2). Thực hiện phép quay Left trên 19. Cây có gốc là 15, con trái là 8 (...), con phải là 21 (con trái là 19, con trái của 19 là 17, con phải của 21 là 25).
**Phần b: Xóa node có key 8.**
Sau khi cây AVL được hình thành từ phần a, ta tiến hành xóa nút 8. Việc xóa một nút có thể làm mất cân bằng cây.
* Tìm nút 8. Nút 8 là con trái của nút 9.
* Vì 8 có hai con (là 6 và 7), ta tìm phần tử nhỏ nhất ở cây con bên phải của 8, đó là 6. Tuy nhiên, 6 có con phải là 7. Do đó, ta sẽ tìm phần tử nhỏ nhất ở cây con bên phải của 8. Tìm cây con bên phải của 8: nút 9. Cây con bên phải của 8 là cây con của 9. Phần tử nhỏ nhất ở cây con bên phải của 8 không tồn tại vì 8 không có cây con bên phải trực tiếp. Theo quy tắc xóa, nếu nút có hai con, ta thay thế nó bằng phần tử nhỏ nhất của cây con bên phải (hoặc lớn nhất của cây con bên trái).
Để chính xác hơn, ta tìm phần tử nhỏ nhất ở cây con bên phải của 8. Cây con bên phải của 8 bắt đầu từ 9. Cây con bên phải của 8 là: 9 (con trái là 7), 15, 17, 19, 21, 25. Phần tử nhỏ nhất là 7.
Thay thế 8 bằng 7. Sau đó xóa 7 khỏi vị trí ban đầu.
* Ban đầu, cây có gốc là 15. Cây con trái của 15 là 8 (con trái 6, con trái 5, con trái 3, con trái 1, con phải 7), con phải là 21 (con trái 19, con trái 17, con phải 25).
* Ta xóa 8, thay thế nó bằng phần tử nhỏ nhất của cây con bên phải của 8. Cây con bên phải của 8 không tồn tại. Cây con bên trái của 8 có 6 (con trái 5, con trái 3, con trái 1) và 7 (con phải của 6).
Quy tắc xóa: Nếu nút cần xóa có hai con, thay thế nút đó bằng phần tử nhỏ nhất của cây con bên phải của nó. Phần tử nhỏ nhất của cây con bên phải của 8 là 9. Tuy nhiên, 9 không phải là con trực tiếp của 8.
Trong trường hợp này, ta tìm phần tử nhỏ nhất của cây con bên phải của 8. Cây con bên phải của 8 là cây con của 9. Do đó ta tìm phần tử nhỏ nhất của cây con của 9. Cây con của 9 bao gồm 7. Vậy ta thay 8 bằng 7.
Sau khi xóa 8, cây có thể mất cân bằng. Cần kiểm tra và thực hiện các phép quay nếu cần.
**Cây AVL cuối cùng sau khi chèn:** Gốc 15. Con trái: 6 (con trái 5, con trái 3, con trái 1, con phải 7). Con phải: 21 (con trái 19, con trái 17, con phải 25).
**Xóa 8:** Nút 8 không còn trong cây. Cây sẽ có cấu trúc mới và có thể cần cân bằng lại.
Do yêu cầu là vẽ, nên đáp án sẽ là hình ảnh của cây.
* **Sau khi chèn:** Gốc 15. Con trái: 6 (con trái 5, con trái 3, con trái 1, con phải 7). Con phải: 21 (con trái 19, con trái 17, con phải 25).
* **Sau khi xóa 8:** Nút 8 không còn. Ta tìm phần tử nhỏ nhất ở cây con bên phải của 8. Cây con bên phải của 8 là cây con bắt đầu từ 9. Cây con này bao gồm 7. Vì vậy, 7 sẽ thay thế 8. Sau đó, ta xóa 7 khỏi vị trí cũ. Cây có gốc là 15. Cây con trái của 15 là 6 (con trái 5, con trái 3, con trái 1, con phải 7). Cây con phải của 15 là 21 (con trái 19, con trái 17, con phải 25). Cây vẫn cân bằng.
Đề thi kết thúc học phần môn Cấu trúc dữ liệu và giải thuật, bao gồm các câu hỏi về thuật toán sắp xếp Shell sort, cây AVL, hàm băm với các phương pháp giải quyết đụng độ, và ứng dụng cây nhị phân tìm kiếm (BST) để quản lý thông tin bàn trong một quán cà phê.
4 câu hỏi 90 phút
