Để việc tìm kiếm thông tin mặt hàng được nhanh chóng, người ta dùng một bảng băm theo phương pháp thăm dò, làm việc trên mã quản lý của mặt hàng. Mã quản lý này là một con số nguyên. Bảng băm có:
- Hàm băm: h(key) = (key % M)
- Hàm băm lại (hàm thăm dò): prob(key, i) = (h(key) + i*i + i) % M
Trong đó:
- key là giá trị khóa.
- i là một số nguyên cho biết lần băm lại (thăm dò) thứ i.
- M là kích thước bảng băm.
Giả sử M = 7, cho trường hợp T của bảng băm đã chứa dữ liệu như bên dưới. Biết “-” là ký hiệu vị trí trống trong bảng băm.
.png)
a. Trình bày từng bước việc tìm mã quản lý 23 trong bảng băm T.
b. Trình bày từng bước việc thêm các mã quản lý sau vào bảng băm T theo đúng thứ tự liệt kê là 11, 20, 27.
Trả lời:
Đáp án đúng:
Câu hỏi này kiểm tra kiến thức về cấu trúc dữ liệu bảng băm (hash table) với phương pháp giải quyết xung đột bằng thăm dò bậc hai (quadratic probing). Cụ thể, câu hỏi yêu cầu thực hiện hai tác vụ chính: tìm kiếm một mã quản lý đã có trong bảng băm và thêm mới một số mã quản lý vào bảng băm.
**Phần a: Tìm kiếm mã quản lý 23**
Để tìm mã quản lý 23, chúng ta sẽ sử dụng hàm băm và hàm thăm dò đã cho. Kích thước bảng băm là M = 7.
1. **Tính toán vị trí ban đầu bằng hàm băm chính:**
h(key) = key % M
h(23) = 23 % 7 = 2
Vị trí đầu tiên cần kiểm tra là chỉ số 2.
2. **Kiểm tra vị trí 2 trong bảng băm T:**
Quan sát hình ảnh bảng băm, ta thấy tại chỉ số 2 có giá trị là 16. Vì 16 != 23, nên mã 23 chưa được tìm thấy tại đây.
3. **Tiến hành thăm dò lần thứ nhất (i=1) nếu vị trí ban đầu không khớp:**
Hàm thăm dò: prob(key, i) = (h(key) + i*i + i) % M
prob(23, 1) = (h(23) + 1*1 + 1) % 7
prob(23, 1) = (2 + 1 + 1) % 7 = 4 % 7 = 4
Vị trí tiếp theo cần kiểm tra là chỉ số 4.
4. **Kiểm tra vị trí 4 trong bảng băm T:**
Tại chỉ số 4 có giá trị là 23. Mã quản lý 23 đã được tìm thấy.
**Kết luận phần a:** Mã quản lý 23 được tìm thấy tại chỉ số 4 sau 1 lần thăm dò.
**Phần b: Thêm các mã quản lý 11, 20, 27**
Chúng ta sẽ thêm lần lượt từng mã vào bảng băm T có kích thước M=7 và trạng thái ban đầu được cho.
**1. Thêm mã 11:**
- Tính vị trí ban đầu: h(11) = 11 % 7 = 4.
- Kiểm tra vị trí 4: Vị trí 4 đang chứa giá trị 23. Xung đột xảy ra.
- Thăm dò lần 1 (i=1): prob(11, 1) = (h(11) + 1*1 + 1) % 7 = (4 + 1 + 1) % 7 = 6 % 7 = 6.
- Kiểm tra vị trí 6: Vị trí 6 trống ('-').
- Thêm 11 vào vị trí 6.
Bảng băm sau khi thêm 11: [2, 9, 16, -, 23, -, 11]
**2. Thêm mã 20:**
- Tính vị trí ban đầu: h(20) = 20 % 7 = 6.
- Kiểm tra vị trí 6: Vị trí 6 đang chứa giá trị 11. Xung đột xảy ra.
- Thăm dò lần 1 (i=1): prob(20, 1) = (h(20) + 1*1 + 1) % 7 = (6 + 1 + 1) % 7 = 8 % 7 = 1.
- Kiểm tra vị trí 1: Vị trí 1 trống ('-').
- Thêm 20 vào vị trí 1.
Bảng băm sau khi thêm 20: [2, 20, 16, -, 23, -, 11]
**3. Thêm mã 27:**
- Tính vị trí ban đầu: h(27) = 27 % 7 = 6.
- Kiểm tra vị trí 6: Vị trí 6 đang chứa giá trị 11. Xung đột xảy ra.
- Thăm dò lần 1 (i=1): prob(27, 1) = (h(27) + 1*1 + 1) % 7 = (6 + 1 + 1) % 7 = 8 % 7 = 1.
- Kiểm tra vị trí 1: Vị trí 1 đang chứa giá trị 20. Xung đột xảy ra.
- Thăm dò lần 2 (i=2): prob(27, 2) = (h(27) + 2*2 + 2) % 7 = (6 + 4 + 2) % 7 = 12 % 7 = 5.
- Kiểm tra vị trí 5: Vị trí 5 trống ('-').
- Thêm 27 vào vị trí 5.
Bảng băm sau khi thêm 27: [2, 20, 16, -, 23, 27, 11]
**Kết luận phần b:** Các mã 11, 20, 27 được thêm vào các vị trí tương ứng là 6, 1, 5.
Đề thi cuối kỳ môn Cấu trúc dữ liệu và giải thuật của Trường Đại học Công nghệ Thông tin, Học kỳ 2, năm học 2021-2022. Nội dung bao gồm các câu hỏi về thuật toán Insertion Sort, cây nhị phân tìm kiếm, cây B-Tree, kỹ thuật băm và biểu diễn đồ thị cho bài toán đường đi ngắn nhất.
5 câu hỏi 90 phút
Câu hỏi liên quan
Lời giải:
Câu hỏi này yêu cầu hai phần chính:
a. Xây dựng cấu trúc dữ liệu biểu diễn đồ thị: Đề bài mô tả một bài toán tìm đường đi ngắn nhất trên đồ thị có hướng, có trọng số dương. Input bao gồm số cạnh, thông tin các cạnh (đỉnh đầu, đỉnh cuối, trọng số) và cặp đỉnh xuất phát - đích. Yêu cầu là xây dựng cấu trúc dữ liệu tiết kiệm tài nguyên và hỗ trợ hiệu quả các thao tác: kiểm tra hai đỉnh có kề nhau không, tìm danh sách đỉnh kề của một đỉnh mà không cần duyệt toàn bộ cạnh.
Để đáp ứng các tiêu chí này, ma trận kề (adjacency matrix) là một lựa chọn không tối ưu vì nó tiêu tốn O(V^2) bộ nhớ, không hiệu quả với đồ thị thưa, và việc tìm đỉnh kề yêu cầu duyệt toàn bộ hàng/cột (O(V)). Danh sách cạnh (edge list) trực tiếp lưu trữ input, nhưng việc tìm đỉnh kề hoặc kiểm tra kề nhau sẽ tốn O(E).
Cấu trúc dữ liệu phù hợp nhất cho yêu cầu này là danh sách kề (adjacency list). Với đồ thị có hướng, mỗi đỉnh sẽ có một danh sách (thường là `std::vector` hoặc `std::list` trong C++ STL) chứa các cặp (đỉnh kề, trọng số).
* Tiết kiệm tài nguyên: Dung lượng bộ nhớ là O(V + E), phù hợp với cả đồ thị thưa và dày.
* Kiểm tra hai đỉnh có kề nhau không (u, v): Ta truy cập danh sách kề của u, sau đó tìm kiếm v trong danh sách đó. Nếu đỉnh kề được lưu trong `std::vector`, tìm kiếm có thể mất O(deg(u)) hoặc O(log deg(u)) nếu sắp xếp. Tuy nhiên, nếu dùng `std::map` hoặc `std::unordered_map` để lưu danh sách kề (ánh xạ đỉnh kề tới trọng số), thao tác này sẽ nhanh hơn, trung bình O(1) với `unordered_map` hoặc O(log deg(u)) với `map`.
* Tìm danh sách các đỉnh kề với một đỉnh cho trước (u): Ta chỉ cần truy cập danh sách kề của đỉnh u. Thời gian là O(deg(u)), không phụ thuộc vào tổng số cạnh E.
Do đó, sử dụng một `std::map>>` hoặc `std::unordered_map>>` (hoặc tương tự với `int` thay vì `string` nếu đỉnh được đánh số) là giải pháp tối ưu.
b. Viết hàm nhập Input và lưu trữ: Hàm này cần đọc số lượng cạnh, sau đó lặp lại số lần đó để đọc thông tin từng cạnh (u, v, w) và lưu vào cấu trúc dữ liệu đã chọn. Cuối cùng, đọc cặp đỉnh xuất phát (s) và đích (f).
Lưu ý: Câu hỏi không yêu cầu giải thuật tìm đường đi ngắn nhất, chỉ tập trung vào việc biểu diễn đồ thị và nhập liệu. Do đó, không có đáp án đúng để chọn theo format `answer_iscorrect` vì đây là yêu cầu thực hiện, không phải trắc nghiệm.
a. Xây dựng cấu trúc dữ liệu biểu diễn đồ thị: Đề bài mô tả một bài toán tìm đường đi ngắn nhất trên đồ thị có hướng, có trọng số dương. Input bao gồm số cạnh, thông tin các cạnh (đỉnh đầu, đỉnh cuối, trọng số) và cặp đỉnh xuất phát - đích. Yêu cầu là xây dựng cấu trúc dữ liệu tiết kiệm tài nguyên và hỗ trợ hiệu quả các thao tác: kiểm tra hai đỉnh có kề nhau không, tìm danh sách đỉnh kề của một đỉnh mà không cần duyệt toàn bộ cạnh.
Để đáp ứng các tiêu chí này, ma trận kề (adjacency matrix) là một lựa chọn không tối ưu vì nó tiêu tốn O(V^2) bộ nhớ, không hiệu quả với đồ thị thưa, và việc tìm đỉnh kề yêu cầu duyệt toàn bộ hàng/cột (O(V)). Danh sách cạnh (edge list) trực tiếp lưu trữ input, nhưng việc tìm đỉnh kề hoặc kiểm tra kề nhau sẽ tốn O(E).
Cấu trúc dữ liệu phù hợp nhất cho yêu cầu này là danh sách kề (adjacency list). Với đồ thị có hướng, mỗi đỉnh sẽ có một danh sách (thường là `std::vector` hoặc `std::list` trong C++ STL) chứa các cặp (đỉnh kề, trọng số).
* Tiết kiệm tài nguyên: Dung lượng bộ nhớ là O(V + E), phù hợp với cả đồ thị thưa và dày.
* Kiểm tra hai đỉnh có kề nhau không (u, v): Ta truy cập danh sách kề của u, sau đó tìm kiếm v trong danh sách đó. Nếu đỉnh kề được lưu trong `std::vector`, tìm kiếm có thể mất O(deg(u)) hoặc O(log deg(u)) nếu sắp xếp. Tuy nhiên, nếu dùng `std::map` hoặc `std::unordered_map` để lưu danh sách kề (ánh xạ đỉnh kề tới trọng số), thao tác này sẽ nhanh hơn, trung bình O(1) với `unordered_map` hoặc O(log deg(u)) với `map`.
* Tìm danh sách các đỉnh kề với một đỉnh cho trước (u): Ta chỉ cần truy cập danh sách kề của đỉnh u. Thời gian là O(deg(u)), không phụ thuộc vào tổng số cạnh E.
Do đó, sử dụng một `std::map
b. Viết hàm nhập Input và lưu trữ: Hàm này cần đọc số lượng cạnh, sau đó lặp lại số lần đó để đọc thông tin từng cạnh (u, v, w) và lưu vào cấu trúc dữ liệu đã chọn. Cuối cùng, đọc cặp đỉnh xuất phát (s) và đích (f).
Lưu ý: Câu hỏi không yêu cầu giải thuật tìm đường đi ngắn nhất, chỉ tập trung vào việc biểu diễn đồ thị và nhập liệu. Do đó, không có đáp án đúng để chọn theo format `answer_iscorrect` vì đây là yêu cầu thực hiện, không phải trắc nghiệm.
Lời giải:
Thuật toán Sắp xếp chèn (Insertion Sort) có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất và trung bình, do trong mỗi lần chèn một phần tử, ta có thể phải duyệt qua tất cả các phần tử đã được sắp xếp trước đó để tìm vị trí thích hợp. Trong trường hợp tốt nhất (mảng đã sắp xếp), độ phức tạp là O(n). Để sắp xếp mảng giảm dần, ta cần thay đổi điều kiện so sánh trong vòng lặp `while` từ `key < arr[j]` sang `key > arr[j]` (trong trường hợp tăng dần) để đảm bảo các phần tử lớn hơn được dịch sang phải, tạo không gian cho phần tử hiện tại được chèn vào đúng vị trí để có thứ tự giảm dần. Minh họa từng bước với dãy `3, 8, 4, 5, 9, 1, 2, 6` cho việc sắp xếp giảm dần như sau:
1. Khởi tạo: Mảng con đã sắp xếp `[3]`. Phần tử đang xét: `8`.
* `8 > 3`. Chèn `8` vào sau `3`. Mảng con: `[8, 3]`.
2. Phần tử đang xét: `4`.
* `4 < 8`. `4 > 3`. Chèn `4` vào giữa `8` và `3`. Mảng con: `[8, 4, 3]`.
3. Phần tử đang xét: `5`.
* `5 < 8`. `5 > 4`. Chèn `5` vào giữa `8` và `4`. Mảng con: `[8, 5, 4, 3]`.
4. Phần tử đang xét: `9`.
* `9 > 8`. Chèn `9` vào đầu. Mảng con: `[9, 8, 5, 4, 3]`.
5. Phần tử đang xét: `1`.
* `1 < 9`, `1 < 8`, `1 < 5`, `1 < 4`, `1 < 3`. Chèn `1` vào giữa `3` và `2`. Mảng con: `[9, 8, 5, 4, 3, 1]`.
6. Phần tử đang xét: `2`.
* `2 < 9`, `2 < 8`, `2 < 5`, `2 < 4`, `2 < 3`. `2 > 1`. Chèn `2` vào giữa `3` và `1`. Mảng con: `[9, 8, 5, 4, 3, 2, 1]`.
7. Phần tử đang xét: `6`.
* `6 < 9`, `6 < 8`. `6 > 5`. Chèn `6` vào giữa `8` và `5`. Mảng con: `[9, 8, 6, 5, 4, 3, 2, 1]`.
Kết quả cuối cùng là mảng được sắp xếp giảm dần: `[9, 8, 6, 5, 4, 3, 2, 1]`.
1. Khởi tạo: Mảng con đã sắp xếp `[3]`. Phần tử đang xét: `8`.
* `8 > 3`. Chèn `8` vào sau `3`. Mảng con: `[8, 3]`.
2. Phần tử đang xét: `4`.
* `4 < 8`. `4 > 3`. Chèn `4` vào giữa `8` và `3`. Mảng con: `[8, 4, 3]`.
3. Phần tử đang xét: `5`.
* `5 < 8`. `5 > 4`. Chèn `5` vào giữa `8` và `4`. Mảng con: `[8, 5, 4, 3]`.
4. Phần tử đang xét: `9`.
* `9 > 8`. Chèn `9` vào đầu. Mảng con: `[9, 8, 5, 4, 3]`.
5. Phần tử đang xét: `1`.
* `1 < 9`, `1 < 8`, `1 < 5`, `1 < 4`, `1 < 3`. Chèn `1` vào giữa `3` và `2`. Mảng con: `[9, 8, 5, 4, 3, 1]`.
6. Phần tử đang xét: `2`.
* `2 < 9`, `2 < 8`, `2 < 5`, `2 < 4`, `2 < 3`. `2 > 1`. Chèn `2` vào giữa `3` và `1`. Mảng con: `[9, 8, 5, 4, 3, 2, 1]`.
7. Phần tử đang xét: `6`.
* `6 < 9`, `6 < 8`. `6 > 5`. Chèn `6` vào giữa `8` và `5`. Mảng con: `[9, 8, 6, 5, 4, 3, 2, 1]`.
Kết quả cuối cùng là mảng được sắp xếp giảm dần: `[9, 8, 6, 5, 4, 3, 2, 1]`.
Lời giải:
Câu hỏi này yêu cầu thực hiện các thao tác trên cây nhị phân tìm kiếm (Binary Search Tree - BST), bao gồm xây dựng cây từ một dãy ký tự, duyệt cây theo các thứ tự khác nhau (RNL, NRL), và thực hiện các thao tác xóa nút trên cây. Để trả lời đầy đủ câu hỏi này, người học cần nắm vững các khái niệm sau:
1. Cây nhị phân tìm kiếm (BST): Định nghĩa, quy tắc xây dựng (mỗi nút con trái nhỏ hơn nút cha, mỗi nút con phải lớn hơn nút cha). Giá trị của ký tự được xác định theo thứ tự xuất hiện trong từ điển. Giả sử bảng chữ cái tiếng Anh là cơ sở để xác định giá trị.
* R -> 18
* E -> 5
* T -> 20
* A -> 1
* V -> 22
* X -> 24
* L -> 12
* G -> 7
* S -> 19
* I -> 9
2. Xây dựng BST: Thêm lần lượt các phần tử vào cây theo thứ tự cho trước.
* Thêm R (18): R là nút gốc.
* Thêm E (5): 5 < 18, E là con trái của R.
* Thêm T (20): 20 > 18, T là con phải của R.
* Thêm A (1): 1 < 18 (R), 1 < 5 (E), A là con trái của E.
* Thêm V (22): 22 > 18 (R), 22 > 20 (T), V là con phải của T.
* Thêm X (24): 24 > 18 (R), 24 > 20 (T), 24 > 22 (V), X là con phải của V.
* Thêm L (12): 12 < 18 (R), 12 > 5 (E), 12 < 20 (T), L là con trái của T.
* Thêm G (7): 7 < 18 (R), 7 > 5 (E), 7 < 20 (T), 7 < 12 (L), G là con trái của L.
* Thêm S (19): 19 > 18 (R), 19 > 20 (T), 19 < 22 (V), S là con trái của V.
* Thêm I (9): 9 < 18 (R), 9 > 5 (E), 9 < 20 (T), 9 > 12 (L), 9 > 7 (G), I là con phải của G.
Cây sau khi thêm là:
R(18)
/ \
E(5) T(20)
/ / \
A(1) L(12) V(22)
/ / \
G(7) S(19) X(24)
/ \
I(9)
3. Duyệt cây:
* RNL (Root-Node-Left): Thứ tự duyệt thường gặp là NLR (Node-Left-Right), LNR (Left-Node-Right), LRN (Left-Right-Node), RLN (Right-Left-Node), RNL (Right-Node-Left), RNL (Right-Node-Left), RNL (Right-Node-Left), RNL (Right-Node-Left). Tuy nhiên, RNL không phải là một thứ tự duyệt cây nhị phân chuẩn và có thể là một cách diễn đạt sai hoặc ít dùng. Nếu hiểu RNL là duyệt gốc trước, sau đó duyệt cây con bên phải rồi mới đến cây con bên trái, thì thứ tự sẽ là: R, T, V, X, S, E, A, L, G, I. Nếu RNL được hiểu theo cách khác, cần làm rõ.
* NRL (Node-Right-Left): Tương tự, NRL cũng không phải là một thứ tự duyệt cây nhị phân chuẩn. Nếu hiểu NRL là duyệt gốc trước, sau đó duyệt cây con bên phải rồi mới đến cây con bên trái, thì thứ tự sẽ là: R, T, V, X, S, E, A, L, G, I. Tuy nhiên, nếu quy ước duyệt theo chiều sâu (depth-first) với thứ tự gốc, phải, trái thì đó là RNR N, sau đó mới đến L N. RNL và NRL có thể là cách viết tắt của các thuật toán duyệt cây. Giả sử RNL có nghĩa là duyệt gốc, rồi đến cây con bên phải, rồi đến cây con bên trái. NRL có nghĩa là duyệt gốc, rồi đến cây con bên trái, rồi đến cây con bên phải. Nếu RNL là Root-Right-Left và NRL là Node-Right-Left. Giả sử đề bài muốn hỏi theo thứ tự duyệt cây "Right-Node-Left" và "Node-Right-Left". Tuy nhiên, các thứ tự duyệt cây chuẩn là NLR, LNR, LRN, RNL, RLN, NRN, NLR, LRN. Nếu RNL là Right-Node-Left và NRL là Node-Right-Left thì sẽ có sự khác biệt. Với RNL (Right-Node-Left): R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), A(1), E(5). Với NRL (Node-Right-Left) ta có thể hiểu là duyệt nút gốc, rồi duyệt cây con bên phải, rồi duyệt cây con bên trái. R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
Nếu RNL là duyệt gốc, cây con phải, cây con trái và NRL là duyệt gốc, cây con trái, cây con phải.
RNL: R, T, V, X, S, E, A, L, G, I
NRL: R, E, A, L, G, I, T, V, X, S.
Tuy nhiên, đề bài chỉ ghi RNL, NRL. RNL có thể là Right-Node-Left (Duyệt nút gốc, rồi cây con phải, rồi cây con trái). NRL không có chuẩn như vậy. Giả sử đề bài nhầm và muốn hỏi các thứ tự duyệt phổ biến như NLR, LNR. Tuy nhiên, ta phải tuân thủ đề bài. Nếu coi RNL và NRL là hai thứ tự duyệt cây cụ thể, thì ta sẽ thực hiện theo đúng quy tắc đó.
RNL (Root-Node-Left) có thể hiểu là: Gốc -> Cây con phải -> Cây con trái. Duyệt R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
NRL (Node-Right-Left) có thể hiểu là: Gốc -> Cây con phải -> Cây con trái. Đây là cùng một thứ tự như RNL. Điều này rất có thể là lỗi đề bài.
Giả sử RNL là Right-Node-Left (Cây con phải, Gốc, Cây con trái): S, X, V, T, I, G, L, A, E, R. NRL (Node-Right-Left) không có chuẩn.
Nếu RNL là Root-Right-Left và NRL là Node-Right-Left thì RNL sẽ là: R, T, V, X, S, L, G, I, E, A. NRL có thể hiểu là duyệt nút gốc, sau đó duyệt cây con bên phải, rồi cây con bên trái. R, T, V, X, S, L, G, I, E, A.
Nếu ta coi RNL là thứ tự duyệt: Root, Right, Left. Và NRL là thứ tự duyệt: Node, Right, Left.
RNL: R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
NRL: R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
Hai thứ tự này giống nhau.
Nếu đề bài muốn hỏi NLR, LNR thì sẽ khác:
NLR: R, E, A, T, L, G, I, V, S, X.
LNR: A, E, R, G, I, L, T, S, V, X.
Giả định RNL là duyệt Root-Then-Right-Then-Left và NRL là duyệt Node-Then-Right-Then-Left.
RNL: R -> T -> V -> X -> S -> L -> G -> I -> E -> A.
NRL: R -> T -> V -> X -> S -> L -> G -> I -> E -> A.
Nếu ta hiểu RNL là Right-Node-Left và NRL là Node-Right-Left, thì hai thứ tự duyệt này sẽ giống nhau.
4. Xóa nút trên cây: Các trường hợp xóa nút:
* Nút không có con.
* Nút có một con.
* Nút có hai con (thay thế bằng nút nhỏ nhất của cây con phải hoặc nút lớn nhất của cây con trái).
* Xóa L (12): L có một con là G.
Cây sau khi xóa L:
R(18)
/ \
E(5) T(20)
/ / \
A(1) G(7) V(22)
/ / \
I(9) S(19) X(24)
* Xóa T (20): T có hai con là G và V. Ta sẽ thay T bằng nút nhỏ nhất của cây con phải của T, đó là S (19).
Cây sau khi xóa T:
R(18)
/ \
E(5) S(19)
/ / \
A(1) G(7) V(22)
/ / \
I(9) X(24)
* Xóa E (5): E có một con là A.
Cây sau khi xóa E:
R(18)
/ \
A(1) S(19)
/ \
G(7) V(22)
/ / \
I(9) X(24)
* Xóa R (18): R là nút gốc, có hai con là A và S. Ta thay R bằng nút nhỏ nhất của cây con phải của R, đó là G (7).
Cây sau khi xóa R:
G(7)
/ \
A(1) S(19)
/ \
I(9) V(22)
/ \
X(24)
Vì câu hỏi không cung cấp đáp án để chọn (answer_iscorrect), nên ta sẽ tập trung vào việc giải thích chi tiết quy trình.
1. Cây nhị phân tìm kiếm (BST): Định nghĩa, quy tắc xây dựng (mỗi nút con trái nhỏ hơn nút cha, mỗi nút con phải lớn hơn nút cha). Giá trị của ký tự được xác định theo thứ tự xuất hiện trong từ điển. Giả sử bảng chữ cái tiếng Anh là cơ sở để xác định giá trị.
* R -> 18
* E -> 5
* T -> 20
* A -> 1
* V -> 22
* X -> 24
* L -> 12
* G -> 7
* S -> 19
* I -> 9
2. Xây dựng BST: Thêm lần lượt các phần tử vào cây theo thứ tự cho trước.
* Thêm R (18): R là nút gốc.
* Thêm E (5): 5 < 18, E là con trái của R.
* Thêm T (20): 20 > 18, T là con phải của R.
* Thêm A (1): 1 < 18 (R), 1 < 5 (E), A là con trái của E.
* Thêm V (22): 22 > 18 (R), 22 > 20 (T), V là con phải của T.
* Thêm X (24): 24 > 18 (R), 24 > 20 (T), 24 > 22 (V), X là con phải của V.
* Thêm L (12): 12 < 18 (R), 12 > 5 (E), 12 < 20 (T), L là con trái của T.
* Thêm G (7): 7 < 18 (R), 7 > 5 (E), 7 < 20 (T), 7 < 12 (L), G là con trái của L.
* Thêm S (19): 19 > 18 (R), 19 > 20 (T), 19 < 22 (V), S là con trái của V.
* Thêm I (9): 9 < 18 (R), 9 > 5 (E), 9 < 20 (T), 9 > 12 (L), 9 > 7 (G), I là con phải của G.
Cây sau khi thêm là:
R(18)
/ \
E(5) T(20)
/ / \
A(1) L(12) V(22)
/ / \
G(7) S(19) X(24)
/ \
I(9)
3. Duyệt cây:
* RNL (Root-Node-Left): Thứ tự duyệt thường gặp là NLR (Node-Left-Right), LNR (Left-Node-Right), LRN (Left-Right-Node), RLN (Right-Left-Node), RNL (Right-Node-Left), RNL (Right-Node-Left), RNL (Right-Node-Left), RNL (Right-Node-Left). Tuy nhiên, RNL không phải là một thứ tự duyệt cây nhị phân chuẩn và có thể là một cách diễn đạt sai hoặc ít dùng. Nếu hiểu RNL là duyệt gốc trước, sau đó duyệt cây con bên phải rồi mới đến cây con bên trái, thì thứ tự sẽ là: R, T, V, X, S, E, A, L, G, I. Nếu RNL được hiểu theo cách khác, cần làm rõ.
* NRL (Node-Right-Left): Tương tự, NRL cũng không phải là một thứ tự duyệt cây nhị phân chuẩn. Nếu hiểu NRL là duyệt gốc trước, sau đó duyệt cây con bên phải rồi mới đến cây con bên trái, thì thứ tự sẽ là: R, T, V, X, S, E, A, L, G, I. Tuy nhiên, nếu quy ước duyệt theo chiều sâu (depth-first) với thứ tự gốc, phải, trái thì đó là RNR N, sau đó mới đến L N. RNL và NRL có thể là cách viết tắt của các thuật toán duyệt cây. Giả sử RNL có nghĩa là duyệt gốc, rồi đến cây con bên phải, rồi đến cây con bên trái. NRL có nghĩa là duyệt gốc, rồi đến cây con bên trái, rồi đến cây con bên phải. Nếu RNL là Root-Right-Left và NRL là Node-Right-Left. Giả sử đề bài muốn hỏi theo thứ tự duyệt cây "Right-Node-Left" và "Node-Right-Left". Tuy nhiên, các thứ tự duyệt cây chuẩn là NLR, LNR, LRN, RNL, RLN, NRN, NLR, LRN. Nếu RNL là Right-Node-Left và NRL là Node-Right-Left thì sẽ có sự khác biệt. Với RNL (Right-Node-Left): R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), A(1), E(5). Với NRL (Node-Right-Left) ta có thể hiểu là duyệt nút gốc, rồi duyệt cây con bên phải, rồi duyệt cây con bên trái. R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
Nếu RNL là duyệt gốc, cây con phải, cây con trái và NRL là duyệt gốc, cây con trái, cây con phải.
RNL: R, T, V, X, S, E, A, L, G, I
NRL: R, E, A, L, G, I, T, V, X, S.
Tuy nhiên, đề bài chỉ ghi RNL, NRL. RNL có thể là Right-Node-Left (Duyệt nút gốc, rồi cây con phải, rồi cây con trái). NRL không có chuẩn như vậy. Giả sử đề bài nhầm và muốn hỏi các thứ tự duyệt phổ biến như NLR, LNR. Tuy nhiên, ta phải tuân thủ đề bài. Nếu coi RNL và NRL là hai thứ tự duyệt cây cụ thể, thì ta sẽ thực hiện theo đúng quy tắc đó.
RNL (Root-Node-Left) có thể hiểu là: Gốc -> Cây con phải -> Cây con trái. Duyệt R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
NRL (Node-Right-Left) có thể hiểu là: Gốc -> Cây con phải -> Cây con trái. Đây là cùng một thứ tự như RNL. Điều này rất có thể là lỗi đề bài.
Giả sử RNL là Right-Node-Left (Cây con phải, Gốc, Cây con trái): S, X, V, T, I, G, L, A, E, R. NRL (Node-Right-Left) không có chuẩn.
Nếu RNL là Root-Right-Left và NRL là Node-Right-Left thì RNL sẽ là: R, T, V, X, S, L, G, I, E, A. NRL có thể hiểu là duyệt nút gốc, sau đó duyệt cây con bên phải, rồi cây con bên trái. R, T, V, X, S, L, G, I, E, A.
Nếu ta coi RNL là thứ tự duyệt: Root, Right, Left. Và NRL là thứ tự duyệt: Node, Right, Left.
RNL: R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
NRL: R(18), T(20), V(22), X(24), S(19), L(12), G(7), I(9), E(5), A(1).
Hai thứ tự này giống nhau.
Nếu đề bài muốn hỏi NLR, LNR thì sẽ khác:
NLR: R, E, A, T, L, G, I, V, S, X.
LNR: A, E, R, G, I, L, T, S, V, X.
Giả định RNL là duyệt Root-Then-Right-Then-Left và NRL là duyệt Node-Then-Right-Then-Left.
RNL: R -> T -> V -> X -> S -> L -> G -> I -> E -> A.
NRL: R -> T -> V -> X -> S -> L -> G -> I -> E -> A.
Nếu ta hiểu RNL là Right-Node-Left và NRL là Node-Right-Left, thì hai thứ tự duyệt này sẽ giống nhau.
4. Xóa nút trên cây: Các trường hợp xóa nút:
* Nút không có con.
* Nút có một con.
* Nút có hai con (thay thế bằng nút nhỏ nhất của cây con phải hoặc nút lớn nhất của cây con trái).
* Xóa L (12): L có một con là G.
Cây sau khi xóa L:
R(18)
/ \
E(5) T(20)
/ / \
A(1) G(7) V(22)
/ / \
I(9) S(19) X(24)
* Xóa T (20): T có hai con là G và V. Ta sẽ thay T bằng nút nhỏ nhất của cây con phải của T, đó là S (19).
Cây sau khi xóa T:
R(18)
/ \
E(5) S(19)
/ / \
A(1) G(7) V(22)
/ / \
I(9) X(24)
* Xóa E (5): E có một con là A.
Cây sau khi xóa E:
R(18)
/ \
A(1) S(19)
/ \
G(7) V(22)
/ / \
I(9) X(24)
* Xóa R (18): R là nút gốc, có hai con là A và S. Ta thay R bằng nút nhỏ nhất của cây con phải của R, đó là G (7).
Cây sau khi xóa R:
G(7)
/ \
A(1) S(19)
/ \
I(9) V(22)
/ \
X(24)
Vì câu hỏi không cung cấp đáp án để chọn (answer_iscorrect), nên ta sẽ tập trung vào việc giải thích chi tiết quy trình.
.png)
Lời giải:
Câu hỏi này yêu cầu thực hiện các thao tác thêm và xóa trên cây B-Tree bậc 3.
Phần 3.1: Thêm các khóa vào cây B-Tree bậc 3 rỗng.
Một cây B-Tree bậc 3 có tối đa 3 con, nghĩa là mỗi nút có thể chứa tối đa 2 khóa.
Ta sẽ lần lượt thêm các số: 12, 17, 20, 23, 15, 11, 24, 13, 19, 22, 18, 21, 16.
1. Thêm 12: Cây: [12]
2. Thêm 17: Cây: [12, 17]
3. Thêm 20: Nút [12, 17] đầy, thêm 20 thành [12, 17, 20]. Tách nút: 17 lên làm gốc. Cây: [17] với con trái [12] và con phải [20]. *(Khóa gây tách: 20)*
4. Thêm 23: Thêm vào nút [20]. Cây: [17], [12], [20, 23]
5. Thêm 15: Thêm vào nút [12]. Cây: [17], [12, 15], [20, 23]
6. Thêm 11: Thêm vào nút [12, 15] thành [11, 12, 15]. Tách nút: 12 lên làm cha. Cây: [12, 17], [11], [15], [20, 23]. *(Khóa gây tách: 11)*
7. Thêm 24: Thêm vào nút [20, 23] thành [20, 23, 24]. Tách nút: 23 lên làm cha. Cây: [12, 17, 23], [11], [15], [20], [24]. *(Khóa gây tách: 24)*. Nút gốc [12, 17, 23] đầy, tách nút: 17 lên làm gốc mới. Cây: [17], [12], [23], [11], [15], [20], [24]. *(Khóa gây tách: 23)*
8. Thêm 13: Thêm vào nút [15]. Cây: [17], [12], [23], [11], [13, 15], [20], [24].
9. Thêm 19: Thêm vào nút [20]. Cây: [17], [12], [23], [11], [13, 15], [19, 20], [24].
10. Thêm 22: Thêm vào nút [23]. Cây: [17], [12], [22, 23], [11], [13, 15], [19, 20], [24].
11. Thêm 18: Thêm vào nút [19, 20] thành [18, 19, 20]. Tách nút: 19 lên làm cha. Cây: [17, 19], [12], [22, 23], [11], [13, 15], [18], [20], [24]. *(Khóa gây tách: 18)*
12. Thêm 21: Thêm vào nút [20]. Cây: [17, 19], [12], [22, 23], [11], [13, 15], [18], [20, 21], [24].
13. Thêm 16: Thêm vào nút [13, 15] thành [13, 15, 16]. Tách nút: 15 lên làm cha. Cây: [15, 17, 19], [12], [22, 23], [11], [13], [16], [18], [20, 21], [24]. *(Khóa gây tách: 16)*. Nút gốc [15, 17, 19] đầy, tách nút: 17 lên làm gốc mới. Cây: [17], [15], [19], [12], [22, 23], [11], [13], [16], [18], [20, 21], [24]. *(Khóa gây tách: 16)*.
a. Các khóa làm phát sinh thao tác tách node: 20, 11, 24, 23, 18, 16.
b. Cần vẽ lại cây tại mỗi bước có tách node.
Phần 3.2: Xóa các khóa khỏi cây B-Tree bậc 3 cho trước.
Cây B-Tree ban đầu:
* Gốc: [17, 25]
* Cây con trái của 17: [10, 14]
* Cây con giữa 17 và 25: [19, 22]
* Cây con phải của 25: [28, 30]
* Các nút lá con: [6, 8], [11, 12] (dưới [10, 14]); [18], [20, 21] (dưới [19, 22]); [27], [29] (dưới [28, 30]).
a. Xóa 13:
* Khóa 13 không có trong cây. Cây không thay đổi.
* Cây trước khi xóa: Như cây ban đầu.
* Cây sau khi xóa: Như cây ban đầu.
b. Xóa 24:
* Khóa 24 không có trong cây. Cây không thay đổi.
* Cây trước khi xóa: Như cây ban đầu.
* Cây sau khi xóa: Như cây ban đầu.
c. Xóa 19:
* 19 nằm ở gốc [17, 25].
* Tìm khóa thế mạng lớn nhất nhỏ hơn 19: là 18 (từ nút lá [18]).
* Thay 19 bằng 18 ở gốc. Gốc: [17, 18, 25].
* Xóa 18 khỏi nút lá [18]. Nút này còn trống.
* Xử lý underflow: Nút [18] trống. Node cha là [17, 18, 25]. Nút trống là con thứ 3.
* Xét anh em bên trái: nút [20, 21] (con thứ 4 của 25).
* Nhường khóa: Nút cha [17, 18, 25] nhường 18 xuống. Gốc thành [17, 25]. Khoá 18 đi xuống.
* Nút trống [18] nhận 18, trở thành [18].
* Nhường từ anh em: Nút [20, 21] nhường 20 lên. Nút [20, 21] còn [21].
* Cha [17, 25] nhận 20 lên. Cha thành [17, 20, 25].
* Cây sau khi xóa 19:
* Gốc: [17, 20, 25]
* Cây con 17: [10, 14]
* Cây con 20: [19, 22]
* Cây con 20: [18]
* Cây con 25: [21]
* Cây con 25: [28, 30]
* Các lá dưới [10, 14]: [6, 8], [11, 12]
* Các lá dưới [19, 22]: [18] (nơi 18 bị xóa, giờ là nút lá)
* Các lá dưới [28, 30]: [27], [29].
Lưu ý quan trọng: Với các thao tác vẽ cây, cần thể hiện rõ ràng cấu trúc của cây sau mỗi bước có thay đổi.
Phần 3.1: Thêm các khóa vào cây B-Tree bậc 3 rỗng.
Một cây B-Tree bậc 3 có tối đa 3 con, nghĩa là mỗi nút có thể chứa tối đa 2 khóa.
Ta sẽ lần lượt thêm các số: 12, 17, 20, 23, 15, 11, 24, 13, 19, 22, 18, 21, 16.
1. Thêm 12: Cây: [12]
2. Thêm 17: Cây: [12, 17]
3. Thêm 20: Nút [12, 17] đầy, thêm 20 thành [12, 17, 20]. Tách nút: 17 lên làm gốc. Cây: [17] với con trái [12] và con phải [20]. *(Khóa gây tách: 20)*
4. Thêm 23: Thêm vào nút [20]. Cây: [17], [12], [20, 23]
5. Thêm 15: Thêm vào nút [12]. Cây: [17], [12, 15], [20, 23]
6. Thêm 11: Thêm vào nút [12, 15] thành [11, 12, 15]. Tách nút: 12 lên làm cha. Cây: [12, 17], [11], [15], [20, 23]. *(Khóa gây tách: 11)*
7. Thêm 24: Thêm vào nút [20, 23] thành [20, 23, 24]. Tách nút: 23 lên làm cha. Cây: [12, 17, 23], [11], [15], [20], [24]. *(Khóa gây tách: 24)*. Nút gốc [12, 17, 23] đầy, tách nút: 17 lên làm gốc mới. Cây: [17], [12], [23], [11], [15], [20], [24]. *(Khóa gây tách: 23)*
8. Thêm 13: Thêm vào nút [15]. Cây: [17], [12], [23], [11], [13, 15], [20], [24].
9. Thêm 19: Thêm vào nút [20]. Cây: [17], [12], [23], [11], [13, 15], [19, 20], [24].
10. Thêm 22: Thêm vào nút [23]. Cây: [17], [12], [22, 23], [11], [13, 15], [19, 20], [24].
11. Thêm 18: Thêm vào nút [19, 20] thành [18, 19, 20]. Tách nút: 19 lên làm cha. Cây: [17, 19], [12], [22, 23], [11], [13, 15], [18], [20], [24]. *(Khóa gây tách: 18)*
12. Thêm 21: Thêm vào nút [20]. Cây: [17, 19], [12], [22, 23], [11], [13, 15], [18], [20, 21], [24].
13. Thêm 16: Thêm vào nút [13, 15] thành [13, 15, 16]. Tách nút: 15 lên làm cha. Cây: [15, 17, 19], [12], [22, 23], [11], [13], [16], [18], [20, 21], [24]. *(Khóa gây tách: 16)*. Nút gốc [15, 17, 19] đầy, tách nút: 17 lên làm gốc mới. Cây: [17], [15], [19], [12], [22, 23], [11], [13], [16], [18], [20, 21], [24]. *(Khóa gây tách: 16)*.
a. Các khóa làm phát sinh thao tác tách node: 20, 11, 24, 23, 18, 16.
b. Cần vẽ lại cây tại mỗi bước có tách node.
Phần 3.2: Xóa các khóa khỏi cây B-Tree bậc 3 cho trước.
Cây B-Tree ban đầu:
* Gốc: [17, 25]
* Cây con trái của 17: [10, 14]
* Cây con giữa 17 và 25: [19, 22]
* Cây con phải của 25: [28, 30]
* Các nút lá con: [6, 8], [11, 12] (dưới [10, 14]); [18], [20, 21] (dưới [19, 22]); [27], [29] (dưới [28, 30]).
a. Xóa 13:
* Khóa 13 không có trong cây. Cây không thay đổi.
* Cây trước khi xóa: Như cây ban đầu.
* Cây sau khi xóa: Như cây ban đầu.
b. Xóa 24:
* Khóa 24 không có trong cây. Cây không thay đổi.
* Cây trước khi xóa: Như cây ban đầu.
* Cây sau khi xóa: Như cây ban đầu.
c. Xóa 19:
* 19 nằm ở gốc [17, 25].
* Tìm khóa thế mạng lớn nhất nhỏ hơn 19: là 18 (từ nút lá [18]).
* Thay 19 bằng 18 ở gốc. Gốc: [17, 18, 25].
* Xóa 18 khỏi nút lá [18]. Nút này còn trống.
* Xử lý underflow: Nút [18] trống. Node cha là [17, 18, 25]. Nút trống là con thứ 3.
* Xét anh em bên trái: nút [20, 21] (con thứ 4 của 25).
* Nhường khóa: Nút cha [17, 18, 25] nhường 18 xuống. Gốc thành [17, 25]. Khoá 18 đi xuống.
* Nút trống [18] nhận 18, trở thành [18].
* Nhường từ anh em: Nút [20, 21] nhường 20 lên. Nút [20, 21] còn [21].
* Cha [17, 25] nhận 20 lên. Cha thành [17, 20, 25].
* Cây sau khi xóa 19:
* Gốc: [17, 20, 25]
* Cây con 17: [10, 14]
* Cây con 20: [19, 22]
* Cây con 20: [18]
* Cây con 25: [21]
* Cây con 25: [28, 30]
* Các lá dưới [10, 14]: [6, 8], [11, 12]
* Các lá dưới [19, 22]: [18] (nơi 18 bị xóa, giờ là nút lá)
* Các lá dưới [28, 30]: [27], [29].
Lưu ý quan trọng: Với các thao tác vẽ cây, cần thể hiện rõ ràng cấu trúc của cây sau mỗi bước có thay đổi.
