Pohon pencarian biner - database terstruktur yang berisi node, dua tautan ke node lain, kanan dan kiri. Node adalah objek dari kelas yang memiliki data, dan NULL adalah tanda yang menandai akhir dari pohon.
Hal ini sering disebut sebagai BST, yang memiliki properti khusus: node yang lebih besar dari root terletak di sebelah kanannya, dan yang lebih kecil di sebelah kiri.
Teori dan terminologi umum
Dalam pohon pencarian biner, setiap simpul, tidak termasuk root, dihubungkan oleh tepi terarah dari satu simpul ke simpul lain, yang disebut induk. Masing-masing dari mereka dapat dihubungkan ke sejumlah node yang berubah-ubah, yang disebut anak-anak. Node tanpa "anak" disebut daun (node luar). Unsur yang bukan daun disebut internal. Node dengan orang tua yang sama adalah saudara kandung. Node paling atas disebut root. Di BST, tetapkan elemen ke setiap node dan pastikan mereka memiliki properti khusus yang ditetapkan untuk mereka.
Terminologi pohon:
- Kedalaman sebuah simpul adalah jumlah sisi yang didefinisikan dari akar hingga simpul tersebut.
- Tinggi sebuah simpul adalah jumlah tepi yang didefinisikan dari simpul tersebut hingga daun terdalam.
- Tinggi pohon ditentukan oleh tinggi akar.
- Pohon pencarian biner adalah desain khusus, memberikan rasio tinggi dan jumlah node terbaik.
- Tinggi h dengan N node paling banyak O (log N).
Anda dapat dengan mudah membuktikannya dengan menghitung simpul pada setiap level, mulai dari akar, dengan asumsi bahwa simpul tersebut berisi jumlah terbesar: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Memecahkan ini untuk h menghasilkan h=O (log n).
Manfaat kayu:
- Mencerminkan hubungan struktural data.
- Digunakan untuk mewakili hierarki.
- Pastikan instalasi dan pencarian yang efisien.
- Pohon adalah data yang sangat fleksibel, memungkinkan Anda untuk memindahkan subpohon dengan sedikit usaha.
Metode pencarian
Secara umum, untuk menentukan apakah suatu nilai ada dalam BST, mulailah pohon pencarian biner pada akarnya dan tentukan apakah memenuhi persyaratan:
- berada di root;
- berada di subpohon kiri root;
- di subpohon kanan root.
Jika tidak ada register dasar yang terpenuhi, pencarian rekursif dilakukan di subpohon yang sesuai. Sebenarnya ada dua opsi dasar:
- Pohon kosong - return false.
- Nilainya ada di simpul root - kembalikan true.
Perlu dicatat bahwa pohon pencarian biner dengan skema yang dikembangkan selalu mulai mencari sepanjang jalur dari akar ke daun. Dalam kasus terburuk, ia pergi ke daun. Oleh karena itu, waktu terburuk sebanding dengan panjang jalur terpanjang dari akar ke daun, yaitu tinggi pohon. Secara umum, ini adalah saat Anda perlu mengetahui berapa lama waktu yang dibutuhkan untuk mencari sebagai fungsi dari jumlah nilai yang disimpan di pohon.
Dengan kata lain, ada hubungan antara jumlah node dalam BST dan tinggi pohon, tergantung pada "bentuknya". Dalam kasus terburuk, node hanya memiliki satu anak, dan pohon pencarian biner seimbang pada dasarnya adalah daftar tertaut. Misalnya:
50
/
10
15
30
/
20
Pohon ini memiliki 5 simpul dan tinggi=5. Menemukan nilai dalam rentang 16-19 dan 21-29 akan memerlukan jalur berikut dari akar ke daun (simpul yang berisi nilai 20), mis., itu akan memakan waktu sebanding dengan jumlah node. Paling-paling, mereka semua memiliki 2 anak, dan daunnya terletak di kedalaman yang sama.
Pohon pencarian biner ini memiliki 7 node dan tinggi=3. Secara umum, pohon seperti ini (pohon penuh) akan memiliki ketinggian sekitar log 2 (N), di mana N adalah jumlah node di pohon. Nilai log 2 (N) adalah berapa kali (2) N dapat dibagi sebelum nol tercapai.
Ringkasan: waktu terburuk yang dibutuhkan untuk mencari di BST adalah O (tinggi pohon). Pohon "linier" kasus terburuk adalah O(N), di mana N adalah jumlah simpul di pohon. Paling-paling, pohon "lengkap" adalah O(log N).
sisipan biner BST
Bertanya-tanya di mana seharusnyanode baru terletak di BST, Anda perlu memahami logikanya, itu harus ditempatkan di tempat pengguna menemukannya. Selain itu, Anda perlu mengingat aturan:
- Duplikat tidak diperbolehkan, mencoba memasukkan nilai duplikat akan menimbulkan pengecualian.
- Metode penyisipan publik menggunakan metode "pembantu" rekursif helper untuk benar-benar menyisipkan.
- Node yang berisi nilai baru selalu disisipkan sebagai daun di BST.
- Metode penyisipan publik mengembalikan batal, tetapi metode pembantu mengembalikan BSTnode. Ia melakukan ini untuk menangani kasus di mana simpul yang diteruskan ke sana adalah nol.
Secara umum, metode helper menunjukkan bahwa jika pohon pencarian biner asli kosong, hasilnya adalah pohon dengan satu simpul. Jika tidak, hasilnya akan berupa penunjuk ke simpul yang sama yang diteruskan sebagai argumen.
Penghapusan dalam algoritma biner
Seperti yang Anda harapkan, menghapus elemen melibatkan pencarian simpul yang berisi nilai yang akan dihapus. Ada beberapa hal dalam kode ini:
- BST menggunakan pembantu, metode penghapusan kelebihan beban. Jika elemen yang Anda cari tidak ada di pohon, maka metode pembantu akhirnya akan dipanggil dengan n==null. Ini tidak dianggap sebagai kesalahan, pohon tidak berubah dalam kasus ini. Metode pembantu hapus mengembalikan nilai - penunjuk ke pohon yang diperbarui.
- Ketika sebuah daun dihapus, penghapusan dari pohon pencarian biner menyetel penunjuk anak yang sesuai dari induknya ke nol, atau akar ke nol jika yang dihapus adalahnode adalah root dan tidak memiliki anak.
- Perhatikan bahwa panggilan hapus harus salah satu dari yang berikut: root=delete (root, key), n.setLeft (delete (n.getLeft (), key)), n.setRight (delete(n. getRight(), kunci)). Jadi, dalam ketiga kasus tersebut benar bahwa metode delete hanya mengembalikan null.
- Ketika pencarian node yang berisi nilai yang akan dihapus berhasil, ada tiga opsi: node yang akan dihapus adalah daun (tidak memiliki anak), node yang akan dihapus memiliki satu anak, memiliki dua anak-anak.
- Ketika node yang dihapus memiliki satu anak, Anda cukup menggantinya dengan anak, mengembalikan pointer ke anak.
- Jika node yang akan dihapus memiliki nol atau 1 anak, maka metode delete akan "mengikuti jalur" dari root ke node tersebut. Jadi waktu terburuk sebanding dengan tinggi pohon, baik untuk pencarian maupun penyisipan.
Jika node yang akan dihapus memiliki dua anak, langkah-langkah berikut diambil:
- Temukan node yang akan dihapus, ikuti jalur dari root ke sana.
- Temukan nilai v terkecil di subpohon kanan, lanjutkan sepanjang jalur ke daun.
- Hapus nilai v secara rekursif, ikuti jalur yang sama seperti pada langkah 2.
- Jadi, dalam kasus terburuk, jalur dari akar ke daun dilakukan dua kali.
Urutan lintasan
Traversal adalah proses yang mengunjungi semua node dalam sebuah pohon. Karena pohon pencarian biner C adalah struktur data non-linier, tidak ada traversal yang unik. Misalnya, terkadang beberapa algoritma traversaldikelompokkan menjadi dua jenis berikut:
- kedalaman penyeberangan;
- pass pertama.
Hanya ada satu jenis persilangan lebar - melewati level. Lintasan ini mengunjungi node level bawah dan kiri, atas dan kanan.
Ada tiga jenis penyeberangan kedalaman yang berbeda:
- Passing PreOrder - pertama mengunjungi orang tua dan kemudian anak kiri dan kanan.
- Passing InOrder - mengunjungi anak kiri, lalu orang tua dan anak kanan.
- Melewati PostOrder - mengunjungi anak kiri, lalu anak kanan, lalu orang tua.
Contoh untuk empat traversal dari pohon pencarian biner:
- PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
- Pesanan - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
- PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
- Pesanan Tingkat - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.
Gambar menunjukkan urutan node yang dikunjungi. Angka 1 adalah node pertama dalam traversal tertentu, dan 7 adalah node terakhir.
Traversal umum ini dapat direpresentasikan sebagai algoritma tunggal, dengan asumsi bahwa setiap node dikunjungi tiga kali. Tur Euler adalah perjalanan mengelilingi pohon biner di mana setiap tepi diperlakukan sebagai dinding yang tidak dapat dilintasi pengguna. Dalam perjalanan ini, setiap simpul akan dikunjungi baik di kiri, atau di bawah, atau di kanan. Tur Euler, yang mengunjungi node di sebelah kiri, menyebabkan preposisi dilewati. Ketika node di bawah dikunjungi, mereka dilalui secara berurutan. Dan ketika node di sebelah kanan dikunjungi - dapatkanbypass langkah demi langkah.
Navigasi dan Debugging
Untuk memudahkan navigasi pohon, buat fungsi yang terlebih dahulu memeriksa apakah itu anak kiri atau kanan. Untuk mengubah posisi sebuah node, harus ada akses yang mudah ke pointer pada node induk. Menerapkan pohon dengan benar sangat sulit, jadi Anda perlu mengetahui dan menerapkan proses debugging. Pohon pencarian biner dengan implementasi sering kali memiliki pointer yang sebenarnya tidak menunjukkan arah perjalanan.
Untuk mengetahui semua ini, sebuah fungsi digunakan yang memeriksa apakah pohon itu benar, dan membantu menemukan banyak kesalahan. Misalnya, ia memeriksa apakah simpul induk adalah simpul anak. Dengan assert(is_wellformed(root)) banyak kesalahan dapat ditangkap sebelum waktunya. Menggunakan beberapa titik henti sementara yang diberikan dalam fungsi ini, Anda juga dapat menentukan dengan tepat penunjuk mana yang salah.
Fungsi Konsolenausgabe
Fungsi ini mem-flush seluruh pohon ke konsol dan karena itu sangat berguna. Urutan di mana tujuan keluaran pohon dieksekusi adalah:
- Untuk melakukan ini, Anda harus terlebih dahulu menentukan informasi apa yang akan dikeluarkan melalui node.
- Dan Anda juga perlu mengetahui seberapa lebar dan tinggi pohon untuk memperhitungkan berapa banyak ruang yang harus ditinggalkan.
- Fungsi berikut menghitung informasi ini untuk pohon dan setiap subpohon. Karena Anda hanya dapat menulis ke konsol baris demi baris, Anda juga perlu mencetak pohon baris demi baris.
- Sekarang kita perlu cara lain untuk menarikseluruh pohon, bukan hanya baris demi baris.
- Dengan bantuan fungsi dump, Anda dapat membaca pohon dan secara signifikan meningkatkan algoritme keluaran, sejauh menyangkut kecepatan.
Namun, fungsi ini akan sulit digunakan pada pohon besar.
Salin konstruktor dan destruktor
Karena pohon bukanlah struktur data yang sepele, lebih baik untuk mengimplementasikan salinan konstruktor, destruktor, dan operator penugasan. Destructor mudah diimplementasikan secara rekursif. Untuk pohon yang sangat besar, ini dapat menangani "heap overflow". Dalam hal ini, dirumuskan secara iteratif. Idenya adalah untuk menghilangkan daun yang mewakili nilai terkecil dari semua daun, sehingga berada di sisi kiri pohon. Memotong daun pertama akan membuat daun baru, dan pohon itu menyusut sampai akhirnya tidak ada lagi.
Konstruktor salinan juga dapat diimplementasikan secara rekursif, tetapi berhati-hatilah jika ada pengecualian. Jika tidak, pohon dengan cepat menjadi membingungkan dan rawan kesalahan. Itu sebabnya versi iteratif lebih disukai. Idenya adalah menelusuri pohon lama dan pohon baru, seperti yang Anda lakukan di destruktor, mengkloning semua simpul yang ada di pohon lama tapi bukan yang baru.
Dengan metode ini, implementasi pohon pencarian biner selalu dalam keadaan sehat dan dapat dihapus oleh destruktor bahkan dalam keadaan tidak lengkap. Jika pengecualian terjadi, yang perlu Anda lakukan adalah menginstruksikan destruktor untuk menghapus pohon setengah jadi. operator penugasandapat dengan mudah diimplementasikan menggunakan Copy & Swap.
Membuat pohon pencarian biner
Pohon pencarian biner yang optimal sangat efisien jika dikelola dengan benar. Beberapa aturan untuk pohon pencarian biner:
- Sebuah simpul induk memiliki paling banyak 2 simpul anak.
- Simpul anak kiri selalu lebih kecil dari simpul induk.
- Sebuah simpul anak yang valid selalu lebih besar dari atau sama dengan simpul induk.
Array yang akan digunakan untuk membangun pohon pencarian biner:
- Array bilangan bulat dasar dari tujuh nilai dalam urutan yang tidak diurutkan.
- Nilai pertama dalam array adalah 10, jadi langkah pertama dalam membangun pohon adalah membuat simpul akar 10, seperti yang ditunjukkan di sini.
- Dengan satu set simpul akar, semua nilai lain akan menjadi anak dari simpul ini. Mengacu pada aturan, langkah pertama yang harus dilakukan untuk menambahkan 7 ke pohon adalah membandingkannya dengan simpul akar.
- Jika nilai 7 kurang dari 10, itu akan menjadi simpul anak kiri.
- Jika nilai 7 lebih besar atau sama dengan 10, maka akan bergerak ke kanan. Karena 7 diketahui kurang dari 10, maka ditetapkan sebagai simpul anak kiri.
- Lakukan perbandingan secara rekursif untuk setiap elemen.
- Mengikuti pola yang sama, lakukan perbandingan yang sama terhadap nilai ke-14 dalam larik.
- Membandingkan nilai 14 dengan simpul akar 10, mengetahui bahwa 14 adalah anak yang benar.
- Berjalan melalui array,datang ke 20.
- Mulailah dengan membandingkan larik dengan 10, mana yang lebih besar. Jadi pindah ke kanan dan bandingkan dengan 14, dia lebih dari 14 dan tidak memiliki anak di sebelah kanan.
- Sekarang ada nilai 1. Mengikuti pola yang sama dengan nilai lainnya, bandingkan 1 hingga 10, pindah ke kiri dan bandingkan dengan 7 dan akhirnya ke 1 anak kiri dari simpul ke-7.
- Jika nilainya 5, bandingkan dengan 10. Karena 5 kurang dari 10, geser ke kiri dan bandingkan dengan 7.
- Mengetahui bahwa 5 kurang dari 7, lanjutkan ke bawah pohon dan bandingkan 5 dengan 1 nilai.
- Jika 1 tidak memiliki anak dan 5 lebih besar dari 1, maka 5 adalah anak yang valid dari 1 simpul.
- Akhirnya masukkan nilai 8 ke dalam pohon.
- Ketika 8 kurang dari 10, pindahkan ke kiri dan bandingkan dengan 7, 8 lebih besar dari 7, jadi pindahkan ke kanan dan lengkapi pohonnya, jadikan 8 turunan dari 7.
Mendapatkan dan mengevaluasi keanggunan sederhana dari pohon pencarian biner yang optimal. Seperti banyak topik dalam pemrograman, kekuatan pohon pencarian biner berasal dari kemampuannya untuk menyelesaikan data menjadi komponen kecil yang terkait. Mulai sekarang, Anda dapat bekerja dengan kumpulan data lengkap secara terorganisir.
Masalah Pencarian Biner Potensial
Pohon pencarian biner sangat bagus, tetapi ada beberapa peringatan yang perlu diingat. Mereka biasanya hanya efektif jika seimbang. Pohon yang seimbang adalah pohon di manaperbedaan antara ketinggian subpohon dari setiap simpul di pohon paling banyak satu. Mari kita lihat contoh yang mungkin membantu memperjelas aturan. Mari kita bayangkan bahwa array dimulai dengan sortable.
Jika Anda mencoba menjalankan algoritme pohon pencarian biner pada pohon ini, ia akan bekerja persis seperti jika hanya mengulangi array sampai nilai yang diinginkan ditemukan. Kekuatan pencarian biner terletak pada kemampuan untuk menyaring nilai yang tidak diinginkan dengan cepat. Ketika sebuah pohon tidak seimbang, tidak akan memberikan manfaat yang sama dengan pohon yang seimbang.
Sangat penting untuk memeriksa data yang digunakan pengguna saat membuat pohon pencarian biner. Anda dapat mengintegrasikan rutinitas seperti pengacakan array sebelum menerapkan pohon pencarian biner untuk bilangan bulat untuk menyeimbangkannya.
Contoh perhitungan pencarian biner
Kita perlu menentukan jenis pohon apa yang akan dihasilkan jika 25 dimasukkan ke dalam pohon pencarian biner berikut:
10
/
/
5 15
/ / \
/ / \
2 12 20
Saat menyisipkan x ke pohon T yang belum mengandung x, kunci x selalu ditempatkan di daun baru. Sehubungan dengan ini, pohon baru akan terlihat seperti:
10
/
/
5 15
/ / \
/ / \
2 12 20
25
Pohon apa yang akan Anda dapatkan jika Anda memasukkan 7 ke dalam pohon pencarian biner berikut?
10
/
/
5 15
/ / \
/ / \
2 12 20
Jawaban:
10
/
/
/
5 15
/ / /
/ / /
2 7 12 20
Sebuah pohon pencarian biner dapat digunakan untuk menyimpan objek apapun. Keuntungan menggunakan pohon pencarian biner daripada daftar tertaut adalah jika pohon cukup seimbang dan lebih seperti pohon "penuh" daripada pohon "linier", penyisipan, pencarian, dan semua operasi penghapusan dapat diimplementasikan untuk dijalankan di O(log N) waktu.
