Video: Section 10 2024
Struktur pokok jenis khas adalah timbunan binari, yang menempatkan setiap elemen nod dalam perintah khas. Cari pokok membolehkan anda mencari data dengan cepat. Mendapatkan item data, meletakkannya dalam urutan yang disusun dalam pokok, dan kemudian mencari pokok itu adalah salah satu cara yang lebih cepat untuk mencari maklumat.
Dalam timbunan binari, nod akar sentiasa mengandungi nilai terkecil. Apabila melihat cawangan, anda melihat cawangan peringkat atas sentiasa menjadi nilai yang lebih kecil daripada cawangan dan daun peringkat rendah. Kesannya adalah untuk memastikan pokok itu seimbang dan dalam susunan yang dapat diprediksikan supaya carian menjadi sangat cekap. Kos dalam memastikan pokok itu seimbang.
Daripada semua tugas yang dilakukan oleh aplikasi, pencarian adalah lebih banyak memakan masa dan juga yang paling diperlukan. Walaupun menambah data (dan mengisih kemudian) memerlukan sedikit masa, manfaat untuk membuat dan mengekalkan dataset datang daripada menggunakannya untuk melaksanakan kerja yang berguna, yang bermaksud mencari maklumat penting. Akibatnya, anda kadang-kadang dapat dengan fungsi CRUD yang kurang berkesan dan bahkan rutin semakan yang kurang daripada optimum, tetapi carian mesti diteruskan secepat mungkin. Satu-satunya masalah adalah bahawa tiada satu carian melakukan setiap tugas dengan kecekapan mutlak, jadi anda harus mempertimbangkan pilihan anda berdasarkan apa yang anda harapkan untuk melakukan sebagai sebahagian dari rutin pencarian.
Dua kaedah mencari yang lebih cekap melibatkan penggunaan pokok carian binari (BST) dan timbunan binari. Kedua-dua teknik carian bergantung pada struktur seperti pohon untuk memegang kunci yang digunakan untuk mengakses elemen data. Walau bagaimanapun, susunan kedua-dua kaedah adalah berbeza, oleh itu, seseorang mempunyai kelebihan berbanding yang lain apabila melakukan tugas tertentu. Angka ini menunjukkan susunan untuk BST.
Perhatikan bagaimana kunci mengikut susunan di mana nombor yang lebih rendah muncul ke kiri dan bilangan yang lebih besar muncul di sebelah kanan. Nod akar mengandungi nilai yang berada di tengah-tengah pelbagai kekunci, memberikan BST pendekatan yang mudah difahami dengan seimbang untuk menyimpan kunci. Sebarkan susunan ini kepada timbunan binari yang ditunjukkan di sini.
Setiap peringkat mengandungi nilai yang kurang daripada tahap sebelumnya, dan akar mengandungi nilai utama maksimum untuk pokok itu. Di samping itu, dalam kes ini, nilai yang lebih rendah muncul di sebelah kiri dan yang lebih besar di sebelah kanan (walaupun pesanan ini tidak dikuatkuasakan dengan ketat). Angka itu sebenarnya menggambarkan timbunan maksimum binari. Anda juga boleh mencipta binary min binary di mana akar mengandungi nilai kunci terendah dan setiap peringkat dibina kepada nilai yang lebih tinggi, dengan nilai tertinggi muncul sebagai sebahagian daripada daun.
Seperti yang telah dinyatakan sebelumnya, BST mempunyai beberapa kelebihan berbanding tumpukan biner apabila digunakan untuk melakukan carian. Senarai berikut memberikan beberapa kemunculan kelebihan ini:
- Mencari elemen memerlukan waktu O (log n), berbanding dengan waktu O (n) untuk timbunan biner.
- Percetakan unsur-unsur dalam susunan memerlukan masa O (log n), berbeza dengan waktu O (n log n) untuk timbunan biner.
- Mencari lantai dan siling memerlukan masa O (log n).
- Mencari Kth elemen terkecil / terbesar memerlukan masa O (log n) apabila pohon dikonfigurasi dengan betul.
Sama ada masa-masa penting ini bergantung pada aplikasi anda. BST cenderung untuk bekerja dengan baik dalam situasi di mana anda menghabiskan lebih banyak masa mencari dan kurang masa membina pokok itu. Tumpukan binari cenderung untuk berfungsi dengan baik dalam keadaan dinamik di mana kunci berubah secara berkala. Punca binari juga menawarkan kelebihan, seperti yang dijelaskan dalam senarai berikut:
- Membuat struktur yang diperlukan memerlukan sumber yang lebih sedikit kerana timbunan binari bergantung pada tatasusunan, menjadikannya cache lebih baik juga.
- Membina timbunan binari memerlukan waktu O (n), berbanding BST, yang memerlukan masa O (n log n).
- Menggunakan petunjuk untuk melaksanakan pokok tidak perlu.
- Bergantung pada variasi timbunan binari (contohnya, Heap Fibonacci) menawarkan kelebihan seperti peningkatan dan pengurangan waktu utama masa O (1).
