Timbunan binari dan pokok carian binari dalam C++

Dalam pengaturcaraan C++, timbunan binari dan pepohon carian binari ialah dua struktur data yang biasa digunakan. Mereka mempunyai persamaan, tetapi mereka juga mempunyai perbezaan. Artikel ini akan memperkenalkan konsep, operasi asas dan senario aplikasi timbunan binari dan pepohon carian binari masing-masing. Timbunan binari nod tidak lebih besar daripada (atau tidak kurang daripada) nilai nod induknya. Di sini kita mengambil timbunan maks sebagai contoh, iaitu, nilai nod akar ialah nilai terbesar dalam keseluruhan pokok, dan nilai semua nod anak adalah kurang daripada atau sama dengan nilai nod akar.

1.1.2 Sifat Pokok Binari Lengkap

Kecuali lapisan paling bawah, semua lapisan lain mesti diisi, dan semua nod mesti dijajarkan ke kiri.

Di sini tatasusunan berikut digunakan untuk mewakili timbunan maksimum:

[ 16, 14, 10, 8, 7, 9, 3, 2, 4 , 1 ]

Timbunan yang sepadan adalah seperti yang ditunjukkan di bawah:

16

/

14 10

/ /

8 7 9 3

/

2 4

1

1.2 Operasi asas

1.2.1 Operasi sisipan

ke dalam "sisipkan binari atas elemen "ap baru" " kaedah:

Masukkan elemen baharu ke ruang kosong paling kiri di bahagian bawah timbunan;

Bandingkan elemen baharu dengan nod induknya, jika nilai elemen baharu lebih besar daripada nod induknya , kemudian tukar kedudukan kedua-dua, dan ulangi proses ini sehingga elemen baharu tidak lagi lebih besar daripada nod induknya, atau mencapai bahagian atas timbunan. . bahagian bawah timbunan dilaraskan Pertukaran elemen;

Padamkan unsur atas timbunan yang asal

Bandingkan elemen atas timbunan yang baharu dengan nod anak selapis jika nilainya kurang daripada nilai maksimum dalam anak nod, bandingkan dengan nilai maksimum dalam nod anak Nilai ditukar dan proses ini diulang sehingga susunan timbunan berpuas hati.

1.3 Senario aplikasi
Timbunan binari selalunya digunakan untuk melaksanakan baris gilir keutamaan dan algoritma pengisihan berasaskan timbunan, seperti pengisihan timbunan, masalah topK, dsb.
2. Pokok Carian Binari

2.1 Konsep

Pokok Carian Binari (BST) ialah pokok tertib yang memenuhi sifat berikut:

2.1.1 Nilai semua nod pada subpokok kiri adalah sama kurang daripada nilai nod akarnya.
2.1.2 Nilai semua nod pada subpokok kanan adalah lebih besar daripada nilai nod akarnya.
2.1.3 Subpokok kiri dan kanan juga merupakan pokok carian binari masing-masing.
Ambil pokok berikut sebagai contoh:

    6
  /   
 2     7

/

1 4 9

   /    /
  3   5 8

Kemudian ia adalah pokok carian binari. . carian rekursif Subtree kiri/kanan.

2.2.2 Operasi Penyisipan

Operasi memasukkan nod baru ke dalam pokok carian binari memerlukan perbandingan bermula dari nod akar dan mencari kedudukan di mana ia perlu dimasukkan. berpuas hati.

2.2.3 Padam operasi

Operasi memadamkan nod dalam pokok carian binari boleh dibahagikan kepada tiga situasi:

The node yang akan dihapuskan adalah nod daun, hanya padamkannya secara langsung; satu nod untuk dipadamkan

Apabila nod yang akan dipadamkan mempunyai dua nod anak, gantikan nod dengan nod terkecil subpokok kanan nod dan padam nod terkecil subpohon kanan nod.

2.3 Senario Aplikasi

Pepohon carian binari sering digunakan untuk melaksanakan senario dengan operasi carian dan sisipan seperti kamus dan jadual simbol Prestasi carian adalah berkaitan dengan pengedaran data.

3. Perbandingan Timbunan Binari dan Pokok Carian Binari

3.1 Kesamaan

Timbunan binari dan pokok carian binari adalah kedua-dua pokok binari dan mempunyai beberapa sifat yang sama:

Kedudukan awal nod akar boleh menjadi mana-mana nod;

boleh digunakan untuk melaksanakan baris gilir keutamaan; . untuk memastikan setiap nod memenuhi susunan timbunan; dalam pepohon carian binari, saiz elemen mempunyai peraturan pengisihan tertentu, iaitu, ia memenuhi sifat kiri kecil dan kanan besar.

3.2.2 Akses nilai minimum/maksimum

Dalam timbunan binari, nilai maksimum/minimum boleh diakses dalam masa O(1), iaitu, ia diperoleh dalam nod akar, tetapi kerumitan masa untuk mengakses yang lain elemen ialah O( logn); dalam pepohon carian binari, mencari nilai minimum/maksimum memerlukan merentasi subpohon, dan kerumitan masa juga O(logn).

• 3.2.3 Operasi pemadaman dan pemasukan
• Dalam timbunan binari, setiap operasi pemadaman dan pemasukan mesti mengikut susunan timbunan, iaitu, kerumitan masa O(logn); daripada nod dan memasukkan nod baharu adalah berkaitan dengan ketinggian pokok, jadi dalam kes yang paling teruk ia mungkin memerlukan kerumitan masa O(n).
• 3.3 Cadangan Pemilihan

Apabila memilih timbunan binari dan pepohon carian binari, anda perlu memilih mengikut syarat khusus senario aplikasi.

Jika anda perlu mendapatkan nilai minimum/maksimum dengan cepat dan tidak mempunyai keperluan khas pada saiz elemen, anda boleh memberi keutamaan kepada timbunan binari.

Jika anda perlu memasukkan/memadam elemen dengan cepat dan saiz elemen perlu diisih dalam susunan tertentu, anda boleh mempertimbangkan untuk memilih pepohon carian binari.

IV. Kesimpulan

Ringkasnya, timbunan binari dan pepohon carian binari adalah kedua-dua struktur data yang penting dan mempunyai kelebihan dan kekurangan mereka sendiri dalam senario yang berbeza. Memahami konsep, operasi asas dan senario aplikasi timbunan binari dan pokok carian binari adalah sangat penting untuk menulis program yang cekap.

Atas ialah kandungan terperinci Timbunan binari dan pokok carian binari dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!