Apa aplikasi pohon biner?

Saya bertanya-tanya apa aplikasi pohon biner tertentu. Bisakah Anda memberikan beberapa contoh nyata?

Bertengkar tentang kinerja pohon biner tidak ada artinya - mereka bukan struktur data, tetapi keluarga struktur data, semua dengan karakteristik kinerja yang berbeda. Meskipun benar bahwa pohon biner yang tidak seimbang berkinerja lebih buruk daripada pohon biner penyeimbang sendiri untuk pencarian, ada banyak pohon biner (seperti percobaan biner) yang "menyeimbangkan" tidak memiliki arti.

Aplikasi pohon biner

• Binary Search Tree - Digunakan di banyak aplikasi pencarian di mana data terus-menerus masuk / keluar, seperti objek mapdan setperpustakaan di banyak bahasa.
• Binary Space Partition - Digunakan di hampir setiap gim video 3D untuk menentukan objek apa yang perlu dirender.
• Binary Tries - Digunakan di hampir setiap router bandwidth tinggi untuk menyimpan tabel-router.
• Hash Trees - digunakan dalam program p2p dan gambar-tanda tangan khusus di mana hash perlu diverifikasi, tetapi keseluruhan file tidak tersedia.
• Heaps - Digunakan dalam mengimplementasikan antrian prioritas yang efisien, yang pada gilirannya digunakan untuk proses penjadwalan di banyak sistem operasi, Kualitas Layanan dalam router, dan A * (algoritma pencarian jalur yang digunakan dalam aplikasi AI, termasuk robotik dan video game) . Juga digunakan dalam heap-sort.
• Huffman Coding Tree ( Chip Uni ) - digunakan dalam algoritma kompresi, seperti yang digunakan oleh format file .jpeg dan .mp3.
• GGM Trees - Digunakan dalam aplikasi kriptografi untuk menghasilkan pohon angka pseudo-acak.
• Sintaksis Pohon - Dibangun oleh kompiler dan (secara implisit) kalkulator untuk mengurai ekspresi.
• Treap - Struktur data acak yang digunakan dalam jaringan nirkabel dan alokasi memori.
• T-tree - Meskipun sebagian besar database menggunakan beberapa bentuk B-tree untuk menyimpan data pada drive, database yang menyimpan semua (sebagian besar) data mereka dalam memori sering menggunakan T-tree untuk melakukannya.

Alasan bahwa pohon biner lebih sering digunakan daripada pohon n-ary untuk pencarian adalah bahwa pohon n-ary lebih kompleks, tetapi biasanya tidak memberikan keuntungan kecepatan nyata.

Dalam pohon biner (seimbang) dengan mnode, bergerak dari satu level ke level berikutnya membutuhkan satu perbandingan, dan ada log_2(m)level, untuk total log_2(m)perbandingan.

Sebaliknya, pohon n-ary akan membutuhkan log_2(n)perbandingan (menggunakan pencarian biner) untuk pindah ke tingkat berikutnya. Karena ada log_n(m)level total, pencarian akan memerlukan log_2(n)*log_n(m)= log_2(m)perbandingan total. Jadi, meskipun pohon n-ary lebih kompleks, mereka tidak memberikan keuntungan dalam hal perbandingan total yang diperlukan.

(Namun, pohon n-ary masih berguna dalam situasi khusus. Contoh yang langsung muncul di benak adalah pohon quad-tree dan pohon pemisah ruang lainnya, di mana ruang pembagian menggunakan hanya dua node per level akan membuat logika menjadi tidak perlu rumit; dan B-tree digunakan dalam banyak basis data, di mana faktor pembatasnya bukan berapa banyak perbandingan yang dilakukan pada setiap level tetapi berapa banyak node yang dapat dimuat dari hard-drive sekaligus)

Ketika kebanyakan orang berbicara tentang pohon biner, mereka lebih sering daripada tidak memikirkan pohon pencarian biner , jadi saya akan membahasnya terlebih dahulu.

Pohon pencarian biner yang tidak seimbang sebenarnya berguna untuk sedikit lebih banyak daripada mendidik siswa tentang struktur data. Itu karena, kecuali data masuk dalam urutan yang relatif acak, pohon dapat dengan mudah berubah menjadi bentuk kasus terburuk, yang merupakan daftar tertaut, karena pohon biner sederhana tidak seimbang.

