Pohon
Pohon
Struktur pohon adalah struktur grafik hirarki. Struktur
ini merupakan cara yang sederhana untuk menggambarkan list hirarki pengetahuan
lainnya. Contoh struktur pohon:
Gambar 2.3 Contoh Pohon
Struktur ini terdiri dari node-node yang mencakup nama list dan ark yang menunjukkan hubungan
antar noda. Struktur atau grafik ini disebut pohon karena mempunyai
cabang-cabang. Tapi cabang dari pohon yang terbalik, berbeda dengan pohon yang
sebenarnya. Pohon sangat umum dipakai untuk menggambarkan pengetahuan yang akan
digunakan dalam AI.
Contoh aplikasi pohon
yang dapat kita lihat sehari-hari adalah pengelolaan file dalam direktori penyimpanan. Pohon merupakan struktur data
yang memiliki suatu struktur hirarki pada sekumpulan elemen, dan memiliki
hubungan satu ke banyak (one to may relationship) seperti yang kita
lihat dalam struktur organisasi sebuah perusahaan atau daftar isi sebuah buku.
Dalam struktur
organisasi, kita dapat melihat bahwa ada level atas biasanya hanya ada satu
pimpinan tertinggi. Pada level berikutnya diisi oleh beberapa orang dengan
jabatan yang berbeda tetapi dalam tingkatan yang sama. Selanjutnya dapat
dipecah lagi ke level berikutnya sampai struktur dapat memenuhi fungsi dan
tujuan organisasi. Biasanya satu atasan memiliki beberapa bawahan yang berada
dalam ruang lingkup wewenang dan tugas atasan. Begitu juga dalam daftar isi
buku, dimana satu buku terdiri dari beberapa bab dan setiap terdiri dari
beberapa sub bab, satu sub bab terdiri dari beberapa sub sub bab dan
seterusnya. Dengan demikian hirarki dapat kita anggap sebagai “terdiri dari”
atau “bawahan” atau “diawasi” dari atas ke bawah. Salah satu keuntungan pohon
dibandingkan dengan struktur data linier adalah waktu cari sebuah node maksimum
(dapat) lebih kecil dari n jika jumlah data = n.
Sebuah tree
dapat mempunyai hanya sebuah simpul tanpa sebuah sisi pun. Dengan kata
lain, jika G = (V, E) adalah tree, maka V tidak boleh
berupa himpunan kosong, namun E boleh kosong. Tree juga seringkali
didefinisikan sebagai graf tak-berarah dengan sifat bahwa hanya terdapat sebuah
lintasan unik antara setiap pasang simpul. Selain itu, di dalam tree jumlah sisinya adalah jumlah simpul
dikurangi satu.
Secara
sederhana, sebuah tree bisa
didefenisikan sebagai kumpulan dari elemen – elemen yang disebut dengan node / vertex (simpul) dimana salah satu
node disebut dengan root (akar), dan sisa node lain terpecah menjadi himpunan yang
saling tidak berhubungan satu sama lain dan disebut dengan subtree (pohon bagian). Jika dilihat pada setiap subtree maka subtree juga mempunyai root
dari subtree-nya masing – masing.
Dengan melihat istilah dasar di atas, maka sebuah tree secara rekursif dapat didefenisikan
sebagai berikut :
- Sebuah node tunggal adalah sebuah tree.
- Jika terdapat sebuah node N dan beberapa subtree N1, N2, N3, …, Nk maka dari node N dan subtree yang ada dapat dibentuk sebuah tree yang mempunyai root pada node N.
