Tree

STRUKTUR POHON (TREE) dalam struktur data

TREE (POHON)

            Tree adalah salah satu bentuk struktur data tidak linear yang mengambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen – elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan – himpunan yang saling tak berhubungan satu sama lain (disebut Subtree) atau cabang.

Cara Penggambaran Tree :

• Notasi Kurung

• Diagram Venn

• Notasi Tingkat

• Notasi Garis

Ilustrasi struktur data tree:

\Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.
Contoh : Node E memiliki in degree 1 dan out degree 2

Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0.
Contoh : Node A adalah root

Subtree / child adalah bagian salah satu node dibawah root sampai ke bawah.

Contoh : Tree C adalah right subtree dari A dan tree B merupakan left subtree dari A Node      G dan F merupakan child dari node C

node F merupakan parent dari node J dan K

Ancestor adalah Node yang berada di atas node lain.

Contoh : node B adalah ancestor dari node E

Descendant adalah node yang berada di bawah node lain.

Contoh : node E adalah descendant dari node A.

Leaf (daun) adalah semua node yang derajat masuknya 1 dan derajat keluarnya 0.

Contoh : node D, H, I, J, K, dan G adalah leaf

Sibling adalah node yang mempunyai level yang sama dan parent yang sama.
Contoh : node D adalah sibling dari node A

Height (ketinggian) adalah level tertinggi dari tree ditambah 1.

Contoh : height dari tree A adalah 3 + 1 = 4

Weight (bobot) adalah jumlah leaf(daun) pada tree.

Contoh : weight dari tree A adalah 6

Sifat sifat pohon 
 1. Jika Pohon mempunyai simpul sebanyak n, maka banyaknya ruas atau edge adalah n-1

2. Mempunyai simpul khusus yang di sebut root, jika simpul tersebut mempunyai derajat keluar >=0, dan derajat masuk = 0.
3. Mempunyai simpul yang disebut daun/leaf, jika simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
4. Setiap simpul mempunyai Tingkatan/level yang dimulai dari root yang levelnya =1, sampai dengan  level ke-n yang berada pada daun yang paling bawah.simpul yang mempunyai level sama di sebut bersaudara.
5. Pohon mempunyai ketinggian atau kedalaman atau height, yang merupakan level tertinggi.
6. Pohon mempunyai berat atau weight, yang banyaknya daun pada pohon.

 Hutan (forest) adalah Kumpulan pohon yang tidak saling berhubungan

Sebuah hutan adalah sebuah himpunan yang terdiri dari pohon terurut. Lintasan inorder, preorder, dan postorder didefinisikan secara rekursif untuk hutan.

• Inorder

1.      Lewati inorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada

2.      Kunjungi akar dari pohon pertama.

3.      Lewati inorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.

• Preorder

1.      Kunjungi akar dari pohon pertama.

2.      Lewati preorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada

3.      Lewati preorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.

• Postorder

1.      Lewati postorder hutan yang dibentuk oleh sub pohon yang pertama dalam hutan, jika ada

2.      Lewati postorder hutan yang dibentuk oleh sisa pohon dalam hutan, jika ada.

3.      Kunjungi akar dari pohon pertama.

• ·         Cara pertama 

               Merupakan cara terbanyak dan termudah untuk digunakan, caranya seperti gambar di bawah :

               

• ·         Cara kedua

    Dengan membuat diagram venn seperti gambar di bawah ini

 
  

• Cara ketiga 

Dengan cara menggunakan notasi kurung untuk gambar pada diagram venn di atas.

                        hasilnya : (P(Q(R,S)),T(U(V,W)))

• Cara Keempat

Dengan menggunakan notasi tingkat dan notasi garis

Salah satu jenis Tree yang memiliki sifat khusus adalah:

1.         POHON BINAR (BINARY TREE)

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

