Tree

Merupakan salah satu bentuk strukture data tidak linear yang menggambarkan 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 lainnya (disebut subtree). Untuk jelasnya, di bawah akan diuraikan istilah-istilah umum dalam tree :

1. a) Prodecessor : node yang berada diatas node tertentu.
2. b) Successor : node yang berada di bawah node tertentu.
3. c) Ancestor : seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. d) Descendant : seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
5. e) Parent : predecssor satu level di atas suatu node.
6. f) Child : successor satu level di bawah suatu node.
7. g) Sibling : node-node yang memiliki parent yang sama dengan suatu node.
8. h) Subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.
9. i) Size : banyaknya node dalam suatu tree.
10. j) Height : banyaknya tingkatan/level dalam suatu tree.
11. k) Root : satu-satunya node khusus dalam tree yang tak punya predecssor.
12. l) Leaf : node-node dalam tree yang tak memiliki seccessor.
13. m) Degree : banyaknya child yang dimiliki suatu node.

Beberapa jenis Tree yang memiliki sifat khusus :

1) Binary Tree

Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksial 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 :

1. a) Full Binary Tree

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

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

1. c) Skewed Binary Tree

akni 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 :

(Ket: LC=Left Child; RC=Right Child)

Operasi-operasi pada Binary Tree :

v Create : Membentuk binary tree baru yang masih kosong.

v Clear : Mengosongkan binary tree yang sudah ada.

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

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

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

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

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

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

v 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)

v 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 :

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

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

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

(Keadaan awal merupakan lanjutan gambar sebelumnya)

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

Tree atau Pohon, sekumpulana 1 data atau lebih yang berhubungan.

Konsep Tree :

• Node paling atas disebut root
• Suatu garis yang menghubungkan kedua node disebut edge
• Node yang tidak memiliki child disebut leaf
• Node yang mempunyai parent yang sama disebut sibling

Konsep Binary Tree :

•  Setiap Node mempunyai paling banyak 2 child
• Setiap childnya biasa dibedakan dengan LEFT dan RIGHT
• Node yang tidak mempunyai child disebut leaf

Expression Tree

Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)

Structure Node yang digunakan adalah :
struct tnode
{
char chr;
struct tnode *left;
struct tnode *right;
};

Prefix Traversal (Print Left Right):
void prefix (struct tnode *curr)
{
printf(“%c”, curr->chr);
if (curr->left) prefix(curr->left);
if (curr->right) prefix(curr->right);
}

Post Traversal (Left Right Print):
void postfix (struct tnode *curr)
{
if (curr->left) postfix (curr->left);
if (curr->right) postfix (curr->right);
printf(“%c”, curr->chr);
}

Infix Traversal (Left Print Right) :
void infix (struct tnode *curr)
{
if (is_operator(curr->chr)) putchar(‘(‘);
if (curr->left) infix(curr->left);
printf(“%c”, curr->chr);
if (curr->right) infix(curr->right);
if (is_operator(curr->chr)) putchar(‘)’);
}

Stack
Stack adalah salah satu data struktur yang menggunakan konsep LIFO (Last In First Out). Dimana data paling terakhir yang ditambahkan akan diambil terlebih dahulu.
Stack mempunyai 2 variables, yaitu top dan max, dimana top adalah element paling atas dan max adalah jumlah element yang dapat ditampung
Stack memiliki beberapa method yaitu :

1. push(x) : menambahkan item x kedalam stack
2. pop() : menghapus data yang paling terakhir ditambahkan
3. top() : mengakses data yang paling terakhir ditambahkan

Terdapat 3 notasi yang diketahui :

1. Prefix (Reverse Polish Notation)
   Operator yang ditulis sebelum operans
   Contoh : ++x
2. Infix
   Operator yang ditulis diantara kedua operans
   Contoh : x + y
3. Postfix (Polish Notation)
   Operator yang ditulis sesudah operans
   Contoh : x++

