Tree

Struktur data tree adalah sebuah struktur data yang secara bentuk menyerupai sebuah pohon, yang terdiri dari serangkaian node (simpul) yang saling berhubungan, Dalam literature lain dikatakan bahwa Struktur data pohon adalah suatu struktur data yang digunakan secara luas yang menyerupai struktur pohon dengan sejumlah simpul yang terhubung. Dengan kata lain dapat diambil sebuah definisi bahwa struktur data tree adalah sebuah struktur data bukan linear yang menggambarkan hierarki antar elemen-elemennya dan terbentuk dari sejumlah simpul-simpul yang saling terhubung. Dalam struktur data Tree ini dikenal adanya istilah-istilah, seperti root, node, child, parent, daun, derajad  dan sebagainya atau dengan kata lain terminology dari tree sebagai berikut :

 

-          Root  adalah node teratas dari sebuah tree. Node ini merupakan parent yang berada di level0 atau level teratas.

Root ini merupakan node yang memiliki hierarki tertinggi dan dapat juga memiliki anak. Node Root ini akan di ciptakan pertama,artinya jika tree kosong dan dimasukan suatu data untuk yang pertama kali maka data tersebut dijadikan sebagai root.  Node di bawah root yang saliang berhubungan akan membentuk subtree.

-          Node adalah elemen dalam sebuah tree yang berisi informasi.

-          Parent adalah Node yang berada diatas node lain secara langsung. Parent teratas bernama root.

-          Child adalah cabang langsung dari sebuah node.

-          Daun adalah node terakhir yang tidak memiliki child / anak. Disebut juga external node.

-          Derajad atau level adalah tingkatan dalam hierarki tree, dimulai dari level 0 untuk root dan level 1 untuk child dibawahnya dan seterusnya.

-          Predecesor, yaitu node yang berada di atas suatu node tertentu.

-          Successor, yaitu node yang berada di bawah suatu node tertentu.

-          Ancestor, yaitu seluruh node yang terletak sebelum node tertentu dan juga pada jalur yang sama.

-          Descendant, yaitu seluruh node yang terletak setelah node tertentu dan juga pada jalur yang sama.

-          Sibling,yaitu node-node yang memiliki parent yang sama.

-          Subtree, yaitu suatu node beserta descendent-nya.

-          Size,yaitu banyaknya node dalam suatu tree

-          Height, yaitu banyaknya tingkatan dalam suatu tree.

Berdasarkan jenisnya, tree dibagi menjadi dua,yaitu jenis tree static dan tree dynamic. Tree static adalah tree yang isi dari node-nodenya tetap, karena bentuk pohonnya telah ditentukan. Sedangkan tree dynamic adalah tree yang isi nodenya dapat berubah-ubah karena proses penambahan dan penghapusan.

Dalam tree terdapat beberapa macam bentuk , tetapi yang terkenal adalah binary tree. Binary Tree adalah sebuah tree yang hanya memiliki paling banyak 2 anak dan paling sedikit 0 anak. Dalam Binary Tree terdapat sebutan Binary Tree complete, yaitu jika semua level (kecuali level terakhir) mempunyai jumlah node maksimum (2^r) dan bila semua simpul pada tingkat terakhir uncul dibagian kiri pohon^[5].

Kemudian dikenal Extanded Binary Tree / 2 –tree, yaitu jika setiap node dalam tree mempunyai 0 atau 2 buah child. Dengan catatan node dengan dua buah child dikatakan internal node, dan node dengan nol child dikatakan external node. Aplikasi penting dari 2 tree ini adalah untuk menyajikan suatu ekspresi aritmatik yang mengandung operasi biner. External Node digunakan untuk menyajikan operand dan internal node disajikan sebagai operator yang bekerja terhadap dua subpohonnya.

Selain itu terdapat juga istilah skewed Binary Tree. Model ini adalah binary Tree yang semua nodenya keculai daun hanya memiliki satu anak. Sehingga model dari tree ini hanya terdiri dari subtree yang ke kanan atau hanya ke kiri saja. Dan pada tiap  levelnya hanya terdiri dari satu node.

