Pohon pencarian adalah struktur data yang digunakan dalam pemrograman komputer untuk menampung dan mengatur daftar data. Setiap pohon pencarian terdiri dari kumpulan node yang berurutan. Node ini dapat dihubungkan ke nol atau lebih lainnya. node. Node individual berisi beberapa data serta tautan ke node lain. Data yang terkandung dalam node pohon sangat sering diurutkan dalam beberapa cara untuk memungkinkan algoritma yang efisien untuk mencari, menyisipkan dan menghapus node dengan mudah.
Node dari pohon pencarian dijelaskan dengan empat istilah penting. Bagian atas pohon, di mana node pertama berada, disebut root. Jika sebuah node berisi link ke sub -node, node tersebut dikenal sebagai parent. Node yang berada di bawah parent disebut child, dan setiap node yang tidak memiliki child node disebut leaf. Jadi, simpul akar diidentifikasi karena tidak memiliki orang tua, dan simpul daun tidak akan memiliki anak.
Sebuah program dapat bergerak melalui pohon mencari data dengan memulai pada node tertentu, melakukan pemeriksaan kondisional dan kemudian pindah ke node logis berikutnya jika data yang diperlukan tidak ada Tergantung pada struktur data yang digunakan , pencarian ini dapat memakan waktu yang bervariasi. Jika pohon pencarian diatur selama proses penambahan dan penghapusan node, pencarian dapat menjadi sangat cepat. Ketika sebuah pohon dirakit secara acak, tidak disortir atau memungkinkan banyak orang tua, pencarian dapat memakan waktu yang sangat lama.
Salah satu faktor yang mempengaruhi penggunaan pohon pencarian adalah masalah keseimbangan Pohon seimbang adalah pohon di mana anak-anak kanan dan kiri dari simpul akar mengandung kedalaman simpul anak yang sama atau berada dalam jumlah satu simpul. satu sama lain Kedalaman pohon adalah jumlah node dari daun terendah pohon ke akar Sebuah pohon tidak seimbang bisa memiliki semua node hanya pada satu sisi atau memiliki semua node diatur secara linier tanpa cabang.Ketika kedalaman pohon meningkat, kecepatan algoritma pencarian dapat menurun secara dramatis.
Ada beberapa jenis pohon pencarian yang digambarkan sebagai self-balancing. Pohon-pohon ini menggunakan operasi seperti rotasi pohon untuk membantu menjaga keseimbangan sambil menjaga urutan data di daun. Meskipun melakukan Rotasi pohon mungkin memperlambat program saat menambah dan menghapus node, hal ini diimbangi dengan kecepatan pengambilan data.
Meskipun ada banyak jenis pohon pencarian, struktur data pohon yang paling umum adalah pohon pencarian biner. Tipe data ini terdiri dari node yang masing-masing memiliki nol hingga dua node anak. Hanya ada satu node root, dan semua daun di pohon diurutkan dari kiri ke kanan dalam nilai naik sesuai dengan data yang mereka pegang. Banyak algoritma yang ada untuk pohon pencarian biner yang dapat membuat pemesanan data sangat mudah.
Tidak ada implementasi standar tunggal untuk node pohon pencarian Node dapat diwakili oleh berbagai macam struktur data Array array dapat digunakan, seperti juga dapat memperbanyak daftar tertaut Seringkali, sebuah pohon pencarian menggunakan struktur data khusus yang dirancang untuk membantu penyelesaian operasi yang diperlukan yang dipanggil oleh program. Beberapa perpustakaan pemrograman standar bahkan menyertakan implementasi internal pohon pencarian mereka sendiri.