Contoh bagus: Saya pernah memperbaiki beberapa perangkat lunak yang memuat datanya ke pohon biner untuk manipulasi dan pencarian. Itu menulis data dalam bentuk diurutkan:

Alice
Bob
Chloe
David
Edwina
Frank

sehingga, ketika membacanya kembali, berakhir dengan pohon berikut:

  Alice
 /     \
=       Bob
       /   \
      =     Chloe
           /     \
          =       David
                 /     \
                =       Edwina
                       /      \
                      =        Frank
                              /     \
                             =       =

yang merupakan bentuk merosot. Jika Anda mencari Frank di pohon itu, Anda harus mencari semua enam node sebelum menemukannya.

Pohon biner menjadi sangat berguna untuk pencarian saat Anda menyeimbangkannya. Ini melibatkan memutar sub-pohon melalui simpul akar mereka sehingga perbedaan tinggi antara dua sub-pohon kurang dari atau sama dengan 1. Menambahkan nama-nama di atas satu per satu ke dalam pohon seimbang akan memberi Anda urutan berikut:

1.   Alice
    /     \
   =       =

2.   Alice
    /     \
   =       Bob
          /   \
         =     =

3.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       =

4.        Bob
        _/   \_
   Alice       Chloe
  /     \     /     \
 =       =   =       David
                    /     \
                   =       =

5.           Bob
        ____/   \____
   Alice             David
  /     \           /     \
 =       =     Chloe       Edwina
              /     \     /      \
             =       =   =        =

6.              Chloe
            ___/     \___
         Bob             Edwina
        /   \           /      \
   Alice     =      David        Frank
  /     \          /     \      /     \
 =       =        =       =    =       =

Anda benar-benar dapat melihat seluruh sub-pohon berputar ke kiri (dalam langkah 3 dan 6) ketika entri ditambahkan dan ini memberi Anda pohon biner seimbang di mana pencarian kasus terburuk O(log N)daripada O(N) yang diberikan oleh formulir degenerasi. Pada titik tidak ada NULL tertinggi ( =) berbeda dari yang terendah lebih dari satu tingkat. Dan, di pohon terakhir di atas, Anda dapat menemukan Frank hanya dengan melihat tiga simpul ( Chloe, Edwinadan, akhirnya, Frank).

Tentu saja, mereka bisa menjadi lebih berguna ketika Anda membuatnya seimbang pohon multi-arah daripada pohon biner. Itu berarti bahwa setiap node memegang lebih dari satu item (secara teknis, mereka menyimpan N item dan N + 1 pointer, pohon biner menjadi kasus khusus dari pohon multi-arah 1 arah dengan 1 item dan 2 pointer).

Dengan pohon tiga arah, Anda berakhir dengan:

  Alice Bob Chloe
 /     |   |     \
=      =   =      David Edwina Frank
                 /     |      |     \
                =      =      =      =

Ini biasanya digunakan dalam memelihara kunci untuk indeks item. Saya telah menulis perangkat lunak basis data yang dioptimalkan untuk perangkat keras di mana sebuah simpul berukuran persis seperti blok disk (katakanlah, 512 byte) dan Anda memasukkan kunci sebanyak yang Anda bisa ke dalam satu simpul. The pointer dalam kasus ini sebenarnya jumlah rekor menjadi file langsung akses fixed-length-record terpisah dari file indeks (jumlah sehingga record Xdapat ditemukan dengan hanya berusaha untuk X * record_length).

Sebagai contoh, jika pointer adalah 4 byte dan ukuran kunci adalah 10, jumlah kunci dalam simpul 512-byte adalah 36. Itu adalah 36 kunci (360 byte) dan 37 pointer (148 byte) untuk total 508 byte dengan 4 byte terbuang per node.

Penggunaan kunci multi-arah memperkenalkan kompleksitas pencarian dua fase (pencarian multi-arah untuk menemukan node yang tepat dikombinasikan dengan pencarian sekuensial kecil (atau linear biner) untuk menemukan kunci yang benar dalam node) tetapi keuntungan dalam melakukan lebih sedikit disk I / O lebih dari make up untuk ini.

