Apakah pokok AA dalam C/C++?
Dalam sains komputer, pokok AA ditakrifkan sebagai pelaksanaan pokok yang seimbang untuk penyimpanan dan pengambilan data yang dipesan dengan cekap. Pokok AA dianggap sebagai varian pokok merah-hitam, pokok carian binari yang menyokong penambahan dan pemadaman entri yang cekap. Tidak seperti pokok merah-hitam, nod merah pada pokok AA hanya boleh ditambah sebagai nod anak kanan dan tidak boleh ditambah sebagai nod anak kiri. Hasil daripada operasi ini adalah untuk mensimulasikan pokok 2-3 dan bukannya pokok 2-3-4, dengan itu memudahkan operasi penyelenggaraan. Algoritma penyelenggaraan untuk pokok merah-hitam perlu menganggap atau mempertimbangkan tujuh bentuk berbeza untuk mengimbangi pokok dengan betul.
Bertentangan dengan pokok merah-hitam, pokok AA atau hanya perlu assume pertimbangkan dua bentuk kerana hanya pautan yang betul boleh menjadi merah.
putaran seimbang#🎜#🎜韎##🎜🎜🎜🎜 nod memerlukan satu bit metadata mengimbangi (warna), manakala pepohon AA memerlukan O(log(log(N))) bit metadata bagi setiap nod, dalam bentuk "tahap" integer. Invarian berikut digunakan untuk pokok AA:
- Tahap setiap nod daun dianggap sebagai 1.
- Tahap setiap nod anak kiri adalah 1 kurang daripada nod induknya.
- Tahap setiap nod anak kanan adalah sama dengan atau 1 kurang daripada nod induknya.
- Tahap setiap nod cucu kanan adalah lebih kecil daripada nod datuk neneknya.
- Setiap nod dengan tahap lebih besar daripada 1 mempunyai dua nod anak.
- Menyeimbangkan semula pokok AA adalah lebih mudah daripada mengimbangi semula pokok merah-hitam.
Dalam pokok AA, hanya dua operasi berbeza diperlukan untuk memulihkan keseimbangan: "skew" dan "split". Skew dianggap sebagai putaran kanan, menggantikan subpokok yang terdiri daripada pautan mendatar kiri dengan pautan mendatar kanan. Dalam kes Split, ia membelok ke kiri dan meningkatkan tahap, menggantikan subpokok yang mengandungi dua pautan mendatar kanan yang kurang berturut-turut dengan dua atau lebih pautan mendatar kanan berturut-turut. Kedua-dua operasi "skew" dan "split" diterangkan di bawah.
Takrifan skew fungsi adalah seperti berikut:
input: An AA tree that needs to be rebalanced is represented by a node, t. output: The rebalanced AA tree is represented by another node. if nil(t) then return nil else if nil(left(t)) then return t else if level(left(t)) == level(t) then Exchange the pointers of horizontal left links. l = left(t) left(t) := right(l) right(l) := t return l else return t end if end function
#🎜🎜 #🎜🎜 Terjemahan bagi #function split ialah
ialah:input: An AA tree that needs to be rebalanced is represented by a node, t. output: The rebalanced AA tree is represented by another node. if nil(t) then return nil else if nil(right(t)) or nil(right(right(t))) then return t else if level(t) == level(right(right(t))) then We have two horizontal right links. The middle node is taken, elevate it, and return it. r = right(t) right(t) := left(r) left(r) := t level(r) := level(r) + 1 return r else return t end if end function
Atas ialah kandungan terperinci Apakah pokok AA dalam C/C++?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Butiran artikel ini C jenis pulangan fungsi, merangkumi asas (int, float, char, dan lain -lain), diperolehi (tatasusunan, petunjuk, struktur), dan jenis kekosongan. Pengkompil menentukan jenis pulangan melalui pengisytiharan fungsi dan pernyataan pulangan, menguatkuasakan

GULC adalah perpustakaan C berprestasi tinggi yang mengutamakan overhead yang minimum, inlining agresif, dan pengoptimuman pengkompil. Sesuai untuk aplikasi kritikal prestasi seperti perdagangan frekuensi tinggi dan sistem tertanam, reka bentuknya menekankan kesederhanaan, modul

Artikel ini menerangkan perisytiharan fungsi C vs definisi, argumen lulus (dengan nilai dan penunjuk), nilai pulangan, dan perangkap umum seperti kebocoran memori dan jenis ketidakcocokan. Ia menekankan pentingnya pengisytiharan modularity dan provi

Butiran artikel ini C berfungsi untuk penukaran kes rentetan. Ia menerangkan menggunakan ToUpper () dan Tolower () dari CType.H, meleleh melalui rentetan, dan mengendalikan terminator null. Perangkap biasa seperti melupakan ctype.h dan mengubahsuai literal rentetan adalah

Artikel ini mengkaji fungsi penyimpanan nilai pulangan C. Nilai pulangan kecil biasanya disimpan dalam daftar untuk kelajuan; Nilai yang lebih besar boleh menggunakan petunjuk untuk memori (timbunan atau timbunan), memberi kesan kepada seumur hidup dan memerlukan pengurusan memori manual. Secara langsung acc

Artikel ini menganalisis kegunaan pelbagai kata sifat "berbeza," meneroka fungsi tatabahasa, frasa umum (mis., "Berbeza," "berbeza"), dan aplikasi bernuansa dalam formal vs tidak formal

Artikel ini memperincikan penggunaan algoritma STL yang cekap dalam c. Ia menekankan pilihan struktur data (vektor vs senarai), analisis kerumitan algoritma (mis., Std :: Sort vs Std :: partial_sort), penggunaan iterator, dan pelaksanaan selari. Perangkap biasa seperti

Artikel ini menerangkan Perpustakaan Templat St Standard (STL), yang memberi tumpuan kepada komponen terasnya: bekas, iterator, algoritma, dan functors. Ia memperincikan bagaimana ini berinteraksi untuk membolehkan pengaturcaraan generik, meningkatkan kecekapan kod dan kebolehbacaan t
