Atree: Implementasi Tree sederhana dan efisien tanpa pointer

• Apter Trees dalam C++
• Tree yang direpresentasikan secara sederhana hanya dengan menggunakan dua vektor: [nilai node, indeks induk)
• Sebagian besar tree diimplementasikan seperti binary tree, dengan setiap node menyertakan nilainya sendiri dan pointer ke node anak kiri/kanan
• Struktur data seperti ini harus diimplementasikan secara rekursif, dan bisa menjadi lambat karena perilaku cache serta malloc() yang sering
• Konsep tentang siapa yang "memiliki" node tree bisa menjadi rumit dalam perangkat lunak multi-layer
• Apter tree jauh lebih cepat, lebih mudah dipahami, dan lebih mudah diimplementasikan

Cara kerja

• Diimplementasikan dengan dua array yang ukurannya sama
  • vektor (array) data d
  • vektor indeks induk p. Indeks pada vektor d digunakan sebagai key (c)
  • sering kali key/indeks c bertipe integer
• Jika Coco adalah induk dari Molly dan Arca, dan Arca memiliki anak bernama Cricket, maka strukturnya menjadi seperti berikut
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• Node yang induknya 0 dan key-nya 0 adalah node root (pada Apter tree, node root wajib ada, atau -1 berarti "tidak ada induk", tetapi itu diabaikan di sini)
• Komputer dapat memanipulasi vektor dengan sangat cepat. Karena jauh lebih cepat daripada operasi pointer, membandingkan notasi Big-O untuk algoritme sebenarnya tidak terlalu bermakna dalam praktik

Mengapa penting

• Cara implementasi ini adalah yang paling elegan di antara implementasi tree yang pernah dilihat penulis
• Jika menggunakan library operasi vektor yang tepat, struktur ini mudah dipahami dan bug lebih mudah ditemukan
• Karena sederhana, pendekatan ini mudah diterapkan ke berbagai skenario penggunaan lain
• Kita bisa dengan cepat mengiterasi nilai-nilainya sambil mengabaikan vektor indeks induk, yang menjadikannya seperti Deep Map gratis
• Ramah GPU dan mudah digunakan di lingkungan embedded
• Keamanan dapat dijaga dengan mudah dengan mencegah ukuran vektor bertumbuh melampaui ukuran tertentu

Asal-usul

• Penulis sedang berusaha mencari siapa penemu teknik ini, dan menduga teknik ini sudah memiliki nama pada era 60-an dan 70-an yang berorientasi vektor
• Penulis pertama kali melihat penjelasan lengkapnya seperti yang dijelaskan oleh Apter, tetapi teknik ini juga didokumentasikan luas di K3
• APL mengimplementasikan tree dengan cara tradisional, tetapi menggunakan teknik serupa untuk graph berbasis vektor
• Teknik ini juga dikenal di kalangan pengguna J, dan ada penjelasan tentang implementasi tree bahasa J di Rosetta Code
• John Earnest menjelaskan implementasi vector tree secara lebih rinci, termasuk pendekatan "offset index" untuk item yang dihapus
• Pendekatan yang lebih kompleks adalah melacak kedalaman setiap item

Implementasi tree umum lainnya

• Ada implementasi tree kernel FreeBSD, tree milik klib, kelas tree Ruby, dan kelas tree deklaratif Python
• Implementasi-implementasi ini tidak menyediakan fungsi yang sama dengan Apter tree, dan beberapa jauh lebih besar karena digeneralisasi

Status kode ini

• Ini adalah upaya implementasi sambil mempelajari C++17
• Belum siap digunakan, dan penulis masih perlu belajar lebih banyak tentang C++

Opini GN⁺

• Apter Trees menyederhanakan struktur tree tradisional yang kompleks sehingga memungkinkan pengelolaan data yang cepat dan efisien
• Implementasi tree berbasis vektor dapat meminimalkan overhead memori dan meningkatkan performa melalui akses linear
• Artikel ini menawarkan eksplorasi menarik terhadap pendekatan inovatif pada struktur data dalam rekayasa perangkat lunak

[GN⁺]

Opini Hacker News

• Seorang pengguna mengungkapkan keterkejutannya saat melihat karyanya ditautkan di Hacker News. Ia sangat tertarik pada struktur data ringan berbasis array, dan secara khusus menyebut pola implementasi yang sering digunakan untuk tree node pada skinning model 3D. Ia menjelaskan bahwa jika array diurutkan sehingga parent node muncul sebelum child node, maka perhitungan ulang transformasi dunia untuk semua node dapat ditangani dengan loop sederhana.
• Pengguna lain menanggapi komentar bahwa mengiterasi child node dalam gaya tree seperti ini berbiaya O(N), dengan menyebut bahwa sebenarnya cukup mudah untuk menggeneralisasi desain atree dengan menambahkan pointer ke "child pertama" dan "sibling berikutnya". Ia juga menyarankan untuk mengubah struktur data agar mendukung operasi yang memang dibutuhkan.
• Seorang pengguna berpendapat bahwa menyimpan node dalam array dan menggunakan indeks sebagai pointer adalah hal yang esensial untuk implementasi algoritma tree. Ia menambahkan bahwa jika perlu mengakses child dari suatu node, sebaiknya mempertimbangkan struktur terpisah untuk internal node dan leaf node demi menghemat memori.
• Pengguna lain menyebut agak aneh bahwa cara merepresentasikan tree dengan parent array mendapat begitu banyak perhatian di Hacker News. Menurutnya, ini menunjukkan sejauh mana presentasi yang baik dapat membawa sebuah ide dasar.
• Seorang pengguna menunjukkan bahwa proyek ini pada dasarnya hanya mengganti pointer sistem dengan pointer buatannya sendiri.
• Pengguna lain menyarankan bahwa jika tujuannya adalah mengurangi malloc dan meningkatkan lokalitas data, sebaiknya mencoba implementasi tree tradisional yang menggunakan node pool.
• Ada komentar yang merekomendasikan untuk merujuk pada penjelasan Aaron Hsu yang menggunakan APL.
• Seorang pengguna mengusulkan perubahan struktur dengan mengemas semua child dari sebuah node secara berdekatan. Dengan begitu, daftar semua child dari sebuah node dapat ditemukan melalui pencarian biner dan tetap memiliki sifat yang ramah cache.
• Ada komentar tentang penyebutan indeks dalam array sebagai "handle" atau "index-handle", serta bahwa bentuk representasi tree ini mengingatkan pada struktur data klasik seperti heap dan disjoint set.
• Terakhir, ada komentar yang menjelaskan bahwa indeks array juga bisa dianggap sebagai sejenis "pointer", dan bahwa implementasi tree tradisional memerlukan malloc karena kebutuhan untuk menambah atau menghapus node secara dinamis. Jika ukuran tree terbatas dan penghapusan jarang dilakukan, implementasi berbasis array bisa menjadi pilihan yang cocok.