Apakah pohon biner melayani tujuan khusus dalam menyimpan data hierarkis? Apa penggunaan kanonik mereka?

12

Saya memahami struktur pohon biner dan cara melintasinya. Namun, saya berjuang untuk menyadari kegunaan sebenarnya, tujuan dalam program dan pemrograman. Ketika saya memikirkan contoh 'kehidupan nyata' dari data hierarkis, mereka hampir pasti memiliki lebih dari 2 anak. Misalnya, dalam silsilah keluarga, seorang ibu mungkin sering memiliki lebih dari dua anak.

Apakah 'pohon biner' benar-benar hanya berguna untuk menyimpan data terkait linier karena waktu pemrosesan lebih cepat dari array dan daftar? Atau, apakah mereka melayani tujuan tertentu dalam menyimpan data hierarkis? Jika demikian, contoh apa yang ada dari aplikasi pohon biner. Data apa yang sedemikian rupa sehingga simpul memiliki paling banyak 2 anak?

data-structures binary-tree sw123456
sumber
Saya pikir penggunaan utama pohon biner adalah untuk memesan data. https://en.wikipedia.org/wiki/Binary_search_tree
Mandrill

Jawaban:

25

Tidak, pohon biner bukan untuk menyimpan data hierarkis dalam arti yang Anda pikirkan. Kasus penggunaan utama untuk pohon n-ary, di mana nnomor tetap, adalah kemampuan pencarian cepat , bukan hierarki semantik.

Ingat permainan lama di mana satu orang memikirkan angka antara 1 dan 100, dan yang lain harus menebaknya sesedikit mungkin tebakan, dan jika Anda menebak salah, orang yang memikirkan nomor itu harus memberi tahu Anda jika Anda juga tinggi atau terlalu rendah? Menjadi membosankan setelah beberapa saat karena Anda dengan cepat mengetahui bahwa Anda harus selalu mulai dari 50, lalu pergi ke 25 atau 75, dan terus membagi rentang yang akan dicari setengah dengan setiap tebakan baru setelah itu, dan akhirnya Anda dapat menebak angka apa pun paling banyak 7 tebakan, dijamin.

Ini mungkin tidak cocok untuk permainan yang menyenangkan, tetapi properti itulah yang membuat pohon biner (dan n-ary lainnya) berguna: Anda dapat menggunakannya untuk mencari kumpulan data yang sangat besar dalam waktu yang sangat sedikit.

Mason Wheeler
sumber
Jawaban yang sangat bagus terima kasih banyak. Jadi, pohon biner benar-benar hanyalah struktur lain untuk menyimpan data seperti yang Anda lakukan dalam array atau daftar, tetapi dengan manfaat tambahan dari kemampuan pencarian cepat?
sw123456
1
@ sw123456: Benar. Seperti halnya teknik apa pun, ia disertai dengan pengorbanan, (menggunakan lebih banyak - dan lebih terfragmentasi - memori daripada array dengan jumlah elemen yang sama, O (n) akses ke elemen #n dari kumpulan data daripada O (1) akses, dll,) tetapi pencarian cepat jelas merupakan manfaat utama dari pohon biner.
Mason Wheeler
@ sw123456 Senang saya bisa membantu menjelaskannya :)
Mason Wheeler
3
Akses ke elemen adalah O (log (n)) ketika pohon seimbang. O (n) akan menjadi kasus terburuk ketika mengalami degenerasi (sebagian besar node hanya dengan satu braket).
Mandrill
@ sw123456 Perutean jaringan menggunakan sedikit modifikasi pohon biner yang disebut Trie (dibuat untuk efisiensi yang lebih besar untuk domain masalah). Itu benar-benar menyimpan informasi hierarki sebagai router melintasi pohon sedikit demi sedikit ketika mencari alamat IP untuk menemukan di mana ia harus meneruskan paket. Alamat IP juga secara alami bersifat hierarkis, jadi dalam melintasi IP untuk menemukan kecocokan awalan terpanjang, router melintasi hierarki IP, IP subnet, dll. Tidak semantik secara semantik, tetapi hubungannya ada. Router menggunakan struktur ini untuk efisiensi pencarian, seperti yang dijawab Mason.
Chris Cirefice
3

Setiap struktur pohon, di mana simpul dapat memiliki jumlah anak yang tidak terbatas, dapat diimplementasikan menggunakan pohon biner.

Untuk setiap simpul di pohon Anda, ganti dengan simpul dengan pointer kanan dan kiri. Pointer kiri pergi ke yang pertama dari anak-anak node. Node kanan menuju ke saudara kandung node berikutnya. Semua anak-anak dari node yang diberikan berada dalam daftar tertaut yang bergabung dengan pointer kanan mereka, dengan kepala daftar menunjuk oleh pointer kiri dari orang tua mereka.

Pohon n-ary Anda yang rumit telah menjadi pohon biner yang sederhana.

Saya yakin ini ada di Knuth, Vol. 1 di suatu tempat.

Justsalt
sumber
Ini adalah implementasi yang sangat menarik. Apakah saya benar dalam berpikir bahwa karena setiap simpul anak adalah awal dari daftar yang ditautkan, pohon tidak akan lagi menjadi O (log) n) jika seimbang atau O (n) jika tidak, karena fakta bahwa mengunjungi setiap simpul akan mulai dari pencarian linear? Implementasi ini akan menghasilkan waktu pencarian jauh lebih lambat? Tetapi pada terbalik, waktu pencarian akan lebih cepat daripada struktur linear standar? Sudahkah saya memahami ini dengan benar?
sw123456
@ sw123456, Jika pohon asli seimbang, pohon biner yang dihasilkan hampir pasti tidak. Saya percaya segalanya tergantung pada kipas dari pohon, berapa banyak anak yang dimiliki oleh simpul tertentu. Pencarian linear hanya akan terjadi ketika mencari tahu anak simpul mana yang harus diikuti. Tapi saya tidak yakin Anda bisa menghindarinya dalam implementasi pohon n-ary lainnya.
Justsalt
2

Pohon biner mengapa menggunakannya?

Dalam pemrograman Anda banyak bekerja dengan koleksi data tipe yang sama.

Dua cara dasar untuk menyimpan data ini adalah: daftar dan array yang ditautkan.

Keduanya memiliki kelebihan dan kekurangan: Dalam daftar tertaut, mudah untuk menambahkan elemen di posisi apa pun atau menghapus elemen. Tetapi akses ke elemen tertentu lebih sulit, karena Anda harus melalui daftar sampai Anda berada di elemen yang Anda inginkan.

  • Itu tidak mencari secara efisien tetapi memasukkan dan menghapus itu mudah.

Dengan akses array ke elemen tertentu itu mudah, tetapi lebih sulit untuk menyisipkan atau menghapus elemen karena memasukkan cara: memperpanjang array dengan satu, geser semua elemen sebelum posisi insert 1 ke kanan dan masukkan elemen.

  • Itu mencari secara efisien (jika diurutkan) tetapi memasukkan dan menghapus itu sulit.

Jadi baik daftar tertaut dan array memiliki kelemahan.

Pohon biner dibuat untuk mengatasi masalah array dan daftar tertaut:

  1. Sisipkan dan hapus dengan mudah
  2. Pencarian mudah

Jadi pohon biner dibuat ketika Anda memiliki banyak data yang berubah secara teratur.

Pieter B
sumber