Dalam struktur data, Binary Tree memegang peranan yang cukup penting. Struktur ini biasanya digunakan terutama untuk menyajikan data yang mengandung hubungan hierarkykal antara elemen-elemen mereka.  

Bentuk pohon khusus yang lebih mudah dikelola dalam komputer adalah Binary Tree. Bentuk ini merupakan bentuk pohon yang umum. Sebuah pohon binar T didefinisikan terdiri dari sebuah himpunan hingga elemen yang disebut simpul.

Aplikasi pohon biner :

a. Sebagai representasi ekspressi matematika

b. Aplikasi pohon biner dalam Huffman Coding.

Jenis – jenis Binary Tree:

1.         Full Binary Tree

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

2.         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.

 3.         Skewed Binary Tree

Yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

        Dua pohon yang semua simpulnya mempunyai satu anak /turunan kecuali daun.

          

4.      Pohon biner Similer

Dua pohon yang memiliki struktur sama tapi informasinya berbeda

5.         Pohon biner Ekivalent

Dua pohon yang memiliki struktur sama dan informasi yang sama  

Karakteristik Pohon binar

1. Setiap simpul paling banyak hanya memiliki dua buah anak.
2. Derajat tertinggi dari setiap simpul adalah dua
3. Dibedakan antara cabang kiri dan cabang kanan
4. Dimungkinkan tidak memiliki simpul

Representasi :

- Ekspresi MM dengan Binary Tree

- Huffman Code

Ekspressi Matematika (EM) didefenisikan sebagai berikut:

(1). Variabel dan Bilangan adalah EM

(2). Jika E, E1 dan E2 adalah EM maka

       – E, + E dan (E) adalah EM

         E1 + E2, E1 – E2, E1 * E2, E1 / E2, E1 div E2, E1 mod E2 dan

         E1^E2 juga adalah EM

Contoh :

4 adalah EM

X adalah EM

4 + X adalah EM

2 + 4 * 3 adalah EM

(2 + 4) * 3 adalah EM

((3 + 2) * (5 – 2)) / (2 + 3) adalah EM dan seterusnya

Contoh:

Diketahui: Ekspressi Matematika ((2 + 3) * (5 – 2) + 5) * (5 + 3 * 2)

Ditanya: Gambarkan pohon ekspressi dengan cara Bootom Up

Penyelesaian:

Ekspressi tersebut terbagi dua menjadi E1 dan E2 oleh operator *; sehingga

ekspressi tersebut dapat ditulis sebagai (E1) * (E2) dimana E1 = ((2 + 3)

* (5 – 2) + 5) dan E2 = (5 + 3 * 2).

Kemudian gambarkan pohon ekspressi untuk (E1) * (E2).

Huffman Code:

Hubungan Level dengan Jumlah Data :

Level ke :	Jumlah Data
	Minimum	Maksimum
1	1	1 = 20
2	1	2 = 21
3	1	4 = 22
4	1	8 = 23
5	1	16 = 24
6	1	32 = 25
…	…
L	1	2(L-1)

2.      Binary Search Tree (BST)

Binary Search Tree adalah tree yang terurut (ordered Binary Tree). Aturan yang

harus dipenuhi untuk membangun sebuah BST adalah sebagai berikut:

·         Semua data dibagian kiri sub-tree dari node t selalu lebih kecil dari data dalam node t itu sendiri.

·         Semua data dibagian kanan sub-tree dari node t selalu lebih besar atau sama dengan data dalam node t.

 

Deklarasi Pohon Biner dengan program C++

Dalam setiap simpul selalu berisi dua buah pointer untuk menunjuk ke arah cabang kiri dan cabang kanan dan informasi yang akan di simpan dalam simpul tersebut. 

Penyajian Pohon Binar (binary tree)

• Tree dapat dibuat dengan menggunakan linked list secara rekursif 
• Linked list  yang digunakan adalah double linked list non circural
• data yang pertama kali masuk akan menjadi node root
• data yang lebih kecil dari node root akan masuk dan menempati node kiri dari node root,sedangkan jika lebih besar akan masuk dan menempati node sebelah kanan node root