Saya tidak melihat alasan untuk melakukan ini untuk struktur dalam memori, Anda akan lebih baik tetap dengan pohon biner seimbang dan menjaga kode Anda sederhana.

Perlu diingat juga bahwa kelebihan O(log N)lebih O(N)tidak benar-benar muncul ketika set data Anda kecil. Jika Anda menggunakan pohon multi-arah untuk menyimpan lima belas orang di buku alamat Anda, itu mungkin berlebihan. Keuntungan datang ketika Anda menyimpan sesuatu seperti setiap pesanan dari seratus ribu pelanggan Anda selama sepuluh tahun terakhir.

Inti dari notasi O besar adalah untuk menunjukkan apa yang terjadi ketika Nmendekati tak terhingga. Beberapa orang mungkin tidak setuju tetapi bahkan tidak apa-apa untuk menggunakan semacam gelembung jika Anda yakin set data akan tetap di bawah ukuran tertentu, selama tidak ada lagi yang tersedia :-)

Adapun kegunaan lain untuk pohon biner, ada banyak sekali, seperti:

• Tumpukan biner di mana kunci yang lebih tinggi di atas atau sama dengan yang lebih rendah daripada di sebelah kiri (atau di bawah atau sama dengan dan kanan);
• Pohon hash, mirip dengan tabel hash;
• Pohon sintaksis abstrak untuk kompilasi bahasa komputer;
• Pohon Huffman untuk kompresi data;
• Routing tree untuk lalu lintas jaringan.

Mengingat seberapa banyak penjelasan yang saya hasilkan untuk pohon pencarian, saya ragu untuk membahas banyak hal lain, tetapi itu cukup untuk meneliti mereka, jika Anda menginginkannya.

Organisasi kode Morse adalah pohon biner.

Pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua simpul anak, biasanya dibedakan sebagai "kiri" dan "kanan". Node dengan anak-anak adalah node orang tua, dan node anak dapat berisi referensi ke orang tua mereka. Di luar pohon, sering ada referensi ke simpul "root" (leluhur semua simpul), jika ada. Setiap simpul dalam struktur data dapat dicapai dengan mulai dari simpul akar dan berulang kali mengikuti referensi ke anak kiri atau kanan. Dalam pohon biner, derajat setiap simpul adalah maksimum dua.

Pohon biner bermanfaat, karena seperti yang Anda lihat dalam gambar, jika Anda ingin menemukan simpul di pohon, Anda hanya perlu melihat maksimal 6 kali. Jika Anda ingin mencari simpul 24, misalnya, Anda akan mulai dari root.

• Root memiliki nilai 31, yang lebih besar dari 24, jadi Anda pergi ke simpul kiri.
• Node kiri memiliki nilai 15, yang kurang dari 24, jadi Anda pergi ke simpul kanan.
• Simpul kanan memiliki nilai 23, yang kurang dari 24, jadi Anda pergi ke simpul kanan.
• Simpul kanan memiliki nilai 27, yang lebih besar dari 24, jadi Anda pergi ke simpul kiri.
• Node kiri memiliki nilai 25, yang lebih besar dari 24, jadi Anda pergi ke node kiri.
• Node memiliki nilai 24, yang merupakan kunci yang kami cari.

Pencarian ini diilustrasikan di bawah ini:

Anda dapat melihat bahwa Anda dapat mengecualikan setengah dari seluruh simpul pohon pada pass pertama. dan setengah dari subtree kiri pada yang kedua. Ini menjadikan pencarian sangat efektif. Jika ini dilakukan pada 4 miliar elemen, Anda hanya perlu mencari maksimal 32 kali. Oleh karena itu, semakin banyak elemen yang terkandung dalam pohon, semakin efisien pencarian Anda.

Penghapusan bisa menjadi rumit. Jika simpul memiliki 0 atau 1 anak, maka itu hanya masalah memindahkan beberapa petunjuk untuk mengecualikan satu yang akan dihapus. Namun, Anda tidak dapat dengan mudah menghapus simpul dengan 2 anak. Jadi kami mengambil jalan pintas. Katakanlah kita ingin menghapus simpul 19.

