Triển khai mảng DSA
Thực hiện mảng cây nhị phân
Để tránh chi phí cho tất cả các thay đổi trong bộ nhớ mà chúng ta nhận được khi sử dụng Mảng, việc triển khai Cây nhị phân với các con trỏ từ phần tử này sang phần tử tiếp theo là rất hữu ích, giống như Cây nhị phân được triển khai trước thời điểm này, đặc biệt là khi Cây nhị phân được sửa đổi thường.
Nhưng trong trường hợp chúng ta đọc từ Cây nhị phân nhiều hơn là sửa đổi nó, thì việc triển khai Mảng của Cây nhị phân có thể hợp lý vì nó cần ít bộ nhớ hơn, dễ thực hiện hơn và có thể nhanh hơn đối với một số thao tác nhất định do địa phương bộ đệm.
Vị trí bộ đệm là khi bộ nhớ đệm nhanh trong máy tính lưu trữ các phần bộ nhớ được truy cập gần đây hoặc khi bộ đệm lưu trữ các phần bộ nhớ gần với địa chỉ hiện được truy cập. Điều này xảy ra vì có khả năng CPU cần thứ gì đó trong chu kỳ tiếp theo gần với những gì nó đã sử dụng trong chu kỳ trước, gần về thời gian hoặc gần về không gian.
Vì các phần tử Mảng được lưu trữ liên tục trong bộ nhớ, phần tử này nối tiếp phần tử kia nên máy tính đôi khi nhanh hơn khi đọc từ Mảng vì phần tử tiếp theo đã được lưu vào bộ nhớ đệm, có sẵn để truy cập nhanh trong trường hợp CPU cần nó trong chu kỳ tiếp theo.
Cách mảng được lưu trữ trong bộ nhớ được giải thích chi tiết hơn tại đây .
Hãy xem xét Cây nhị phân này:
Cây nhị phân này có thể được lưu trữ trong một mảng bắt đầu bằng nút gốc R trên chỉ mục 0. Phần còn lại của cây có thể được xây dựng bằng cách lấy một nút được lưu trữ trên chỉ mục \(i\) và lưu trữ nút con bên trái của nó trên chỉ mục \( 2\cdot i+1\) và nút con bên phải của nó trên chỉ mục \(2\cdot i+2\).
Dưới đây là cách triển khai Mảng của Cây nhị phân.
Ví dụ
Trăn:
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']
def left_child_index(index):
return 2 * index + 1
def right_child_index(index):
return 2 * index + 2
def get_data(index):
if 0 <= index < len(binary_tree_array):
return binary_tree_array[index]
return None
right_child = right_child_index(0)
left_child_of_right_child = left_child_index(right_child)
data = get_data(left_child_of_right_child)
print("root.right.left.data:", data) Chạy ví dụ »Trong triển khai Mảng này, do các nút Cây nhị phân được đặt trong một mảng nên phần lớn mã là về việc truy cập các nút bằng cách sử dụng các chỉ mục và về cách tìm các chỉ mục chính xác.
Giả sử chúng ta muốn tìm nút con trái và nút con phải của nút B. Vì B nằm ở chỉ mục 2 nên nút con trái của B nằm trên chỉ mục \(2\cdot 2+1=5\), là nút E, phải không? Và nút con bên phải của B nằm trên chỉ mục \(2\cdot 2+2=6\), là nút F và nó cũng phù hợp với hình vẽ ở trên, phải không?
Như bạn có thể thấy ở dòng 1, việc triển khai này yêu cầu các phần tử mảng trống trong đó các nút không có nút con. Vì vậy, để tránh lãng phí dung lượng trên các phần tử Mảng trống, Cây nhị phân được lưu trữ bằng cách triển khai Mảng phải là Cây nhị phân "hoàn hảo" hoặc gần như hoàn hảo.
Cây nhị phân hoàn hảo là khi mỗi nút bên trong có chính xác hai nút con và tất cả các nút lá đều ở cùng một cấp độ.
Nếu chúng ta loại bỏ nút G trong Cây nhị phân ở trên, nó sẽ trông như thế này:
Và dòng đầu tiên trong đoạn mã trên có thể được viết mà không lãng phí khoảng trống trên các phần tử Mảng trống:
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F']Đây là cách có thể thực hiện ba lần duyệt DFS khác nhau khi triển khai Mảng của Cây nhị phân.
Ví dụ
Trăn:
binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']
def left_child_index(index):
return 2 * index + 1
def right_child_index(index):
return 2 * index + 2
def pre_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return [binary_tree_array[index]] + pre_order(left_child_index(index)) + pre_order(right_child_index(index))
def in_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return in_order(left_child_index(index)) + [binary_tree_array[index]] + in_order(right_child_index(index))
def post_order(index):
if index >= len(binary_tree_array) or binary_tree_array[index] is None:
return []
return post_order(left_child_index(index)) + post_order(right_child_index(index)) + [binary_tree_array[index]]
print("Pre-order Traversal:", pre_order(0))
print("In-order Traversal:", in_order(0))
print("Post-order Traversal:", post_order(0)) Chạy ví dụ »Bằng cách so sánh cách thực hiện các quá trình duyệt này trong triển khai mảng với cách thực hiện duyệt con trỏ, bạn có thể thấy rằng các quá trình duyệt pre-order , in-order và post-order hoạt động theo cùng một cách đệ quy.
