Rumah pembangunan bahagian belakang C++ Timbunan binari dan pokok carian binari dalam C++

Timbunan binari dan pokok carian binari dalam C++

Aug 22, 2023 pm 04:10 PM
c++ pokok carian binari timbunan binari

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Alat AI Hot

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

Video Face Swap

Video Face Swap

Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Alat panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

T Teknik Inisialisasi T Teknik Inisialisasi Jul 18, 2025 am 04:13 AM

Terdapat banyak kaedah permulaan dalam C, yang sesuai untuk senario yang berbeza. 1. Inisialisasi Variabel Asas termasuk permulaan tugasan (Inta = 5;), Inisialisasi Pembinaan (Inta (5);) dan Senarai Inisialisasi (Inta {5};), di mana senarai permulaan lebih ketat dan disyorkan; 2. Inisialisasi Ahli Kelas boleh diberikan melalui Senarai Inisialisasi Badan Pembina atau Ahli (MyClass (INTVAL): X (Val) {}), yang lebih cekap dan sesuai untuk ahli -ahli Const dan Rujukan. C 11 juga menyokong permulaan langsung dalam kelas; 3. Arus dan permulaan kontena boleh digunakan dalam mod tradisional atau C 11's std :: array dan std :: vektor, senarai sokongan sokongan dan meningkatkan keselamatan; 4. Inisialisasi lalai

Terangkan raii di c Terangkan raii di c Jul 22, 2025 am 03:27 AM

RAII adalah teknologi penting yang digunakan dalam pengurusan sumber dalam C. terasnya terletak pada menguruskan sumber secara automatik melalui kitaran hayat objek. Idea terasnya ialah: Sumber diperoleh pada masa pembinaan dan dikeluarkan pada kemusnahan, dengan itu mengelakkan masalah kebocoran yang disebabkan oleh pelepasan manual. Sebagai contoh, apabila tidak ada RAII, operasi fail memerlukan secara manual memanggil fclose. Sekiranya terdapat ralat di tengah atau kembali terlebih dahulu, anda mungkin lupa untuk menutup fail; Dan selepas menggunakan RAII, seperti kelas FileHandle yang merangkumi operasi fail, destructor akan dipanggil secara automatik selepas meninggalkan skop untuk melepaskan sumber. 1.RAII digunakan dalam pengurusan kunci (seperti STD :: LOCK_GUARD), 2.

Apakah pemusnah dalam C? Apakah pemusnah dalam C? Jul 19, 2025 am 03:15 AM

Destructor dalam C adalah fungsi ahli khas yang secara automatik dipanggil apabila objek keluar dari skop atau secara eksplisit dipadam. Tujuan utamanya adalah untuk membersihkan sumber yang boleh diperolehi oleh objek semasa kitaran hayatnya, seperti memori, pemegang fail, atau sambungan rangkaian. Destructor secara automatik dipanggil dalam kes -kes berikut: Apabila pembolehubah setempat meninggalkan skop, apabila padam dipanggil pada penunjuk, dan apabila objek luaran yang mengandungi objek itu dimusnahkan. Apabila menentukan pemusnah, anda perlu menambah ~ sebelum nama kelas, dan tidak ada parameter dan nilai pulangan. Sekiranya tidak ditentukan, pengkompil menghasilkan pemusnah lalai, tetapi tidak mengendalikan siaran memori dinamik. Nota termasuk: Setiap kelas hanya boleh mempunyai satu pemusnah dan tidak menyokong beban yang berlebihan; Adalah disyorkan untuk menetapkan pemusnah kelas yang diwarisi kepada maya; Pemusnahan kelas yang diperolehi akan dilaksanakan terlebih dahulu dan kemudian dipanggil secara automatik.

Apakah perdagangan mata wang maya frekuensi tinggi? Prinsip dan Titik Pelaksanaan Teknikal Perdagangan Kekerapan Tinggi Apakah perdagangan mata wang maya frekuensi tinggi? Prinsip dan Titik Pelaksanaan Teknikal Perdagangan Kekerapan Tinggi Jul 23, 2025 pm 11:57 PM