Karena mencoba menentukan ke mana harus mengarahkan pointer kiri dan kanan tidaklah mudah, kami menemukan satu untuk menggantikannya. Kami pergi ke sub-pohon kiri, dan pergi sejauh yang kami bisa. Ini memberi kita nilai terbesar berikutnya dari simpul yang ingin kita hapus.

Sekarang kita menyalin semua konten 18, kecuali untuk pointer kiri dan kanan, dan menghapus 18 node asli.

Untuk membuat gambar-gambar ini, saya menerapkan pohon AVL, pohon penyeimbang sendiri, sehingga pada setiap titik waktu, pohon memiliki paling banyak satu tingkat perbedaan antara simpul daun (simpul tanpa anak). Ini menjaga pohon agar tidak miring dan mempertahankan O(log n)waktu pencarian maksimum , dengan biaya lebih banyak waktu yang diperlukan untuk penyisipan dan penghapusan.

Berikut adalah contoh yang menunjukkan bagaimana pohon AVL saya menjaga dirinya seringkas dan seimbang mungkin.

Dalam array yang diurutkan, pencarian masih akan mengambil O(log(n)), seperti pohon, tetapi penyisipan dan penghapusan acak akan mengambil O (n) bukan pohon O(log(n)). Beberapa wadah STL menggunakan karakteristik kinerja ini untuk keuntungan mereka sehingga waktu penyisipan dan pemindahan mengambil maksimum O(log n), yang sangat cepat. Beberapa kontainer ini map, multimap, set, dan multiset.

Kode contoh untuk pohon AVL dapat ditemukan di http://ideone.com/MheW8

Aplikasi utama adalah pohon pencarian biner . Ini adalah struktur data di mana pencarian, penyisipan, dan penghapusan semuanya sangat cepat (tentang log(n)operasi)

• Pohon biner digunakan dalam pengkodean Huffman , yang digunakan sebagai kode kompresi.
• Pohon biner digunakan dalam pohon pencarian Biner , yang berguna untuk memelihara catatan data tanpa banyak ruang ekstra.

Salah satu contoh menarik dari pohon biner yang belum disebutkan adalah ekspresi matematika yang dievaluasi secara rekursif. Ini pada dasarnya tidak berguna dari sudut pandang praktis, tetapi ini adalah cara yang menarik untuk memikirkan ekspresi seperti itu.

Pada dasarnya setiap simpul pohon memiliki nilai yang melekat pada dirinya sendiri atau dievaluasi secara rekursif dengan beroperasi pada nilai-nilai anak-anaknya.

Misalnya, ekspresi (1+3)*2dapat dinyatakan sebagai:

    *
   / \
  +   2
 / \
1   3

Untuk mengevaluasi ekspresi, kami meminta nilai induknya. Node ini pada gilirannya mendapatkan nilainya dari anak-anaknya, operator plus dan simpul yang hanya berisi '2'. Operator plus pada gilirannya mendapatkan nilainya dari anak-anak dengan nilai '1' dan '3' dan menambahkannya, mengembalikan 4 ke simpul multiplikasi yang mengembalikan 8.

Penggunaan pohon biner ini mirip dengan membalikkan notasi polish dalam arti, dalam urutan bahwa operasi dilakukan identik. Juga satu hal yang perlu diperhatikan adalah ia tidak harus berupa pohon biner, hanya saja operator yang paling umum digunakan adalah biner. Pada tingkat paling dasar, pohon biner di sini sebenarnya hanya bahasa pemrograman yang sangat fungsional murni.

Aplikasi pohon biner:

1. Menerapkan tabel routing di router .
2. Kode kompresi data
3. Implementasi parser Ekspresi dan pemecah ekspresi
4. Untuk mengatasi masalah basis data seperti pengindeksan .
5. Evaluasi ekspresi

Saya tidak berpikir ada gunanya untuk pohon biner "murni". (kecuali untuk tujuan pendidikan) Pohon biner seimbang, seperti pohon Merah-Hitam atau pohon AVL jauh lebih berguna, karena mereka menjamin operasi O (logn). Pohon biner normal mungkin berakhir menjadi daftar (atau hampir daftar) dan tidak benar-benar berguna dalam aplikasi yang menggunakan banyak data.

Pohon seimbang sering digunakan untuk mengimplementasikan peta atau set. Mereka juga dapat digunakan untuk menyortir dalam O (nlogn), bahkan ada cara yang lebih baik untuk melakukannya.

