Sử dụng byte với cấu trúc cây nhị phân

#1

Cho một cấu trúc cây nhị phân, lưu trữ các node gốc, node trái, node phải và node quay lui, mỗi node chiếm 4 byte tổng cộng sử dụng 16 byte, có cách nào để nó sử dụng lý tưởng nhất là 4 byte không

#2

Hi testdesign.

  1. Có.
  2. Tuy nhiên nó sẽ tự giới hạn kích thước cây. Dữ liệu lưu các node trái, phải, v.v.v… là con trỏ trỏ đến vị trí node kết tiếp. Vậy với 4byte -> mỗi con trỏ có kích thước 1 byte -> bạn chỉ đánh số được 256 địa chỉ -> cây của bạn chỉ có tối đa 256 node.
2 Likes
#3

Bạn có thể chỉ cho mình làm sao để mỗi con trỏ có kích thước 1 byte được không.

#4

HI testdesign.
Bạn tạo ra một bộ quản lý bộ nhớ của riêng mình đánh số địa chỉ bằng 1 byte. Khi bạn đưa nột số 1 byte vào nó trả về cho bạn một con trỏ đúng loại. Chú ý là để linh hoạt trong việc cấp phát cũng như kích thước thì dùng con trỏ của con trỏ.

VD: Mô hình đại khái như này.

VTMemory.png720×447 3.63 KB

P/S Bạn có thê code thử và up lên git mình có thể giúp bạn nếu nó không hoạt động.

#5

Làm giống bạn @Phong_Ky_Vo là chuẩn đấy. Phải tradeoff.
Hoặc bạn tham khảo binary heap. Cấu trúc này thì không cần phải chứa địa chỉ của mỗi node do có thể xác định địa chỉ dựa trên index của node hiện tại

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?