Perdagangan frekuensi tinggi adalah salah satu kawasan yang paling kaya dengan teknologi dan modal dalam pasaran mata wang maya. Ini adalah persaingan mengenai kelajuan, algoritma dan teknologi canggih yang peserta pasaran biasa sukar untuk terlibat. Memahami bagaimana ia berfungsi akan membantu kita untuk mempunyai pemahaman yang lebih mendalam tentang kerumitan dan pengkhususan pasaran aset digital semasa. Bagi kebanyakan orang, lebih penting untuk mengenali dan memahami fenomena ini daripada mencuba sendiri.

Menggunakan std :: pilihan dalam c Menggunakan std :: pilihan dalam c Jul 21, 2025 am 01:52 AM

Untuk menentukan sama ada std :: pilihan mempunyai nilai, anda boleh menggunakan kaedah has_value () atau secara langsung menilai dalam pernyataan IF; Apabila mengembalikan hasil yang mungkin kosong, disarankan untuk menggunakan STD :: Pilihan untuk mengelakkan petunjuk dan pengecualian null; Ia tidak boleh disalahgunakan, dan nilai pulangan Boolean atau pembolehubah bool bebas lebih sesuai dalam beberapa senario; Kaedah permulaan adalah pelbagai, tetapi anda perlu memberi perhatian untuk menggunakan Reset () untuk membersihkan nilai, dan memberi perhatian kepada kitaran hayat dan tingkah laku pembinaan.

Pengendali bitwise C dijelaskan Pengendali bitwise C dijelaskan Jul 18, 2025 am 03:52 AM

Pengendali bit di C digunakan untuk mengendalikan bit binari integer secara langsung, dan sesuai untuk pengaturcaraan sistem, pembangunan tertanam, pengoptimuman algoritma dan bidang lain. 1. Pengendali bit biasa termasuk bitwise dan (&), bitwise atau (|), bitwise xor (^), songsang bitwise (~), dan shift kiri (). 2. Gunakan senario pengurusan bendera negara, operasi topeng, pengoptimuman prestasi, dan algoritma penyulitan/mampatan. 3. Nota termasuk membezakan operasi bit dari operasi logik, mengelakkan peralihan kanan yang tidak selamat ke nombor yang ditandatangani, dan tidak terlalu banyak yang menjejaskan kebolehbacaan. Ia juga disyorkan untuk menggunakan makro atau pemalar untuk meningkatkan kejelasan kod, memberi perhatian kepada perintah operasi, dan mengesahkan tingkah laku melalui ujian.

Bagaimana cara menukar rentetan ke huruf besar atau huruf kecil dalam c? Bagaimana cara menukar rentetan ke huruf besar atau huruf kecil dalam c? Jul 19, 2025 am 01:34 AM

InC ,stringscanbeconvertedtouppercaseorlowercasebyprocessingeachcharacterusingstd::toupperorstd::tolowerfrom1.Casteachcharactertounsignedcharbeforeapplyingthefunctiontoavoidundefinedbehavior.2.Modifycharactersinplaceorcopythestringifpreservingtheori

Cara Membangunkan Ringkasan Teks Berasaskan AI Dengan Teknologi Penapisan PHP Pantas Cara Membangunkan Ringkasan Teks Berasaskan AI Dengan Teknologi Penapisan PHP Pantas Jul 25, 2025 pm 05:57 PM

Inti perkembangan PHP Ringkasan Teks AI adalah untuk memanggil API perkhidmatan AI luaran (seperti OpenAI, HuggingFace) sebagai penyelaras untuk merealisasikan pra -proses teks, permintaan API, analisis tindak balas dan paparan hasil; 2. Batasan adalah bahawa prestasi pengkomputeran lemah dan ekosistem AI lemah. Strategi tindak balas adalah untuk memanfaatkan API, decoupling perkhidmatan dan pemprosesan tak segerak; 3. Pemilihan model perlu menimbang ringkasan kualiti, kos, kelewatan, keserasian, privasi data, dan model abstrak seperti GPT atau BART/T5 adalah disyorkan; 4. Pengoptimuman prestasi termasuk cache, antrian asynchronous, pemprosesan batch dan pemilihan kawasan berdekatan. Pemprosesan ralat perlu meliputi had semasa semula, masa tamat rangkaian, keselamatan utama, pengesahan input dan pembalakan untuk memastikan operasi sistem yang stabil dan cekap.

See all articles