Bỏ qua

Biểu diễn cây nhị phân bằng mảng

Trong biểu diễn danh sách liên kết, đơn vị lưu trữ của cây nhị phân là một nút TreeNode, và các nút được liên kết với nhau bằng con trỏ. Phần trước đã giới thiệu các thao tác cơ bản của cây nhị phân trong kiểu biểu diễn này.

Vậy chúng ta có thể sử dụng mảng để biểu diễn một cây nhị phân hay không? Câu trả lời là có.

Biểu diễn cây nhị phân hoàn hảo

Trước hết hãy cùng phân tích một trường hợp đơn giản. Cho một cây nhị phân hoàn hảo (perfect binary tree), chúng ta lưu trữ tất cả các nút trong một mảng theo thứ tự duyệt theo mức (level-order traversal), trong đó mỗi nút tương ứng với một chỉ số mảng duy nhất.

Dựa vào đặc điểm của phép duyệt theo mức, chúng ta có thể suy ra một "công thức ánh xạ" giữa chỉ số của nút cha và chỉ số của các nút con: Nếu chỉ số của một nút là \(i\), thì chỉ số con bên trái của nó là \(2i + 1\) và chỉ số con bên phải của nó là \(2i + 2\). Hình dưới đây thể hiện mối quan hệ ánh xạ giữa các chỉ số nút khác nhau.

Biểu diễn mảng của cây nhị phân hoàn hảo

Công thức ánh xạ này đóng vai trò tương tự như các tham chiếu nút (con trỏ) trong danh sách liên kết. Từ bất kỳ nút nào trong mảng, chúng ta đều có thể truy cập nút con bên trái (hoặc con bên phải) của nó bằng cách sử dụng công thức ánh xạ.

Biểu diễn cây nhị phân bất kỳ

Cây nhị phân hoàn hảo là một trường hợp đặc biệt; ở các mức trung gian của một cây nhị phân thông thường sẽ xuất hiện nhiều giá trị trống (hoặc None). Vì chuỗi kết quả duyệt theo mức không chứa các giá trị trống này, nên chúng ta không thể xác định được số lượng và sự phân bố của các giá trị trống đó chỉ dựa vào chuỗi kết quả. Điều này có nghĩa là nhiều cấu trúc cây nhị phân khác nhau có thể cùng tương ứng với một chuỗi kết quả duyệt theo mức.

Như thể hiện trong hình dưới đây, đối với một cây nhị phân không hoàn hảo, phương pháp biểu diễn bằng mảng nêu trên sẽ không hoạt động.

Chuỗi kết quả duyệt theo mức tương ứng với nhiều khả năng cấu trúc cây nhị phân

Để giải quyết vấn đề này, chúng ta có thể ghi rõ tất cả các giá trị trống (None / null) trong chuỗi kết quả duyệt theo mức. Như trong hình dưới đây, khi đã thực hiện điều này, chuỗi kết quả duyệt theo mức có thể biểu diễn duy nhất một cây nhị phân. Mã ví dụ như sau:

