Apakah pohon diorganisasi oleh struktur “anak pertama, selanjutnya”? Jika tidak, mengapa tidak?

Biasanya, struktur data pohon disusun sedemikian rupa sehingga setiap node berisi pointer ke semua anaknya.

       +-----------------------------------------+
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------------+    +---------------+    +---------------+
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Ini terlihat alami, tetapi ada beberapa masalah. Misalnya, ketika jumlah node anak bervariasi, Anda memerlukan sesuatu seperti array atau daftar untuk mengelola childs.

Dengan hanya menggunakan anak (pertama) dan petunjuk saudara (selanjutnya), kita mendapatkan sesuatu yang terlihat seperti itu:

       +-------------------+
       |        root       |
       | child    sibling  +--->NULL
       +--+----------------+
          |             
+----------------+    +----------------+    +----------------+
|    node1       |    |     node2      |    |     node3      |
| child  sibling +--->| child  sibling +--->| child  sibling +--->NULL
+--+-------------+    +--+-------------+    +--+-------------+
   |                     |                     |

Jelas sekali, struktur semacam ini dapat mewakili pohon juga, tetapi juga menawarkan beberapa keuntungan. Yang paling penting adalah bahwa kita tidak perlu khawatir tentang jumlah simpul anak lagi. Ketika digunakan untuk pohon parse, ia menawarkan representasi alami untuk istilah seperti "a + b + c + d + e" tanpa menjadi pohon yang dalam.

Apakah perpustakaan koleksi menawarkan struktur pohon seperti itu? Apakah parser menggunakan struktur seperti itu? Jika tidak, apa alasannya?

Pohon, seperti daftar, adalah "tipe data abstrak" yang dapat diimplementasikan dengan berbagai cara. Setiap cara memiliki kelebihan dan kekurangan.

Dalam contoh pertama, keuntungan utama dari struktur ini adalah Anda dapat mengakses anak mana pun di O (1). Kerugiannya adalah menambahkan anak kadang-kadang mungkin sedikit lebih mahal ketika array harus diperluas. Biaya ini relatif kecil. Ini juga salah satu implementasi paling sederhana.

Pada contoh kedua, keuntungan utama adalah Anda selalu menambahkan anak di O (1). Kerugian utama adalah bahwa akses acak ke anak biaya O (n). Juga, itu mungkin kurang menarik untuk pohon besar karena dua alasan: ia memiliki overhead memori dari satu objek header dan dua pointer per node, dan node secara acak tersebar di memori yang dapat menyebabkan banyak pertukaran antara cache CPU dan memori ketika pohon dilintasi, membuat implementasi ini kurang menarik bagi mereka. Ini bukan masalah untuk pohon normal dan aplikasi.

Satu kemungkinan menarik terakhir yang tidak disebutkan adalah untuk menyimpan seluruh pohon dalam satu array. Ini mengarah ke kode yang lebih kompleks, tetapi kadang-kadang implementasi yang sangat menguntungkan dalam kasus-kasus tertentu, terutama untuk pohon tetap besar, karena Anda dapat menghemat biaya header objek dan mengalokasikan memori yang berdekatan.

Hampir setiap proyek yang memiliki beberapa model atau dokumen yang dapat diedit akan memiliki struktur hierarki. Dapat berguna untuk mengimplementasikan 'simpul hierarkis' sebagai kelas dasar untuk entitas yang berbeda. Seringkali daftar terkait (child sibling, model 2) adalah cara alami banyak perpustakaan kelas tumbuh, namun anak-anak mungkin dari berbagai jenis, dan mungkin " model objek " bukan apa yang kita pertimbangkan ketika berbicara tentang pohon pada umumnya.

