Bài toán: cho cây tìm kiếm nhị phân T. Yêu cầu chèn khoá v vào cây T sao cho sau khi cho sau khi chèn khoá v thì cây T vẫn là cây tìm kiếm nhị phân. Quan sát, thảo luận, tìm hiểu thuật toán t
Giải thích
Quá trình chèn khoá v = 7 vào cây tìm kiếm nhị phân T ở Hình 7.6a như sau:
Bước 1. Tìm vị trí cần chèn khoá v trên cây T (Hình 7.6b). Khoá v lớn hơn khoá 5, đi đến nút con phải. Khoá y nhỏ khoá 10, đi đến nút con trái. Khoá y nhỏ hơn khoá 8, đi đến nút con trái và gặp nút giả None.
Bước 2. Chèn khoá v vào cây T (Hình 7.6c). Trong trường hợp khoá v không có trong cây T thì chèn khoá v vào cây này bằng cách tạo nút thật mới tại nút giả None và gán khoá y cho nút mới này.