Penyajian Binary tree dalam memory

a.       Penyajian dengan Double Linked List

Penyajian Linked List untuk Binary tree menggunakan array parakek : DATA, LEFT,RIGHT, dan Variabel Pointer ROOT.

Implementasi Binary Tree :

a. Array

b. Linked List

Implementasi BT pada array :

- Indeks pada array menyatakan nomor kode

- Node root mempunyai indeks array = 1

- Leftchild suatu node dengan nomor p adalah (2p)

- Rightchild suatu node dengan nomor p adalah (2p+1)

- Parent dari suatu node dengan nomor p adalah (p div 2)

Implementasi Binary Tree dengan Linked List

Uses crt;

Type

Pointer =^Cell;

Cell = Record

Kiri : Pointer;

Info : Char; (* boleh diganti dg integer / tipe data lain *)

Kanan : Pointer;

End;

BST = Pointer;

           Misalkan Node N berada pada lokasi K, maka

·         DATA [K] adalah isi data dari N

·         LEFT [K] adalah lokasi left Child dari N

·         RIGHT [K] adalah lokasi right Child dari N

a.       Penyajian Secara Sequential

Andaikan T adalah sebuah binary tree, maka penyajian T yang efisien adalah penyajian sequential. Penyajian ini hanya menggunakan single-linier array TREE.

(a)    ROOT R dari T disimpan dalam TREE[1]

(b)   Jika node N berada pada TREE[K] maka left Child disimpan

Dalam TREE[2*K] dan right Child disimpan dalam TREE[2*K+1]

3.  AVL Tree

Definisi : BST yang mempunyai ketentuan bahwa maks

perbedaan tinggi antara subtree kiri dan kanan adalah satu

Height-Balanced Tree :

·         BST adalah Height Balanced p-tree yang artinya maksimum

perbedaan height antara subtree kiri dan kanan adalah p

·         AVL Tree adalah height balanced 1-tree yang berarti

maksimum perbedaan height antara subtree kiri dan kanan

adalah satu

a)      TallLeft bila subtree kiri lebih panjang dari subtree kanan

(simbol -)

b)      TallRight bila subtree kanan lebih panjang dari subtree kiri

(simbol +)

c)      Balance bila Subtree kiri dan kanan mempunyai height

sama, simbolnya 0

Search Path :

Path pencarian lokasi untuk dilakukan operasi insert dimulai

dari Root

Pivot Point :

·         Adanya node pada search path yang balancenya TallLeft

(tanda -) atau TallRight (tanda +) dan terletak paling dekat

dengan node yang baru

·         Contoh : Jika diinsert node baru dengan nilai 5, maka pivot

pointnya di node 25

Operasi Insert :

·         Kasus-1

Tidak ada pivot point dan setiap node adalah balance, maka bisa langsung diinsert sama seperti BST.

·         Kasus 2

Jika ada PP tetapi subtree yang akan ditambahkan node baru memiliki height yang lebih kecil, maka bisa langsung diinsert.

·         Kasus 3

Jika ada PP dan subtree yang akan ditambahkan node baru memiliki height yang lebih besar, maka tree harus digenerate supaya tetap menghasilkan AVL Tree        .

Regenerate :

·         Single Rotation

a.Single Left Rotation

b.Single Right Rotation

·         Double Rotation

a. Double Left Rotation

b. Double Right Rotation

Algoritma Single Right Rotation :

Function SRR (R : Node) : Node;

Begin

Node P := R^.Left;

R^.Left := P^.Right;

P^.Right := R;

SRR := P;

End;

Algoritma Single Left Rotation :

Function SLR (R : Node) : Node;

Begin

Node P := R^.Right;

R^.Right := P^.Left;

P^.Left := R;

SLR := P;

End;

Algoritma Double Right Rotation :

Function DRR (R : Node) : Node;

