Struktur data non-linear terdiri dari kumpulan elemen-elemen yang didistribusikan pada bidang yang berarti tidak ada urutan antara elemen-elemen seperti yang ada dalam struktur data linier.
Grafik perbandingan
| Dasar untuk perbandingan | Pohon | Grafik |
|---|---|---|
| Path | Hanya satu di antara dua simpul. | Lebih dari satu jalur diizinkan. |
| Simpul akar | Ia memiliki tepat satu simpul akar. | Grafik tidak memiliki simpul root. |
| Loop | Tidak ada loop yang diizinkan. | Grafik dapat memiliki loop. |
| Kompleksitas | Tidak terlalu rumit | Lebih kompleks secara komparatif |
| Teknik traversal | Pre-order, In-order, dan Post-order. | Pencarian luas pertama dan pencarian mendalam pertama. |
| Jumlah tepi | n-1 (di mana n adalah jumlah node) | Tidak terdefinisikan |
| Tipe model | Hierarkis | Jaringan |
Definisi Pohon
Pohon adalah kumpulan terbatas dari item data yang biasanya disebut sebagai node. Seperti disebutkan di atas bahwa pohon adalah struktur data non-linear yang mengatur item data dalam urutan diurutkan. Ini digunakan untuk menunjukkan struktur hierarki antara berbagai elemen data dan mengatur data menjadi cabang-cabang yang berhubungan dengan informasi. Penambahan tepi baru dalam hasil pohon dalam pembentukan loop atau sirkuit.
Ada beberapa jenis pohon seperti pohon biner, pohon pencarian biner, pohon AVL, pohon biner berulir, B-tree, dll. Kompresi data, penyimpanan file, manipulasi ekspresi aritmatika dan pohon permainan adalah beberapa aplikasi pohon struktur data.
Properti pohon:
- Ada simpul yang ditunjuk di bagian atas pohon yang dikenal sebagai akar pohon.
- Item data yang tersisa dibagi menjadi himpunan bagian yang terpisah yang disebut sebagai subtree.
- Tinggi pohon melebar ke arah bawah.
- Sebuah pohon harus terhubung yang berarti harus ada jalur dari satu root ke semua node lainnya.
- Itu tidak mengandung loop.
- Sebuah pohon memiliki tepi n-1.
Ada berbagai istilah yang terkait dengan pohon seperti simpul terminal, tepi, level, derajat, kedalaman, hutan, dll. Di antara istilah-istilah itu, beberapa di antaranya dijelaskan di bawah ini.
- Edge - Garis yang menghubungkan dua node.
- Level - Sebuah pohon dipartisi menjadi level sedemikian rupa sehingga simpul akar berada di level 0. Kemudian, anak-anak terdekatnya berada di level 1, dan anak-anak terdekatnya berada di level 2 dan seterusnya hingga terminal atau simpul daun.
- Derajat - Ini adalah jumlah subpohon dari sebuah simpul dalam pohon yang diberikan.
- Kedalaman - Ini adalah tingkat maksimum dari setiap simpul dalam pohon tertentu dan juga dikenal sebagai tinggi .
- Terminal node - Node level tertinggi adalah terminal node sementara node lain kecuali terminal dan root node dikenal sebagai node non-terminal.
Definisi Grafik
Grafik juga merupakan struktur data matematika non-linear yang dapat mewakili berbagai jenis struktur fisik. Terdiri dari sekelompok simpul (atau simpul) dan kumpulan tepi yang menghubungkan kedua simpul. Vertikal pada grafik direpresentasikan sebagai titik atau lingkaran dan tepi ditampilkan sebagai busur atau segmen garis. Tepi diwakili oleh E (v, w) di mana v dan w adalah pasangan dari simpul. Penghapusan tepi dari sirkuit atau grafik yang terhubung menciptakan subgraph yang merupakan pohon.
Grafik diklasifikasikan ke dalam berbagai kategori seperti diarahkan, tidak diarahkan, terhubung, tidak terhubung, sederhana dan multi-grafik. Jaringan komputer, sistem transportasi, grafik jaringan sosial, sirkuit listrik dan perencanaan proyek adalah beberapa aplikasi struktur data grafik. Ini juga digunakan dalam teknik manajemen yang disebut sebagai PERT (evaluasi program dan teknik ulasan) dan CPM (metode jalur kritis) di mana struktur grafik dianalisis.
Properti grafik:
- Sebuah simpul dalam grafik dapat dihubungkan ke sejumlah simpul lain menggunakan tepi.
- Edge dapat bidirected atau diarahkan.
- Tepian bisa ditimbang.
Dalam grafik juga kami menggunakan berbagai istilah seperti simpul yang berdekatan, jalur, siklus, derajat, grafik terhubung, grafik lengkap, grafik tertimbang, dll. Mari kita memahami beberapa istilah ini.
- Verteks yang berdekatan - Sebuah simpul a berbatasan dengan simpul b jika ada tepi (a, b) atau (b, a).
- Jalur - Jalur dari simpul acak w adalah urutan simpul yang berdekatan.
- Siklus - Ini adalah jalur di mana simpul pertama dan terakhir adalah sama.
- Derajat - Ini adalah sejumlah insiden tepi pada suatu titik.
- Grafik terhubung - Jika ada jalur dari titik acak ke titik lainnya, maka grafik tersebut dikenal sebagai grafik terhubung.
Perbedaan Kunci Antara Pohon dan Grafik
- Dalam pohon hanya ada satu jalur antara dua simpul sedangkan grafik dapat memiliki jalur searah dan dua arah antara node.
- Di pohon, tepat ada satu simpul root, dan setiap anak hanya dapat memiliki satu orangtua. Sebagai lawan, dalam grafik, tidak ada konsep simpul akar.
- Sebuah pohon tidak dapat memiliki loop dan loop-sendiri sementara grafik dapat memiliki loop dan loop-diri.
- Grafik lebih rumit karena dapat memiliki loop dan self-loop. Sebaliknya, pohon lebih sederhana dibandingkan dengan grafik.
- Pohon dilintasi menggunakan teknik pre-order, in-order, dan post-order. Di sisi lain, untuk traversal grafik, kami menggunakan BFS (Breadth First Search) dan DFS (Depth First Search).
- Sebuah pohon dapat memiliki n-1 tepi. Sebaliknya, dalam grafik, tidak ada jumlah tepi yang ditentukan sebelumnya, dan itu tergantung pada grafik.
- Sebuah pohon memiliki struktur hierarkis sedangkan grafik memiliki model jaringan.
Kesimpulan
Grafik dan pohon adalah struktur data non-linear yang digunakan untuk menyelesaikan berbagai masalah kompleks. Grafik adalah sekelompok simpul dan tepi di mana tepi menghubungkan sepasang simpul sedangkan pohon dianggap sebagai grafik yang terhubung minimal yang harus dihubungkan dan bebas dari loop.