Langkah-langkah konversi Infix ke Postfix :

1. Cari operator dengan presendensi tertinggi
2. Letakkan operator tersebut ke belakang operan
3. Ulangi hingga selesai

Depth First Search (DFS)
DFS adalah suatu algoritma untuk mencari atau menelusuri suatu pohon. Pencarian atau penelusuran akan dimulai dari anak pohon paling terakhir atau element terdalam dalam suatu pohon.

Contoh penggunakan DFS yaitu :

• Mencari komponen yang terhubung
• Mengurutkan topologi

DFS dapat diimplementasikan dengan fungsi rekursif atau prosedur iteratif menggunakan stack.

Algoritma DFS (Pseudo-code) :
create empty stack
push root into stack
mark root
While stack is not empty
Pop an item from stack into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into stack

Queue
Queue adalah salah satu stuktur data yang menggunakan konsep FIFO (First In First Out). Yang maksudnya adalah data yang paling pertama masuk adalah data yang paling pertama diambil. Contoh dari queue adalah seperti sebuah antrian saat orang ingin membayar belanjaan.

Queue dapat diimplementasikan menggunakan array atau linked list

Queue mempunyai 2 variable, yaitu rear dan front. Dimana front adalah element pertama dari sebuah queue dan rear adalah element terakhir dari queue.

Queue yang diimplementasikan menggunakan linked list :
– Root atau data pertama disebut FRONT
– Pointer dari suatu node yang digunakan untuk menunjuk data selanjutnya disebut REAR
– Menggunakan push tail
– Jika FRONT = REAR = NULL , Maka queue kosong

Operasi Queue :

1. push(x) : Menambahkan item x ke belakang queue
2. pop() : menghapus item paling depan dari suatu queue
3. front() : mengakses item palign depan dari suatu queue

Circular Queue, adalah suatu data struktur yang mirip dengan queue. Perbedaannya terletak pada data terkahir yang terhubung ke data awal sedangkan queue biasa tidak terhubung

Deques
Deques, adalah suatu list yang dimana element didalamnya dapat disisipkan atau dihapus di kedua ujungnya

Priority Queue
Priority queue adalah suatu struktur data yang mirip dengan queue. Namun terdapat suatu perbedaan dimana saat kita akan menambahkan data dan menghapus, data akan dipilih berdasarkan prioritas yang kondisinya telah ditetapkan terpenuhi.

Breadth First Search (BFS)
Breadth First Search, adalah suatu algoritma yang digunakan untuk mencari atau menelusuri suatu tree berdasarkan level-level treenya.

Contoh penggunaaan BFS :

• Mencari jarak terpendek dari unweight graph
• Mencari komponen yang terhubung di dalam suatu graph

Perbedaan dari BFS dan DFS ialah
DFS menggunakan stack sedangkan BFS menggunakan queue

Algoritma BFS (Pseudo-code) :
Prepare an empty queue
Push root into queue
Mark root
While queue is not empty
Pop and item from queue into P
For each node X adjacent with P
If X is not marked
Mark X
Push X into queue

Structure adalah suatu data tipe buatan user yang digunakan untuk menyimpan sekumpulan data yang berkaitan secara bersama-sama, sedangkan array hanya dapat menyimpan informasi atau data dengan tipe yang sama. Data-data didalam struktur dapat memiliki tipe data yang berbeda.

Cara Membuat Structure :
struct nama_struct
{
tipe_data variable_pertama;
tipe_data variable_kedua;
// dan seterusnya
};

Contoh :
struct Mahasiswa
{
char nim[11];
char nama[101];
};

Untuk membuat variable dengan tipe data struct yang dibuat user, kita membuatnya seperti membuat variable biasa.
Contoh :

struct Mahasiswa mhs;

atau Kita Bisa Mendeklarasikan struct dan sekaligus membuat variablenya.
Contoh :

