Video: Struktur Data Graph & Pohon Telusur Biner 2024
Jenis struktur pohon khusus adalah tumpukan biner, yang menempatkan masing-masing elemen simpul dalam urutan khusus. Pohon pencarian memungkinkan Anda mencari data dengan cepat. Mendapatkan item data, menempatkannya dalam urutan yang diurutkan di pohon, dan kemudian mencari pohon itu adalah salah satu cara yang lebih cepat untuk menemukan informasi.
Dalam tumpukan biner, simpul akar selalu berisi nilai terkecil. Saat melihat cabang, Anda melihat bahwa cabang tingkat atas selalu bernilai lebih kecil daripada cabang dan daun tingkat rendah. Efeknya adalah menjaga agar pohon tetap seimbang dan dalam urutan yang dapat diprediksi sehingga pencarian menjadi sangat efisien. Biayanya adalah menjaga agar pohon seimbang.
Dari semua tugas yang dilakukan aplikasi, pencarian adalah waktu yang lebih banyak dan juga yang paling dibutuhkan. Meskipun menambahkan data (dan menyortirnya nanti) memerlukan beberapa waktu, manfaat untuk membuat dan memelihara kumpulan data berasal dari menggunakannya untuk melakukan pekerjaan yang bermanfaat, yang berarti mencari informasi penting. Akibatnya, terkadang Anda bisa mendapatkan fungsi CRUD yang kurang efisien dan bahkan rutinitas yang kurang optimal, namun penelusuran harus berjalan seefisien mungkin. Satu-satunya masalah adalah tidak ada satu pencarian yang melakukan setiap tugas dengan efisiensi absolut, jadi Anda harus mempertimbangkan pilihan Anda berdasarkan apa yang Anda harapkan untuk dilakukan sebagai bagian dari rutin pencarian.
Dua metode pencarian yang lebih efisien melibatkan penggunaan binary search tree (BST) dan binary heap. Kedua teknik pencarian bergantung pada struktur mirip pohon untuk menahan tombol yang digunakan untuk mengakses elemen data. Namun, penataan kedua metode berbeda, oleh karena itulah seseorang memiliki kelebihan dibandingkan saat melakukan tugas tertentu. Angka ini menunjukkan susunan untuk BST.
Perhatikan bagaimana tombol mengikuti perintah di mana nomor yang lebih kecil muncul di sebelah kiri dan angka yang lebih besar muncul di sebelah kanan. Simpul akar berisi nilai yang berada di tengah kisaran tombol, memberi BST pendekatan keseimbangan yang mudah dipahami untuk menyimpan kunci. Bandingkan pengaturan ini dengan tumpukan biner yang ditunjukkan di sini.
Setiap level berisi nilai yang kurang dari level sebelumnya, dan root berisi nilai kunci maksimum untuk pohon. Selain itu, dalam kasus khusus ini, nilai yang lebih rendah muncul di sebelah kiri dan yang lebih besar di sebelah kanan (walaupun perintah ini tidak diterapkan secara ketat). Angka tersebut sebenarnya menggambarkan tumpukan heksadesimal. Anda juga dapat membuat tumpukan biner Seperti yang telah dicatat sebelumnya, BST memiliki beberapa keuntungan dibandingkan tumpukan biner saat digunakan untuk melakukan pencarian. Daftar berikut ini memberikan beberapa keunggulan dari kelebihan ini: Apakah saat-saat ini penting bergantung pada aplikasi Anda. BST cenderung bekerja paling baik dalam situasi di mana Anda menghabiskan lebih banyak waktu untuk mencari dan sedikit waktu membangun pohon. Tumpukan biner cenderung bekerja paling baik dalam situasi dinamis dimana kunci berubah secara teratur. Tumpukan biner juga menawarkan keuntungan, seperti yang dijelaskan dalam daftar berikut:
