Atree: triển khai Tree đơn giản và hiệu quả không cần con trỏ

• Apter Trees trong C++
• Cây được biểu diễn đơn giản chỉ bằng hai vector: [giá trị nút, chỉ số cha]
• Hầu hết cây thường được triển khai như cây nhị phân, trong đó mỗi nút chứa giá trị của chính nó và các con trỏ tới nút con trái/phải
• Kiểu cấu trúc dữ liệu này thường phải được triển khai bằng đệ quy, và có thể chậm do hành vi cache cùng việc gọi malloc() thường xuyên
• Khái niệm ai là người “sở hữu” một nút cây có thể trở nên phức tạp trong phần mềm nhiều lớp
• Apter tree nhanh hơn nhiều, dễ suy luận hơn và cũng dễ triển khai hơn

Cách hoạt động

• Được triển khai bằng hai mảng có cùng kích thước
  • vector (mảng) dữ liệu d
  • vector chỉ số cha p. Chỉ số trong vector d được dùng làm khóa c
  • thường thì khóa/chỉ số c là kiểu số nguyên
• Nếu Coco là cha của Molly và Arca, còn Arca có một nút con là Cricket, thì cấu trúc sẽ như sau
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• Nút có cha bằng 0 và khóa bằng 0 là nút gốc (Apter tree yêu cầu phải có nút gốc, hoặc cũng có thể dùng -1 để biểu thị "không có cha", nhưng ở đây bỏ qua trường hợp đó)
• Máy tính xử lý vector rất nhanh. Vì điều này nhanh hơn nhiều so với thao tác con trỏ, nên việc so sánh ký pháp Big-O của thuật toán trên thực tế không có nhiều ý nghĩa

Vì sao điều này quan trọng

• Đây là cách triển khai cây thanh nhã nhất mà tác giả từng thấy
• Nếu dùng thư viện thao tác vector phù hợp thì rất dễ hiểu và dễ tìm lỗi
• Nhờ sự đơn giản nên có thể dễ dàng áp dụng sang các kịch bản sử dụng khác
• Có thể nhanh chóng lặp qua các giá trị mà bỏ qua vector chỉ số cha; điều này giống như có sẵn Deep Map miễn phí
• Thân thiện với GPU và dễ dùng trong môi trường nhúng
• Có thể dễ dàng đảm bảo an toàn bằng cách không cho vector tăng vượt quá một kích thước nhất định

Nguồn gốc

• Tác giả đang cố tìm người đã phát minh ra kỹ thuật này và đoán rằng nó có lẽ đã có tên gọi từ thời kỳ thiên về vector của thập niên 60 và 70
• Bản mô tả đầy đủ đầu tiên mà tác giả thấy là do Apter trình bày, nhưng nó cũng đã được tài liệu hóa rộng rãi trong K3
• APL triển khai cây theo cách truyền thống, nhưng dùng kỹ thuật tương tự cho đồ thị vector
• Người dùng J cũng đã biết đến cách này, và có phần giải thích về triển khai cây bằng ngôn ngữ J trên Rosetta Code
• John Earnest giải thích chi tiết hơn về cách triển khai cây bằng vector, bao gồm cả cách tiếp cận "offset index" để xử lý việc xóa phần tử
• Một cách tiếp cận phức tạp hơn là theo dõi độ sâu của từng phần tử

Các cách triển khai cây phổ biến khác

• Có triển khai cây trong kernel của FreeBSD, cây của klib, lớp cây của Ruby, lớp cây khai báo trong Python, v.v.
• Chúng không thực hiện đúng cùng chức năng như Apter tree, và một số còn lớn hơn nhiều do tính tổng quát hóa

Tình trạng hiện tại của mã nguồn này

• Đây là một nỗ lực triển khai nó để học C++17
• Chưa sẵn sàng để sử dụng, và tác giả vẫn cần học thêm về C++

Ý kiến của GN⁺

• Apter Trees đơn giản hóa cấu trúc cây vốn phức tạp, cho phép quản lý dữ liệu nhanh và hiệu quả
• Cách triển khai cây dựa trên vector giúp giảm tối thiểu overhead bộ nhớ và có thể cải thiện hiệu năng thông qua truy cập tuyến tính
• Bài viết này mang lại góc nhìn thú vị về cách tiếp cận đổi mới đối với cấu trúc dữ liệu trong kỹ thuật phần mềm

[GN⁺]

Ý kiến trên Hacker News

• Một người dùng cho biết họ rất ngạc nhiên khi thấy công việc của mình được liên kết trên Hacker News. Họ vốn rất quan tâm đến các cấu trúc dữ liệu nhẹ dựa trên mảng, và đặc biệt nhắc đến một kiểu triển khai thường được dùng cho cây nút trong skinning mô hình 3D. Họ giải thích rằng nếu sắp xếp mảng sao cho nút cha đứng trước nút con, thì việc tính lại world transform cho mọi nút có thể được xử lý bằng một vòng lặp đơn giản.
• Một người dùng khác, phản hồi bình luận cho rằng việc lặp qua các nút con trong kiểu cây này là O(N), đã nói rằng thực ra khá dễ để khái quát hóa thiết kế atree bằng cách thêm các con trỏ trỏ đến "đứa con đầu tiên" và "anh chị em kế tiếp". Họ cũng khuyến nghị nên điều chỉnh cấu trúc dữ liệu để hỗ trợ đúng các thao tác cần thiết.
• Một người dùng cho rằng việc lưu các nút trong mảng và dùng chỉ số làm con trỏ là điều thiết yếu khi triển khai các thuật toán trên cây. Đặc biệt, nếu cần truy cập các nút con của một nút, họ khuyên nên cân nhắc dùng các cấu trúc riêng cho nút trong và nút lá để tiết kiệm bộ nhớ.
• Một người dùng khác nhận xét rằng việc biểu diễn cây bằng mảng cha mà lại thu hút nhiều sự chú ý trên Hacker News là điều hơi lạ. Theo họ, điều này cho thấy một bài trình bày tốt có thể đưa một ý tưởng cơ bản đi xa đến mức nào.
• Một người dùng chỉ ra rằng dự án này thực chất chỉ là thay thế con trỏ hệ thống bằng con trỏ tự định nghĩa.
• Một người dùng khác đề xuất rằng nếu mục tiêu là giảm số lần malloc và cải thiện tính cục bộ dữ liệu, thì nên thử cách triển khai cây truyền thống với node pool.
• Có một bình luận khuyến nghị tham khảo phần giải thích của Aaron Hsu sử dụng APL.
• Một người dùng đề xuất thay đổi cấu trúc để đóng gói tất cả các nút con của một nút lại với nhau. Làm như vậy sẽ cho phép tìm danh sách mọi nút con của một nút bằng tìm kiếm nhị phân và mang lại đặc tính thân thiện với cache.
• Có bình luận về việc gọi chỉ số trong mảng là "handle" hoặc "index-handle", đồng thời nhắc rằng cách biểu diễn cây này gợi nhớ đến các cấu trúc dữ liệu kinh điển như heap và disjoint set.
• Cuối cùng, có bình luận giải thích rằng chỉ số mảng cũng có thể được xem là một dạng "con trỏ", và việc các cách cài đặt cây truyền thống cần malloc là do nhu cầu thêm hoặc xóa nút một cách động. Nếu kích thước cây bị giới hạn và không thường xuyên xóa, thì cách cài đặt bằng mảng có thể phù hợp.