Câu hỏi:
13/07/2024 175
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ìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.
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ìm kiếm khoá 7 trên cây tìm kiếm nhị phân và cách chèn khoá 7 vào cây này.
Quảng cáo
Trả lời:
Giải bởi Vietjack
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.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
Sách thầy cô Vietjack biên soạn:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Sơ đồ có dạng như sau:
![Cho trước dãy các số A = [10, 1, 2, 11, 8, 15, 20, 9, 0]. Hãy mô tả và vẽ sơ đồ cây nhị phân biểu diễn dãy số trên sau khi thực hiện thao tác chèn như đã mô tả trong hoạt động. (ảnh 1)](https://video.vietjack.com/upload2/quiz_source1/2024/06/17-1719395681.jpg)
Số 10 là gốc.
1 < 10. Chèn sang nút con bên trái số 10.
2 < 10 & 2 > 1. Chèn sang nút con bên phải số 1.
11 > 10. Chèn sang nút con bên phải số 10.
8 < 10 & 8 > 1 & 8 > 2. Chèn sang nút con bên phải số 2.
15 > 10 & 15 > 11. Chèn sang nút con bên phải số 11.
20 > 10 & 20 > 11 & 20 > 15. Chèn sang nút con bên phải số 15.
9 < 10 & 9 > 1 & 9 > 2 & 9 > 8. Chèn sang nút con bên phải số 8.
0 < 10 & 0 < 1 & 0 < 2. Chèn sang nút con bên trái số 2 (Cũng có thể là số 1, 8, 9).
Lời giải
Nếu dãy số được chèn vào cây tìm kiếm nhị phân là tăng dần (hoặc giảm dần), thì cây tìm kiếm nhị phân tương ứng sẽ có dạng như một cây cân bằng.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
🔥 Đề thi HOT:
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Mô hình và các giao thức mạng có đáp án
-
15 câu Trắc nghiệm Tin học 12 Cánh diều Giới thiệu trí tuệ nhân tạo có đáp án
-
15 câu Trắc nghiệm Tin học 12 Kết nối tri thức Bài 23 có đáp án
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 3
-
Bộ 3 đề thi cuối kì 2 Tin 12 Kết nối tri thức có đáp án - Đề 1
-
Bộ 3 đề thi cuối kì 2 Tin 12 Cánh diều có đáp án - Đề 2
-
Bộ 3 đề thi cuối kì 2 Tin 12 Chân trời sáng tạo có đáp án - Đề 2