Begin

Node P := R^.Left;

Node Q := P^.Right;

R^.Left := Q^.Right;

P^.Right := Q^.Left;

Q^.Right := R;

Q^.Left := P;

DRR := Q;

End;

Algoritma Double Left Rotation :

Function DLR (R : Node) : Node;

Begin

Node P := R^.Right;

Node Q := P^.Left;

R^.Right := Q^.Left;

P^.Left := Q^.Right;

Q^.Left := R;

Q^.Right := P;

DLR := Q;

End;               

4.         Splay-Tree

Splay-Tree merupakan salah satu modifikasi binary search tree dengan tujuan tertentu. Tujuan utama dari konsep splay-tree ini adalah untuk memudahkan pencarian dan pengambilandata terutama data yang baru masuk dan yang paling aktif diakses atau dimodifikasi. Perbedaan utama splay-tree dibandingkan binary search tree ataupun AVL-Tree adalah data baru atau yang frekuensi aksesnya tinggi berada dekat dengan akar pohon sehingga untuk mengakses data tersebut tidak diperlukan waktu yang lama dibandingkan dengan binary search tree atau AVL-Tree yang membuat kita harus menelusuri pohon sampai  ke daun karena data baru akan ditempatkan sebagai daun. Untuk jenis data seperti inilah splay-tree sangat dibutuhkan dimana setiap kali adanya operasi penambahan atau juga pengambilan data, struktur pohonnya akan dirombak ulang dengan menaikkan data tersebut (jika berada dibagian bawah pohon /daun) sesuai dengan tingkat frekuensi akses dan keterbaharuannya.

Aplikasi Splay Tree

Contoh nyata dari struktur data yang menggunakan konsep splay-tree ini adalah struktur data sebuah rumah sakit. Tentunya kita tahu bahwa sebuah rumah sakit itu harus menjaga record data pasien-pasiennya. Record data pasien-pasien yang masih berada dirumah sakit tentunya mempunyai keaktifan yang tinggi atau dengan kata lain frekuensi akses nya tinggi, sedangkan untuk pasien yang sudah keluar rumah sakit frekuensi aksesnya akan rendah. Dan sebuah rumah sakit tidak boleh menghapus data pasien yang sudah keluar dari rumah sakit tersebut karena tentunya data tersebut bisa saja akan dibutuhkan disuatu saat nanti oleh pihak-pihak lain misalnya. Dan untuk itulah akan sangat tidak efisien jika record data pasien baru atau yang frekuensi aksesnya tinggi berada pada tingkat daun pada struktur data pohon tersebut sehingga untuk setiap kali mengaksesnya diperlukan waktu yang lebih lama dibanding dengan record data yang tergolong sudah tidak aktif lagi.

Pembuatan Splay-Tree

Seperti yang telah dijelaskan tadi, splay tree adalah sebuah binary search tree yang sedikit dimodifikasi. Oleh karena itu untuk membuat splay tree kita hanya perlu melakukan proses splaying pada binary search tree. Ide utama dalam melakukan splaying adalah memindahkan simpul tujuan 2 level keatas dalam setiap langkahnya. 3 Sekarang bayangkan lintasan dari akar sampai ke simpul yang telah diakses. Setiap kali kita bergerak kekiri disebut zig dan setiap kekanan disebut zag. Bergerak 2 kali kekiri disebut zigzig, 2 kali kekanan disebut zag-zag, kekiri lalu kekanan disebut zig-zag, dan kekanan lalu kekiri disebut zag-zig. Inilah 4 kemungkinan yang dapat terjadi saat bergerak 2 level kebawah. Bagaimanapun jika panjang lintasannya genap, diperlukan satu langkah lagi baik kekiri ataupun kekanan. Berikut contoh zig-zig, zig-zag, dan zag. Sisanya yaitu zag-zag, zag-zig, dan zig merupakan refleksinya saja.

Semoga Bermanfaat.............