Operasi dalam binary tree ada beberapa macam, yaitu insert, find, traverse, dan delete. Insert digunakan untuk memasukkan data ke dalam tree, find adalah untuk mencari data di dalam tree, delete adalah untuk menghapus data dalam tree, dan traverse (kunjungan) adalah teknik untuk mengunjungi semua node dengan kunjungan satu kali tiap node. Traverse ini terdapat tiga macam :

-          PreOrder traversal, yaitu jenis kunjungan yang akan mencetak node yang dikunjungi dulu, kemudian mencetak ke kiri dan terakhir ke kanan.

-          InOrder traversal, yaitu jenis kunjungan yang akan mencetak node bagian kiri dahulu kemudian ke node parent-nya baru ke node kanan.

-          PostOrder traversal, yaitu jenis kunjungan yang mencetak node kiri dahulu kemudian ke kanan dan terakhir baru ke parent.

Dengan adanya traversal ini maka data akan dicetak berdasarkan kunjungannya. Dapat diketahui bahwa kunjungan yang akan menghasilkan data terurut adalah kunjungan InOrder traversal.

Setelah mempelajari karakteristik dari struktur data Tree, maka akan dapat menilai apa kelebihan dan kekurangan dari struktur data Tree ini. Struktur data ini memiliki kelebihan dan kekurangan

Kelebihannya adalah ketika melakukan searching akan lebih cepat. Tetapi juga terdapat kelemahan yaitu dalam memasukan data (proses inserting) lebih lambat dari pada struktur linkedlist. Hal ini terjadi karena pada saat tree melakukan insert data maka data akan di urutkan sesuai nilainya, sehingga akan lebih memakan waktu, sedang saat mencari data (searching), karena data telah terurut maka proses akan lebih cepat daripada linkedlist.

di bawah akan diuraikan istilah-istilah umum dalam tree :

a) Prodecessor : node yang berada diatas node tertentu.

b) Successor : node yang berada di bawah node tertentu.

c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.

d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

e) Parent : predecssor satu level di atas suatu node.

f) Child : successor satu level di bawah suatu node.

g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.

h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

i) Size : banyaknya node dalam suatu tree.

j) Height : banyaknya tingkatan/level dalam suatu tree.

k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.

l) Leaf : node-node dalam tree yang tak memiliki seccessor.

m) Degree : banyaknya child yang dimiliki suatu node.

Beberapa jenis Tree yang memiliki sifat khusus :

1) Binary Tree

Binary Tree adalah tree dengan syarat tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua child.

 

Jenis-jenis Binary Tree :

a) Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

 
b) Complete Binary Tree

Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

       c) Skewed Binary Tree
yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

Implementasi Binary Tree

Binary Tree dapat diimplemntasikan dalam Pascal dengan menggunakan double Linked List. Untuk nodenya, bisa dideklarasikan sbb :

Type Tree = ^node;

Node = record

Isi : TipeData;

Left,Right : Tree;

end;

Contoh ilustrasi Tree yang disusun dengan double linked list :

 

 

Operasi-operasi pada Binary Tree :

Ø  Create : Membentuk binary tree baru yang masih kosong.

Ø  Clear : Mengosongkan binary tree yang sudah ada.

Ø  Empty : Function untuk memeriksa apakah binary tree masih kosong.

Ø  Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

Ø  Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

Ø  Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

Ø  Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

Ø  DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

Ø  Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

Ø  Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Ada tiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

v  PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

v  InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

v  PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

Untuk lebih jelasnya perhatikan contoh operasi-operasi pada Binary Tree berikut ini :

 

 

2) Binary search Tree

Adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Contoh binary search tree umum :

  

 Pada dasarnya operasi dalam binary search tree sama dengan Binary tree biasa, kecuali pada operasi insert, update, dan delete

1. Insert : Pada Binary Search Tree, insert dilakukan setelah ditemukan lokasi yang tepat. (Lokasi tidak ditentukan oleh user sendiri).

 

 

2. Update : Seperti pada Binary Tree biasa, namun disini uapte akan berpengaruh pada posisi node tersebut selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search Tree.

3. Delete : Seperti halnya update, delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree tersebut.

Pada operasi di atas, delete dilakukan terhadap Node dengan 2 child. Maka untuk menggantikannya, diambil node paling kiri dari Right SubTree yaitu 13.