Juga untuk mencari / menyisipkan / menghapus tabel Hash dapat digunakan, yang biasanya memiliki kinerja yang lebih baik daripada pohon pencarian biner (seimbang atau tidak).

Sebuah aplikasi di mana pohon pencarian biner (seimbang) akan berguna jika pencarian / memasukkan / menghapus dan menyortir akan diperlukan. Sortasi bisa dilakukan di tempat (hampir, mengabaikan ruang stack yang diperlukan untuk rekursi), diberi pohon seimbang yang siap bangun. Itu masih akan menjadi O (nlogn) tetapi dengan faktor konstan yang lebih kecil dan tidak membutuhkan ruang tambahan (kecuali untuk array baru, dengan asumsi data harus dimasukkan ke dalam array). Tabel hash di sisi lain tidak dapat diurutkan (setidaknya tidak secara langsung).

Mungkin mereka juga berguna dalam beberapa algoritma canggih untuk melakukan sesuatu, tetapi tidak ada yang terlintas di pikiran saya. Jika saya menemukan lebih banyak saya akan mengedit posting saya.

Pohon lain seperti pohon fe B + banyak digunakan dalam database

Salah satu aplikasi yang paling umum adalah menyimpan data secara efisien dalam bentuk yang diurutkan untuk mengakses dan mencari elemen yang disimpan dengan cepat. Misalnya, std::mapatau std::setdi C ++ Standard Library.

Binary tree sebagai struktur data berguna untuk berbagai implementasi parser ekspresi dan pemecah ekspresi.

Ini juga dapat digunakan untuk memecahkan beberapa masalah basis data, misalnya pengindeksan.

Secara umum, pohon biner adalah konsep umum dari struktur data berbasis pohon tertentu dan berbagai jenis pohon biner dapat dibangun dengan properti yang berbeda.

Di C ++ STL, dan banyak perpustakaan standar lainnya dalam bahasa lain, seperti Java dan C #. Pohon pencarian biner digunakan untuk mengimplementasikan set dan peta.

Salah satu aplikasi paling penting dari pohon biner adalah pohon pencarian biner seimbang seperti:

• Pohon merah-hitam
• Pohon AVL
• Pohon kambing hitam

Jenis pohon ini memiliki properti yang perbedaan ketinggian subtree kiri dan subtree kanan dipertahankan kecil dengan melakukan operasi seperti rotasi setiap kali sebuah node dimasukkan atau dihapus.

Karena ini, ketinggian keseluruhan pohon tetap dari urutan log n dan operasi seperti pencarian, penyisipan dan penghapusan node dilakukan dalam waktu O (log n). STL dari C ++ juga mengimplementasikan pohon-pohon ini dalam bentuk set dan peta.

Mereka dapat digunakan sebagai cara cepat untuk mengurutkan data. Masukkan data ke dalam pohon pencarian biner di O (log (n)). Kemudian lintasi pohon untuk menyortirnya.

sintaksis program Anda, atau dalam hal ini banyak hal lain seperti bahasa alami dapat diuraikan menggunakan pohon biner (meskipun tidak harus).

Implementasi dari java.util.Set

Pada perangkat keras modern, pohon biner hampir selalu suboptimal karena cache yang buruk dan perilaku ruang. Ini juga berlaku untuk varian (semi) seimbang. Jika Anda menemukannya, itu adalah di mana kinerja tidak dihitung (atau didominasi oleh fungsi perbandingan), atau lebih mungkin karena alasan historis atau ketidaktahuan.

Kompiler yang menggunakan pohon biner untuk representasi AST, dapat menggunakan algoritma yang dikenal untuk mem-parsing pohon seperti postorder, inorder. Programer tidak perlu membuat algoritma sendiri. Karena pohon biner untuk file sumber lebih tinggi dari pohon n-ary, pembuatannya membutuhkan waktu lebih lama. Ambil produksi ini: selstmnt: = "if" "(" expr ")" stmnt "ELSE" stmnt Dalam pohon biner ia akan memiliki 3 tingkat node, tetapi pohon n-ary akan memiliki 1 level (chids)

Itu sebabnya OS-s berbasis Unix lambat.