Perbedaan antara pohon biner dan pohon pencarian biner

Apa itu pohon biner?

Pohon biner adalah struktur data hierarkis di mana setiap node memiliki nol, satu, atau paling banyak, dua anak. Setiap node berisi penunjuk "kiri", penunjuk "kanan", dan elemen data. Pointer "root" mewakili simpul paling atas di pohon. Setiap node dalam struktur data terhubung langsung ke jumlah node yang sewenang -wenang di kedua sisi, disebut sebagai anak -anak. Pointer nol mewakili pohon biner. Tidak ada urutan khusus tentang bagaimana node harus diatur di pohon biner. Node tanpa node anak -anak disebut node daun, atau node eksternal.

Secara sederhana, ini mendefinisikan fungsi pelabelan terorganisir pada node, yang pada gilirannya menetapkan beberapa nilai acak untuk setiap node. Apa pun yang memiliki dua anak dan satu simpul orang tua adalah pohon biner. Pohon biner digunakan untuk menyimpan informasi yang membentuk hierarki seperti sistem file di komputer pribadi Anda. Tidak seperti array, pohon tidak memiliki batas atas pada jumlah node karena mereka terhubung menggunakan pointer, seperti daftar tertaut. Fungsi utama pohon biner termasuk mewakili data hierarkis, menyortir daftar data, menyediakan operasi insert/hapus yang efisien, dll. Node pohon direpresentasikan menggunakan struktur di c.

Apa itu pohon pencarian biner?

Pohon pencarian biner adalah jenis struktur data pohon biner di mana node diatur secara berurutan, karenanya juga disebut sebagai "pohon biner yang dipesan". Ini adalah struktur data berbasis node yang menyediakan cara pencarian, pengambilan, pencarian data yang efisien dan cepat. Untuk setiap node, elemen di subtree kiri harus kurang dari atau sama dengan kunci dalam simpul induknya (LP). Seharusnya tidak ada kunci duplikat. Secara sederhana, ini adalah jenis khusus struktur data pohon biner yang secara efisien menyimpan dan mengelola item dalam memori.

Ini memungkinkan untuk akses cepat informasi, penyisipan dan penghapusan data, ditambah dapat digunakan untuk mengimplementasikan tabel pencarian yang memungkinkan untuk mencari item dengan kunci unik mereka, seperti mencari nomor telepon seseorang berdasarkan nama. Kunci unik diurutkan dengan cara yang terorganisir, sehingga pencarian dan operasi dinamis lainnya dapat dilakukan dengan menggunakan pencarian biner. Ini mendukung tiga operasi utama: pencarian elemen, penyisipan elemen, dan penghapusan elemen. Pohon pencarian biner memungkinkan pengambilan unsur -unsur cepat yang disimpan di pohon karena setiap kunci simpul dibandingkan dengan simpul akar, yang membuang setengah dari pohon.

Perbedaan antara pohon biner dan pohon pencarian biner

1. Definisi pohon biner dan pohon pencarian biner - Pohon biner adalah struktur data hierarkis di mana seorang anak dapat memiliki nol, satu, atau maksimum dua node anak; Setiap node berisi pointer kiri, penunjuk kanan dan elemen data. Tidak ada urutan khusus tentang bagaimana node harus diatur di pohon. Pohon pencarian biner, di sisi lain, adalah pohon biner yang dipesan di mana ada urutan relatif bagaimana node harus diatur.
2. Struktur dari Pohon biner dan pohon pencarian biner- Node paling atas di pohon mewakili penunjuk akar di pohon biner, dan pointer kiri dan kanan mewakili pohon yang lebih kecil di kedua sisi. Ini adalah bentuk khusus dari pohon yang mewakili data dalam struktur pohon. Pohon pencarian biner, di sisi lain, adalah jenis pohon biner di mana semua node di subtree kiri kurang dari atau sama dengan nilai simpul akar dan subtree kanan lebih besar dari atau sama dengan nilai dari simpul root.
3. Operasi dari Pohon biner dan pohon pencarian biner- Pohon biner dapat menjadi apa saja yang memiliki dua anak dan satu orang tua. Operasi umum yang dapat dilakukan pada pohon biner adalah penyisipan, penghapusan, dan traversal. Pohon pencarian biner lebih dari pohon biner yang diurutkan yang memungkinkan pencarian, penyisipan, dan penghapusan yang cepat dan efisien. Tidak seperti pohon biner, pohon pencarian biner menjaga kunci mereka diurutkan, jadi pencarian biasanya mengimplementasikan pencarian biner untuk operasi.
4. Tipe dari Pohon biner dan pohon pencarian biner- Ada berbagai jenis pohon biner, yang umum adalah "pohon biner penuh", "pohon biner lengkap", "pohon biner yang sempurna", dan "pohon biner yang diperluas". Beberapa jenis umum pohon pencari biner termasuk pohon T, pohon AVL, pohon splay, pohon tango, pohon merah-hitam dll.

Pohon biner vs. Pohon Pencarian Biner: Bagan Perbandingan

Ringkasan pohon biner dan pohon pencarian biner

Sementara keduanya mensimulasikan struktur pohon hierarkis yang mewakili kumpulan node dengan setiap node yang mewakili nilai, mereka sangat berbeda satu sama lain dalam hal bagaimana mereka dapat diimplementasikan dan digunakan. Pohon biner mengikuti satu aturan sederhana bahwa setiap node induk memiliki tidak lebih dari dua node anak, sedangkan pohon pencarian biner hanyalah varian dari pohon biner yang mengikuti urutan relatif bagaimana node harus diatur dalam pohon.