# Biểu diễn cây nhị phân bằng mảng
# Sử dụng None để biểu diễn các vị trí trống
tree = [1, 2, 3, 4, None, 6, 7, 8, 9, None, None, 12, None, None, 15]

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng giá trị số nguyên lớn nhất INT_MAX để đánh dấu các vị trí trống
vector<int> tree = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng lớp bao Integer cho phép dùng null để đánh dấu các vị trí trống
Integer[] tree = { 1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15 };

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng kiểu int nullable (int?) cho phép dùng null để đánh dấu các vị trí trống
int?[] tree = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng slice kiểu any, cho phép dùng nil để đánh dấu các vị trí trống
tree := []any{1, 2, 3, 4, nil, 6, 7, 8, 9, nil, nil, 12, nil, nil, 15}

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng kiểu Int tùy chọn (Int?) cho phép dùng nil để đánh dấu các vị trí trống
let tree: [Int?] = [1, 2, 3, 4, nil, 6, 7, 8, 9, nil, nil, 12, nil, nil, 15]

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng null để biểu diễn các vị trí trống
let tree = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng null để biểu diễn các vị trí trống
let tree: (number | null)[] = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng kiểu int nullable (int?) cho phép dùng null để đánh dấu các vị trí trống
List<int?> tree = [1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15];

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng None để đánh dấu các vị trí trống
let tree = [Some(1), Some(2), Some(3), Some(4), None, Some(6), Some(7), Some(8), Some(9), None, None, Some(12), None, None, Some(15)];

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng giá trị int lớn nhất để đánh dấu các vị trí trống, do đó giá trị nút không được là INT_MAX
int tree[] = {1, 2, 3, 4, INT_MAX, 6, 7, 8, 9, INT_MAX, INT_MAX, 12, INT_MAX, INT_MAX, 15};

/* Biểu diễn cây nhị phân bằng mảng */
// Sử dụng null để biểu diễn các vị trí trống
val tree = arrayOf( 1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15 )

### Biểu diễn cây nhị phân bằng mảng ###
# Sử dụng nil để biểu diễn các vị trí trống
tree = [1, 2, 3, 4, nil, 6, 7, 8, 9, nil, nil, 12, nil, nil, 15]

Biểu diễn mảng của một cây nhị phân bất kỳ

Đáng chú ý là cây nhị phân hoàn chỉnh (complete binary tree) rất phù hợp với kiểu biểu diễn bằng mảng. Nhớ lại định nghĩa về cây nhị phân hoàn chỉnh, các giá trị trống (None / null) chỉ xuất hiện ở mức dưới cùng và lệch sang bên phải, điều này có nghĩa là tất cả các giá trị trống phải xuất hiện ở phần cuối của chuỗi kết quả duyệt theo mức.

Điều này có nghĩa là khi sử dụng mảng để biểu diễn một cây nhị phân hoàn chỉnh, chúng ta có thể bỏ qua việc lưu trữ tất cả các giá trị trống, điều này cực kỳ tiện lợi. Hình dưới đây đưa ra một ví dụ.

Biểu diễn mảng của một cây nhị phân hoàn chỉnh

Đoạn mã dưới đây triển khai cây nhị phân bằng cách biểu diễn bằng mảng, bao gồm các thao tác sau:

  • Cho trước một nút, lấy giá trị của nó, nút con bên trái (bên phải) và nút cha của nó.
  • Lấy các chuỗi kết quả duyệt tiền thứ tự (preorder), trung thứ tự (inorder), hậu thứ tự (postorder) và duyệt theo mức (level-order).
[file]{array_binary_tree}-[class]{array_binary_tree}-[func]{}

Ưu điểm và hạn chế

Biểu diễn cây nhị phân bằng mảng có các ưu điểm sau:

  • Mảng được lưu trữ trong không gian bộ nhớ liên tục nên rất thân thiện với bộ nhớ đệm (cache-friendly), cho phép truy cập và duyệt nhanh hơn.
  • Không cần lưu trữ các con trỏ, giúp tiết kiệm không gian.
  • Cho phép truy cập ngẫu nhiên (random access) đến các nút.

Tuy nhiên, biểu diễn bằng mảng cũng có một số hạn chế:

  • Việc lưu trữ mảng yêu cầu không gian bộ nhớ liên tục, vì vậy không phù hợp để lưu trữ các cây có lượng dữ liệu lớn.
  • Việc thêm hoặc xóa các nút yêu cầu thực hiện thao tác chèn và xóa trong mảng, dẫn đến hiệu suất thấp hơn.
  • Khi cây nhị phân có nhiều giá trị trống (None), tỷ lệ dữ liệu nút thực tế chứa trong mảng là thấp, dẫn đến hiệu suất sử dụng không gian thấp hơn.