Bài toán dựng cây nhị phân

Question

Cho kết quả duyệt tiền thứ tự (preorder traversal) preorder và duyệt trung thứ tự (inorder traversal) inorder của một cây nhị phân (binary tree), hãy dựng lại cây nhị phân này và trả về nút gốc (root node) của cây. Giả sử không có giá trị nút nào bị trùng lặp trong cây nhị phân (như thể hiện ở hình bên dưới).

Xác định xem đây có phải là bài toán chia để trị không

Bài toán ban đầu được định nghĩa là dựng một cây nhị phân từ preorder and inorder, đây là một bài toán chia để trị điển hình.

• Bài toán có thể phân rã: Từ góc nhìn chia để trị, chúng ta có thể chia bài toán ban đầu thành hai bài toán con: dựng cây con trái (left subtree) và dựng cây con phải (right subtree), cộng với một thao tác: khởi tạo nút gốc. Đối với mỗi cây con (bài toán con), chúng ta vẫn có thể tái sử dụng phương pháp phân chia trên, chia nó thành các cây con nhỏ hơn (bài toán con) cho đến khi đạt được bài toán con nhỏ nhất (cây con rỗng).
• Các bài toán con là độc lập: Cây con trái và cây con phải độc lập với nhau; không có sự chồng chéo giữa chúng. Khi dựng cây con trái, chúng ta chỉ cần tập trung vào các phần duyệt trung thứ tự và duyệt tiền thứ tự tương ứng với cây con trái. Điều tương tự cũng áp dụng cho cây con phải.
• Lời giải của các bài toán con có thể hợp nhất: Khi đã có cây con trái và cây con phải (lời giải của các bài toán con), chúng ta có thể liên kết chúng với nút gốc để thu được lời giải cho bài toán ban đầu.

Cách phân chia các cây con

Dựa trên phân tích ở trên, bài toán này có thể giải quyết bằng phương pháp chia để trị, nhưng làm thế nào để chúng ta chia cây con trái và cây con phải thông qua kết quả duyệt tiền thứ tự preorder và duyệt trung thứ tự inorder?

Theo định nghĩa, cả preorder và inorder đều có thể được chia thành ba phần.

• Duyệt tiền thứ tự: [ Nút gốc | Cây con trái | Cây con phải ], ví dụ cây trong hình trên tương ứng với [ 3 | 9 | 2 1 7 ].
• Duyệt trung thứ tự: [ Cây con trái | Nút gốc ｜ Cây con phải ], ví dụ cây trong hình trên tương ứng với [ 9 | 3 | 1 2 7 ].

Sử dụng dữ liệu từ hình trên làm ví dụ, chúng ta có thể thu được kết quả phân chia thông qua các bước như hình dưới đây.

1. Phần tử đầu tiên 3 trong chuỗi duyệt tiền thứ tự là giá trị của nút gốc.
2. Tìm chỉ số của nút gốc 3 trong inorder, và sử dụng chỉ số này để chia inorder thành [ 9 | 3 ｜ 1 2 7 ].
3. Dựa trên kết quả phân chia của inorder, ta dễ dàng xác định được cây con trái và cây con phải lần lượt có 1 và 3 nút, cho phép chúng ta chia preorder thành [ 3 | 9 | 2 1 7 ].

Mô tả các khoảng cây con dựa trên các biến

Dựa trên phương pháp phân chia ở trên, chúng ta đã có được các khoảng chỉ số của nút gốc, cây con trái và cây con phải trong preorder và inorder. Để mô tả các khoảng chỉ số này, chúng ta cần sử dụng một vài biến chỉ số.

• Ký hiệu chỉ số của nút gốc của cây hiện tại trong preorder là \(i\).
• Ký hiệu chỉ số của nút gốc của cây hiện tại trong inorder là \(m\).
• Ký hiệu khoảng chỉ số của cây hiện tại trong inorder là \([l, r]\).

Như được thể hiện trong bảng dưới đây, thông qua các biến này, chúng ta có thể biểu diễn chỉ số của nút gốc trong preorder và khoảng chỉ số của các cây con trong inorder.

Bảng   Chỉ số của nút gốc và các cây con trong chuỗi duyệt tiền thứ tự và trung thứ tự

	Chỉ số nút gốc trong preorder	Khoảng chỉ số cây con trong inorder
Cây hiện tại	\(i\)	\([l, r]\)
Cây con trái	\(i + 1\)	\([l, m-1]\)
Cây con phải	\(i + 1 + (m - l)\)	\([m+1, r]\)

Xin lưu ý rằng \((m-l)\) trong công thức chỉ số nút gốc của cây con phải có nghĩa là "số lượng nút trong cây con trái". Khuyên bạn nên đọc hiểu phần này kết hợp với hình minh họa bên dưới.

Triển khai mã nguồn

Để nâng cao hiệu suất truy vấn \(m\), chúng ta sử dụng một bảng băm (hash table) hmap để lưu trữ ánh xạ từ các phần tử trong mảng inorder sang chỉ số tương ứng của chúng:

[file]{build_tree}-[class]{}-[func]{build_tree}

Hình dưới đây thể hiện quá trình đệ quy để dựng cây nhị phân. Mỗi nút được thiết lập trong quá trình "đệ quy" đi xuống, trong khi mỗi cạnh (tham chiếu) được thiết lập trong quá trình "quay lui" đi lên.

<1><2><3><4><5><6><7><8><9>

Kết quả phân chia của chuỗi duyệt tiền thứ tự preorder và chuỗi duyệt trung thứ tự inorder trong mỗi hàm đệ quy được thể hiện trong hình dưới đây.

Gọi số lượng nút trong cây là \(n\). Việc khởi tạo mỗi nút (thực thi một hàm đệ quy dfs()) mất thời gian \(O(1)\). Do đó, độ phức tạp thời gian tổng thể là \(O(n)\).

Bảng băm lưu trữ ánh xạ từ các phần tử inorder sang các chỉ số của chúng, với độ phức tạp không gian (space complexity) là \(O(n)\). Trong trường hợp xấu nhất, khi cây nhị phân thoái hóa thành một danh sách liên kết (linked list), độ sâu đệ quy đạt tới \(n\), sử dụng không gian khung ngăn xếp (stack frame space) \(O(n)\). Do đó, độ phức tạp không gian tổng thể là \(O(n)\).