Struktur Data | tree
TREE
Tree bisa didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon inipun juga mempunyai akar dan sub-subpohonnya masing-masing.
Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root. Untuk lebih jelasnya lihat gambar, merupakan contoh dari sebuah tree.
Pembagian Tree :
1. Tree Statik : isi node-nodenya tetap karena bentuk pohonnya sudah ditentukan.
2. Tree Dinamik : isi nodenya berubah-ubah karena proses penambahan (insert) dan penghapusan (delete
Terminologi Tree
Akar (Root nodes)
Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas). Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.
Daun (Leaf nodes)
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.
Representasi Tree menggunakan linked list
Tree dapat dibuat dengan menggunakan linked list secara rekursif.Linked list yang digunakan adalah double linked list non circular.Data yang pertama kali masuk akan menjadi node root.Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.
Operasi-operasi pada Tree:
— Insert: menambah node ke dalam Tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.
— Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya adalah tree tidak boleh kosong.
— Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
— Count: menghitung jumlah node dalam Tree
— Height : mengetahui kedalaman sebuah Tree
— Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
— Child : mengetahui anak dari sebuah node (jika punya)
Jenis-Jenis penelurusan data :
Sebuah pohon biner memiliki operasi traversal yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersimpan di dalam pohon biner.
Terdapat tiga jenis kunjungan pada pohon biner, yaitu :
1. PREORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Cetak isi simpul yang dikunjungi.
- Kunjungi cabang kiri.
- Kunjungi cabang kanan.
Procedure PREORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
PREORDER(Temp^.Kiri); {Kunjungi cabang kiri}
PREORDER(Temp^.Kanan); {Kunjungi cabang kanan}
End;
End;
2. INORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Kunjungi cabang kiri.
- Cetak isi simpul yang dikunjungi.
- Kunjungi cabang kanan.
Prosedur untuk melakukan traversal secara INORDER adalah sebagai
berikut:
Procedure INORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
INORDER(Temp^.Kiri); {Kunjungi cabang kiri}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
INORDER(Temp^.Kanan); {Kunjungi cabang kanan}
End;
End;
3. POSTORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Kunjungi cabang kiri.
- Kunjungi cabang kanan.
- Cetak isi simpul yang dikunjungi.
Procedure POSTORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
POSTORDER(Temp^.Kiri); {Kunjungi cabang kiri}
POSTORDER(Temp^.Kanan); {Kunjungi cabang kanan}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
End;
End;
Dalam pengembangan nantinya, tiga jenis kunjungan ini dapat digunakan sebagai pencarian notasi infix, postfix dan prefix. Kunjungan Preorder untuk mencari prefix, kunjungan Inorder untuk mencari postfix dan kunjungan Postorder untuk mencari infiks.
Cara pertama adalah penyimpanan node secara linked, dalam arti menggunakan tipe data pointer. Pada cara ini, struktur node akan disajikan sebagai berikut:
LPtr Info RPtr
Jika struktur node tersebut diimplementasikan ke dalam Pascal, maka deklarasi node yang sesuai adalah:
1: TYPE
2: BinTreeType = ^BinNodeType;
3: BinNodeType = RECORD
4: LPtr : BinTreeType;
5: Info : BinInfoType;
6: RPtr : BinTreeType;
7: END;
Gambar dibawah adalah binary tree dan representasinya dalam penyimpanan secara linked. Pointer T menunjukkan alamat dari node root, sedang subtree yang kosong diwakili dengan pointer yang bernilai NIL.
TREE
Tree bisa didefinisikan sebagai suatu kumpulan elemen salah satu elemennya disebut dengan akar (root), dan sisa elemen lainnya (yang disebut simpul) terpecah menjadi sejumlah himpunan yang paling tidak berhubungan satu sama lain, yang disebut dengan subpohon (subtree), atau disebut juga cabang. Jika kita melihat pada subpohon, maka subpohon inipun juga mempunyai akar dan sub-subpohonnya masing-masing.
Dalam kehidupan sehari-hari, tree dapat dilihat dari pohon silsilah keluarga. Tingkat yang tertinggi disebut juga sebagai root. Untuk lebih jelasnya lihat gambar, merupakan contoh dari sebuah tree.
Pembagian Tree :
1. Tree Statik : isi node-nodenya tetap karena bentuk pohonnya sudah ditentukan.
2. Tree Dinamik : isi nodenya berubah-ubah karena proses penambahan (insert) dan penghapusan (delete
Terminologi Tree
Akar (Root nodes)
Simpul yang paling atas dalam pohon adalah akar (root node). Menjadi simpul teratas, simpul akar tidak akan memiliki orang tua. Ini merupakan simpul di mana biasanya merupakan tempat untuk memulai operasi dalam pohon (walaupun beberapa algoritma dimulai dengan daun dan berakhir pada akar). Semua simpul yang lain dapat dicapai dari akar dengan menelusuri pinggiran atau pranala. (Dalam definisi resmi, setiap jalan adalah khas). Dalam diagram, ini secara khusus di gambar paling atas. Di beberapa pohon, seperti heap, akar memiliki sifat khusus. Setiap simpul dalam sebuah pohon dapat dilihat sebagai akar dari sub pohon yang berakar pada simpul tersebut.
Daun (Leaf nodes)
Semua simpul yang berada pada tingkat terendah dari pohon dinamakan daun (leaf node). Sejak mereka terletak pada tingkat paling bawah, mereka tidak memiliki anak satupun. Seringkali, daun merupakan simpul terjauh dari akar. Dalam teori grafik, sebuah daun adalah sebuah sudut dengan tingkat 1 selain akar (kecuali jika pohonnya hanya memiliki satu sudut; maka akarnya adalah daunnya juga). Setiap pohon memiliki setidaknya satu daun.
Dalam pohon berdasarkan genetic programming sebuah daun (juga dibilang terminal) adalah bagian terluar dari sebuah program pohon. Jika dibandingkan dengan fungsinya atau simpul dalam, daun tidak memiliki argumen. Di banyak kasus dalam daun-GP input ke programnya.
Representasi Tree menggunakan linked list
Tree dapat dibuat dengan menggunakan linked list secara rekursif.Linked list yang digunakan adalah double linked list non circular.Data yang pertama kali masuk akan menjadi node root.Data yang lebih kecil dari data node root akan masuk dan menempati node kiri dari node root, sedangkan jika lebih besar dari data node root, akan masuk dan menempati node di sebelah kanan node root.
Operasi-operasi pada Tree:
— Insert: menambah node ke dalam Tree secara rekursif. Jika data yang akan dimasukkan lebih besar daripada elemen root, maka akan diletakkan di node sebelah kanan, sebaliknya jika lebih kecil maka akan diletakkan di node sebelah kiri. Untuk data pertama akan menjadi elemen root.
— Find: mencari node di dalam Tree secara rekursif sampai node tersebut ditemukan dengan menggunakan variable bantuan ketemu. Syaratnya adalah tree tidak boleh kosong.
— Traverse: yaitu operasi kunjungan terhadap node-node dalam pohon dimana masing-masing node akan dikunjungi sekali.
— Count: menghitung jumlah node dalam Tree
— Height : mengetahui kedalaman sebuah Tree
— Find Min dan Find Max : mencari nilai terkecil dan terbesar pada Tree
— Child : mengetahui anak dari sebuah node (jika punya)
Jenis-Jenis penelurusan data :
Sebuah pohon biner memiliki operasi traversal yaitu suatu kunjungan pada suatu simpul tepat satu kali. Dengan melakukan kunjungan lengkap kita akan memperoleh urutan informasi secara linier yang tersimpan di dalam pohon biner.
Terdapat tiga jenis kunjungan pada pohon biner, yaitu :
1. PREORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Cetak isi simpul yang dikunjungi.
- Kunjungi cabang kiri.
- Kunjungi cabang kanan.
Procedure PREORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
PREORDER(Temp^.Kiri); {Kunjungi cabang kiri}
PREORDER(Temp^.Kanan); {Kunjungi cabang kanan}
End;
End;
2. INORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Kunjungi cabang kiri.
- Cetak isi simpul yang dikunjungi.
- Kunjungi cabang kanan.
Prosedur untuk melakukan traversal secara INORDER adalah sebagai
berikut:
Procedure INORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
INORDER(Temp^.Kiri); {Kunjungi cabang kiri}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
INORDER(Temp^.Kanan); {Kunjungi cabang kanan}
End;
End;
3. POSTORDER
Kunjungan jenis ini mempunyai urutan kunjungan sebagai berikut :
- Kunjungi cabang kiri.
- Kunjungi cabang kanan.
- Cetak isi simpul yang dikunjungi.
Procedure POSTORDER(Temp : Tree);
Begin
If Temp <> NIL Then
Begin
POSTORDER(Temp^.Kiri); {Kunjungi cabang kiri}
POSTORDER(Temp^.Kanan); {Kunjungi cabang kanan}
Write(Temp^.Info,’ ‘); {Cetak isi simpul}
End;
End;
Dalam pengembangan nantinya, tiga jenis kunjungan ini dapat digunakan sebagai pencarian notasi infix, postfix dan prefix. Kunjungan Preorder untuk mencari prefix, kunjungan Inorder untuk mencari postfix dan kunjungan Postorder untuk mencari infiks.
Cara pertama adalah penyimpanan node secara linked, dalam arti menggunakan tipe data pointer. Pada cara ini, struktur node akan disajikan sebagai berikut:
LPtr Info RPtr
Jika struktur node tersebut diimplementasikan ke dalam Pascal, maka deklarasi node yang sesuai adalah:
1: TYPE
2: BinTreeType = ^BinNodeType;
3: BinNodeType = RECORD
4: LPtr : BinTreeType;
5: Info : BinInfoType;
6: RPtr : BinTreeType;
7: END;
Gambar dibawah adalah binary tree dan representasinya dalam penyimpanan secara linked. Pointer T menunjukkan alamat dari node root, sedang subtree yang kosong diwakili dengan pointer yang bernilai NIL.