Implementasi favorit saya dari pohon (simpul) dari model pertama Anda adalah satu-liner (dalam C #):

public class node : List<node> { /* props go here */ }

Mewarisi dari Daftar generik dari tipe Anda sendiri (atau mewarisi dari kumpulan generik lain dari tipe Anda sendiri). Berjalan dimungkinkan dalam satu arah: bentuk root ke bawah (item tidak mengenal orang tua mereka).

Hanya pohon induk

Model lain yang tidak Anda sebutkan adalah model di mana setiap anak memiliki referensi ke orang tua itu:

               null
                 |
       +---------+---------------------------------+
       |       parent                              |
       | root                                      |
       +-------------------------------------------+
          |                   |                |
+---------+------+    +-------+--------+    +--+-------------+
|     parent     |    |     parent     |    |     parent     |
|     node 1     |    |     node 2     |    |     node 3     |
+----------------+    +----------------+    +----------------+

Berjalan pohon ini hanya mungkin sebaliknya, biasanya semua node ini akan disimpan dalam koleksi (array, hashtable, kamus dll.) Dan sebuah node akan ditemukan dengan mencari koleksi pada kriteria selain posisi hirarkis di pohon yang biasanya tidak terlalu penting.

Pohon induk saja ini biasanya terlihat dalam aplikasi basis data. Sangat mudah untuk menemukan anak-anak dari simpul dengan pernyataan "SELECT * WHERE ParentId = x". Namun kami jarang menemukan ini berubah menjadi objek kelas pohon-simpul seperti itu. Dalam aplikasi statefull (desktop) mereka dapat dibungkus ke dalam kontrol simpul pohon yang ada. Dalam aplikasi stateless (web) bahkan itu mungkin tidak mungkin. Saya telah melihat alat-alat kelas-generator pemetaan ORM melempar kesalahan stack overflow ketika membuat kelas untuk tabel yang memiliki hubungan dengan diri mereka sendiri (terkekeh), jadi mungkin pohon ini tidak begitu umum.

pohon dinavigasi dua arah

Namun dalam kebanyakan kasus praktis, nyaman untuk memiliki yang terbaik dari kedua dunia. Node yang memiliki daftar anak-anak dan selain itu mengenal orang tuanya: pohon dua arah yang dapat dinavigasi.

                          null
                            |
       +--------------------+--------------------+
       |                  parent                 |
       |        root                             | 
       | child1            child2         child3 |
       +--+------------------+----------------+--+
          |                  |                |
+---------+-----+    +-------+-------+    +---+-----------+
|      parent   |    |     parent    |    |  parent       |
|    node1      |    |     node2     |    |     node3     |
| child1 child2 |    | child1 child2 |    | child1 child2 |
+--+---------+--+    +--+---------+--+    +--+---------+--+
   |         |          |         |          |         |

Ini membawa lebih banyak aspek untuk dipertimbangkan:

• Di mana harus menerapkan penautan dan pembatalan tautan induk?
  • biarkan logika bisnis berhati-hati, dan biarkan aspek keluar dari simpul (mereka akan lupa!)
  • Node memiliki metode untuk membuat anak-anak (tidak memungkinkan pemesanan ulang) (pilihan Microsoft dalam implementasi DOM System.Xml.XmlDocument mereka, yang hampir membuat saya gila ketika saya pertama kali menemukannya)
  • Node mengambil induk di konstruktornya (tidak mengizinkan pemesanan ulang)
  • di semua add (), masukkan () dan hapus () metode dan kelebihan node mereka (biasanya pilihan saya)
• Ketekunan
  • Cara berjalan di pohon saat bertahan (misalkan tautan orangtua)
  • Cara membangun kembali penghubung dua arah setelah penghilangan bersambung (mengatur semua orang tua lagi sebagai tindakan pasca deserialisasi)
• Notifikasi
  • Mekanisme statis (bendera IsDirty), menangani properti secara rekursif?
  • Peristiwa, menggelembung melalui orang tua, turun melalui anak-anak, atau keduanya (pertimbangkan pompa pesan windows misalnya).

Sekarang untuk menjawab pertanyaan , pohon dua arah yang dapat dinavigasi cenderung (dalam karir dan bidang saya sejauh ini) yang paling banyak digunakan. Contohnya adalah implementasi Microsoft dari System.Windows.Forms.Control, atau System.Web.UI.Control dalam kerangka .Net, tetapi juga setiap implementasi DOM (Document Object Model) akan memiliki node yang mengetahui orang tua mereka serta enumerasi anak-anak mereka. Alasannya: kemudahan penggunaan lebih dari kemudahan implementasi. Juga, ini biasanya kelas dasar untuk kelas yang lebih spesifik (XmlNode mungkin basis Tag, Atribut, dan kelas Teks) dan kelas dasar ini adalah tempat alami untuk meletakkan serialisasi umum dan arsitektur penanganan peristiwa.

Tree terletak di jantung banyak arsitektur, dan mampu bernavigasi secara bebas berarti mampu mengimplementasikan solusi lebih cepat.

Saya tidak tahu ada perpustakaan kontainer yang secara langsung mendukung kasus kedua Anda, tetapi sebagian besar perpustakaan kontainer dapat dengan mudah mendukung skenario itu. Misalnya, di C ++ Anda bisa memiliki:

class Node;  // forward reference to satisfy the compiler
typedef std::list<Node*> NodeList;
class Node : public NodeList { /* . . . */ };  // a node is also a list

Node* n = new Node;
n->push_back(new Node);
Node* tree = new Node;
tree->push_back(new Node);
tree->push_back(n);

Parser mungkin menggunakan struktur yang mirip dengan ini, karena efisien mendukung node dengan jumlah variabel item dan anak-anak. Saya tidak tahu pasti karena saya biasanya tidak membaca kode sumber mereka.

Salah satu kasus ketika memiliki array anak lebih disukai adalah ketika Anda membutuhkan akses acak ke anak-anak. Dan ini biasanya ketika anak-anak disortir. Misalnya, hierarki hierarki mirip file dapat menggunakan ini untuk pencarian jalur yang lebih cepat. Atau tag tree DOM ketika akses indeks sangat alami

Contoh lain adalah ketika memiliki "petunjuk" untuk semua anak memungkinkan penggunaan yang lebih nyaman. Misalnya kedua tipe yang Anda gambarkan dapat digunakan saat mengimplementasikan hubungan pohon dengan basis data relasional. Tapi yang pertama (master-detail dari orang tua ke anak-anak dalam hal ini) akan memungkinkan permintaan dengan SQL umum untuk data yang berguna, sedangkan yang terakhir akan membatasi Anda secara signifikan.