Apa itu pohon pencarian?

Pohon pencarian adalah struktur data yang digunakan dalam pemrograman komputer untuk berisi dan mengatur daftar data. Setiap pohon pencarian terdiri dari set node yang dipesan. Node ini dapat dihubungkan ke nol atau lebihnode lain. Node individual berisi beberapa data serta tautan ke node lain. Data yang terkandung dalam node pohon sangat sering dipesan dalam beberapa cara untuk memungkinkan algoritma yang efisien untuk dicari,Masukkan dan lepaskan node dengan mudah.

Node dari pohon pencarian dijelaskan dengan empat istilah penting. Bagian atas pohon, di mana node pertama berada, disebut root.Jika sebuah simpul berisi tautan ke sub-node, simpul itu dikenal sebagai node orang tua yang berada di bawah orang tua disebut anak-anak, dan simpul apa pun yang tidak memiliki node anakdisebut daun. Jadi, simpul akar diidentifikasi karena tidak memiliki orang tua, dan node daun tidak memiliki anak.

Suatu program dapat bergerak melalui pohon mencari data dengan memulai dari simpul tertentu, melakukan pemeriksaan bersyarat dan kemudian pindah ke simpul logis berikutnya jika data yang diperlukan tidak ada. Tergantung pada struktur datadigunakan, pencarian ini dapat memakan waktu variabel. Jika pohon pencarian diatur selama proses penambahan dan menghilangkan node, pencarian bisa sangat cepat. Saat pohondirakit secara acak, tidak disortir atau memungkinkan banyak orang tua, pencarian dapat memakan waktu sangat lama.

Salah satu faktor yang mempengaruhi penggunaan pohon pencarian adalah masalah keseimbangan. Pohon seimbang adalahSalah satu di mana anak-anak kanan dan kiri dari simpul akar mengandung kedalaman node anak yang sama atau berada dalam jumlah satu simpul satu sama lain. Kedalaman pohon adalah jumlah node daridaun terendah pohon ke akar. Pohon yang tidak seimbang dapat memiliki semua node di satu sisi atau memiliki semua nodedisusun dengan cara linier tanpa cabang. Ketika kedalaman pohon meningkat, kecepatan algoritma pencarian dapat berkurang secara dramatis.

Ada beberapa jenis pohon pencarian yang digambarkan sebagai penyeimbangan diri.Pohon -pohon ini menggunakan operasi seperti rotasi pohon untuk membantu menjaga keseimbangan sambil menjaga urutan data dalam daun. Meskipun melakukan rotasi pohon mungkin memperlambat program saat menambahkan dan menghapus node,Ini dilawan oleh kecepatan di mana data dapat diambil.

Meskipun ada banyak jenis pohon pencarian, struktur data pohon yang paling umum adalah pohon pencarian biner. Jenis data ini terdiri dari node yang masing -masing memiliki nolke dua node anak. Hanya ada satu node akar, dan semua daun di pohon dipesan dari kiri ke kanan dalam nilai naik sesuai dengan data yang mereka pegang. BanyakAlgoritma ada untuk pohon pencarian biner yang dapat membuat data pemesanan sangat mudah.

Tidak ada standar tunggal implementasi untuk node pohon pencarian. Node dapat diwakili oleh berbagai macam struktur data. Array array dapat digunakan, seperti yang dapat melipatgandakan daftar yang terhubung. Seringkali, pohon pencarian menggunakan kustomStruktur data yang dirancang untuk membantu dalam penyelesaian operasi yang diperlukan yang diperlukan oleh program. Beberapa perpustakaan pemrograman standar bahkan menyertakan implementasi internal mereka sendiri dari pohon pencarian.