struct Mahasiswa
{
char nim[11];
char nama[101];
} mhs;

Untuk mengakses variable yang terdapat didalam sebuah struct, kita menggunakan symbol “.” (dot).
Contoh :

strcpy(mhs.nama, “Ivan”); // Memberikan nilai
printf(“%s”, mhs.nama); // Mengakses nilai

Nested Structure
Kita dapat membuat struct di dalam struct.
Contoh :
struct Gamer
{
char nama[101];
int level;
};

struct Mahasiswa
{
char nim[11];
char nama[101];
Gamer gamer;
} mhs;

Kita juga bisa membuat Array of Structure
Contoh :

struct Mahasiswa mhs[100];

Dynamic Memory Allocation
Kita dapat mengalokasikan memory dinamis saat runtime. Caranya adalah dengan menggunakan fungsi malloc(). Untuk menghapus memory yang sudah dialokasikan, kita gunakan fungsi free()
Contoh :

int *p = (int*) malloc(sizeof(int)); // Allocate
free(p); // Deallocate

Perkenalan Linked List
Linked List adalah suatu struktur data yang terdiri dari deretan data dimana setiap data mempunyai suatu field / variable yang digunakan untuk mengakses data sebelahnya. Setiap data didalam linked list disebut Node. Linked List yang hanya memiliki 1 variable penghubung ke node lain disebut Single Linked List.

Array VS Linked List
Array :
– Sekumpulan element
– Menyimpan nilai di lokasi memory yang berurutan
– Dapat diakses secara random

Linked List :
– Sekumpulan node
– Tidak menyimpan node di memory yang berurutan
– Hanya dapat diakses secara berurutan

Struct adalah sebuah tipe data yang berfungsi untuk membuat tipe data yang baru, misalnya struct x{ int y, char z}; jadi ada tipe data baru yaitu x, biasanya struct ini digunakan untuk membuat kodingan lebih teratur.
untuk mengakses isi dari struct itu, kita menggunakan yang namanya method, contoh kita membuat variable test dengan tipe data x (x test), untuk meninisialisasi kita menggunakan method, yaitu test.y=1.
maximum dari dimension array tergantung bahasa yang dipakai, untuk java maximum dari dimension arraynya adalah 255.

penggunaan struct paling terlihat ketika menggunakan konsep dari link list, link list dibedakan menjadi beberapa bagian, ada single link list, double link list, dan juga ada tree.
pada link list ada 2 tipe, yaitu lifo atau last in first out, dan juga fifo atau first in first out. untuk lifo dan fifo, pengandaian simplenya untuk 2 ini adalah lifo adalah cucian piring, dan untuk fifo adalah antrian atm, ketika piring masuk dia akan ke paling atas, dan ketika ingin dipakai akan diambil paling atas, jadi dia adalah lifo, dan untuk fifo, siapa yang datang duluan maka akan bisa menggunakan atm, jika ada yang datang terakhir maka dia akan bisa gunakan paling terakhir.

Na, apa yang membedakan Array dan Link list ada pada sifatnya, Array bersifat statis, jadi ketika dipesan 10 maka dia akan tetap 10, namun Link list bersifat dinamis, dia dapat bertambah dan berkurang tergantung penggunaannya.

perbedaan antara Single Link List dan Double Link List adalah arah dari link list tersebut, Single link list hanya mengenal satu arah, namun untuk double link list memiliki 2 arah, jadi untuk pengandaiannya, untuk single link list, itu seperti orang hanya meletakkan salah satu tangannya ke pundak yang sebelahnya, jadi dia hanya memiliki 1 akses, yaitu hanya bisa maju,misalnya a ke b, tapi b tidak bisa ke a. untuk double link list itu seperti orang bergandengan tangan, jadi dia memiliki 2 akses, yaitu mundur dan maju,jadi a bisa ke b, dan b bisa ke a.

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