Tree and Binary Tree - 2101713241 - Claudia Anita Magdalena

Binary Tree Concept

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

Macam - macam binary tree:

- Perfect Binary Tree

Perfect Binary Tree adalah binary tree yang setiap levelnya berada pada depth yang sama.

- Complete Binary Tree

Complete Binary Tree adalah binary tree yang setiap levelnya (kecuali yang terakhir), sudah terisi semua.

- Skewed Binary Tree

Skewed Binary Tree adalah binary tree yang masing-masing node mempunyai anak yang paling banyak satu.

- Balanced Binary Tree

Node dalam Binary Tree
Jumlah maksimun node pada tiap tingkat adalah 2<sup>n

Node pada binary tree maksimunnya berjumlah</sup> 2ⁿ -1

Representasi dari Binary Tree

- Implementasi menggunakan array

Index pada array merepresentasikan nomor node.

Index ke-0 adalah akar node.

Index pada left child = 2p+1, dimana p merupakan index parent

Index pada right child = 2p+2

Index parent = (p-1)/2

- Implementasi menggunakan linked list

struct node{

      int data;

      struct node *left;

      struct node *right;

      struct node *parent;

};

struct node *root = NULL;

04 - Introduction to Tree, Binary Tree and Expression Tree - 2101713241 - Claudia Anita Magdalena

• Tree

Tree adalah sebuah kumpulan-kumpulan nodes. 

Node bagian paling atas dinamakan root. 

Nodes yang tidak mempunyai children dinamakan leaf. 

Nodes yang mempunyai parent yang sama dinamakan sibling. 

Garis yang menghubungkan parent dan child dinamakan edge. 

Degree of node merupakan total sub tree dari node. 

Height/Depth merupakan maksimum degree dari nodes pada tree.

Jika terdapat garis yang menghubungkan p ke q, maka p dinamakan ancestor dari q, dan q adalah descendant dari p.

Contoh:

Degree of tree = 3

Degree of C = 2

Height = 3

Parent of C = A

Children of A = B,C,D

Sibling of F = G

Ancestor of F = A,C

Descendant of C = F, G

• Binary Tree Concept

Binary Tree adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Umumnya, anaknya dinamakan kiri dan kanan. Node yang tidak mempunyai anak dinamakan leaf. 

Contoh: 

Binary tree diatas mempunyai 9 nodes dan berakar pada 18. Leaves nodenya adalah 9, 12, 10 dan 23.

Macam - macam binary tree:

- Perfect Binary Tree

Perfect Binary Tree adalah binary tree yang setiap levelnya berada pada depth yang sama.

- Complete Binary Tree

Complete Binary Tree adalah binary tree yang setiap levelnya (kecuali yang terakhir), sudah terisi semua.

- Skewed Binary Tree

Skewed Binary Tree adalah binary tree yang masing-masing node mempunyai anak yang paling banyak satu.

- Balanced Binary Tree

• Representasi dari Binary Tree

- Implementasi menggunakan array

Index pada array merepresentasikan nomor node.

Index ke-0 adalah akar node.

Index pada left child = 2p+1, dimana p merupakan index parent

Index pada right child = 2p+2

Index parent = (p-1)/2

- Implementasi menggunakan linked list

struct node{

      int data;

      struct node *left;

      struct node *right;

      struct node *parent;

};

struct node *root = NULL;

• Ekspresi dari Tree 

Contoh: 

-Prefix : *+ab/-cde

-Postfix : ab+cd-e/*

-Infix : (a+b)*((c-d)/e)

• Prefix Tranversal

Pada prefix, kita harus print terlebih dahulu sebelum childnya di proses.

void prefix(struct tnode *curr){

        printf("%c", curr->chr);

        if(curr->left != 0) prefix(curr->left);

        if(curr->right!= 0) prefix(curr->right);

}

• Postfix Traversal

Pada postfix, kita harus print setelah childnya di proses.

void prefix(struct tnode *curr){

        if(curr->left != 0) prefix(curr->left);

        if(curr->right!= 0) prefix(curr->right);

        printf("%c", curr->chr);

}

• Infix Traversal

Pada infix, mungkin memiliki ambiguitas operator tanpa tanda kurung.

Contohnya:

* + a b c pada prefix akan dikodekan dalam infix sebagai a + b * c dengan kode sebelumnya, sementara infix yang benar adalah (a+b) * c.

a + b * c : b dikalikan dengan c kemudian ditambahkan dengan a.

(a+b) * c : a ditambahkan dengan b kemudian dikalikan dengan c.

Solusinya adalah kita dapat menambahkan brackets () ketika menuliskan operator.

void infix(tnode *curr){

        if(is_operator(curr->chr))putchar( '(' );

        if(curr->left != 0) infix(curr->left);

        printf("%c", curr->chr);

        if(curr->right!= 0) infix(curr->right);

        if(is_operator(curr->chr))putchar( '(' );        

}

Jadi, * + a b c pada prefix akan dikodekan sebagai ((a+b) * c) pada infix, dan ini benar.

03 - Linked List Implemention II - 2101713241 - Claudia Anita Magdalena

• Stack 

Stack (tumpukan) adalah linear data struktur yang diimplementasikan dengan menggunakan array atau linked list. Data disimpan dengan cara "Last In First Out".

Dalam representasi array, stack mempunyai dua variable yaitu
- TOP, digunakan untuk menyimpan alamat dari element stack yang paling atas.
- MAX, digunakan untuk menyimpan nilai maximun dari stack.

Dalam representasi linked list, stack mempunyai node. Setiap node mempunyai dua bagian yaitu untuk menyimpan data dan untuk menyimpan alamat dari node selanjutnya. Pointer START dari linked list digunakan sebagai TOP.

Operasi stack yaitu push, pop, top.
- push(x), menambah suatu item x dari bagian atas stack.
- pop(), menghapus suatu item dari bagian atas stack.
- top(), mengembalikan/menyatakan bagian atas dari stack.

Stack dapat digunakan untuk,
1. Infix, Postfix, dan Prefix Notation

Prefix : operator ditulis sebelum operand.

Infix : operator ditulis diantara operand.

Postfix : operator ditulis setelah operand.

Prefix dan postfix notation tidak membutuhkan tanda kurung untuk memprioritaskan suatu operator.
Prefix dan postfix sangat mudah untuk komputer meng-evaluate.

2. Depth First Search
Depth First Search (DFS) adalah suatu algoritma untuk mencari dalam tree atau graph. DFS dapat digunakan untuk mencari artikulasi point dan bridge dalam graph, mencari komponent yang terhubung, topological sorting, dll. DFS dapat diimplementasikan dengan fungsi rekursif atau iterative prosedur dengan menggunakan stack.

3. Membalikkan urutan data.
4. Mengkonversi ekspresi infix menjadi postfix.
5. Mengkonvesi ekspresi postfix menjadi infix, dan sebagainya.

• Queue

Queue (antrian) dapat diimplementasikan dengan menggunakan array atau linked list. Data disimpan dengan cara "First In First Out".

Dalam representasi array, queue mempunyai dua variable yaitu

- Front dan Rear yang menunjukkan posisi deletions dan insertions.

Dalam representasi linked list, sama dengan stack. Setiap element mempunyai dua bagian yaitu untuk menyimpan data dan untuk menyimpan alamat dari element selanjutnya.

Operasi queue yaitu push, pop, front.

- push(x), menambah suatu item dari bagian belakang queue.

- pop(), menghapus suatu item dari bagian depan queue.

- front(), mengembalikan item yang paling depan dari queue.

Queue dapat digunakan untuk,

1. Deques

Deques adalah list dimana setiap element dapat dimasukkan atau dihapus pada bagian belakang. Deques juga dikenal sebagai head-tail linked list, karena setiap elemet dapat ditambah atau dihapus dari bagian depan (head) atau belakang (tail).

Terdapat dua varian dari double-ended queue yaitu,

- Input restricted deque

- Output restricted deque

2. Priority Queue

Priority Queue adalah abstrak data type yang dimana setiap element diberi prioritas. 

Ada aturan dalam memproses element dari priority queue yaitu,

- Element dengan priority yang lebih tinggi dari element dengan priority lebih rendah akan diproses terlebih dahulu.

- Dua element yang mempunyai priority yang sama akan diproses dengan "First Come First Served".

3. Breadth First Search

Breadth First Search (BFS) adalah suatu algoritma untuk mencari dalam tree atau graph.

BFS dapat digunakan untuk,

- Mencari komponen yang terhubung dalam graph

- Mencari shortest path, dan sebagainya.

 

Perbedaan nya dengan DFS adalah BFS menggunakan konsep queue, sedangkan DFS menggunakan konsep stack.

01 - Introduction to Data Structure - 2101713241 - Claudia Anita M

Data Structure

Struktur data adalah cara menyimpan data-data pada memori komputer maupun file secara efisien. Disebut juga dengan jenis data kompleks.

Beberapa tipe data strukur:

• Array

- Kumpulan element data yang memiliki tipe data yang sama.

• Linked lists

- Bersifat dinamik, yang artinya element dapat ditambah atau dihapus secara mudah.

- Setiap element disebut dengan node.

• Queues

- Elemen yang diinsert pertama akan dikeluarkan pertama juga. (First In, First Out)

- Seperti sistem antrian.

• Stacks

- Elemen yang diinsert pertama, akan dikeluarkan terakhir. (Last In, First Out)

- Seperti sistem tumpukkan.

• Binary Trees

- Binary trees adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak.

- Setiap simpul terdiri dari pointer.

• Hash Tables

Data Type

• Abstract Data Type

Abstract Data Type (ADT) adalah tipe data yang diatur menggunakan struktur data tertentu sehingga spesifikasi data dan spesifikasi operasinya terpisah dari representasi dan implementasinya.
Contohnya, dalam bahasa C/C++ mempunyai konsep yang disebut dengan class dan struct yang merupakan implementasi dari ADT.

01 - Array dan Pointer - 2101713241 - Claudia Anita M

Array

Array adalah kumpulan dari elemen data yang mempunyai tipe data yang sama. Elemen dari array disimpan dalam lokasi memori yang berurutan yang dinamakan indeks. Indeks array dimulai dari nol.

Menurut dimensinya, array dapat dibedakan menjadi :

- Array berdimensi satu

• Deklarasi array : tipearray namarray[ukuran];

Contohnya: int arr[5];

• Setiap elemen array dapat diakses melalui indeks.

- Array berdimensi dua

• Deklarasi array : tipearray namaarray[ukuran1][ukuran2];

Contohnya: int arr[2][6];

• Array dua dimensi terdiri dari baris dan kolom. Bentuknya dapat berupa matriks atau tabel.

- Array multidimensi

• Array multidimensi adalah array yang memiliki ukuran lebih dari dua.
• Deklarasi array : tipe array namaarray[ukuran1][ukuran2][ukuran3][...];

Contohnya: int arr[4][8][6][10];

Bentuk pendeklarasian array sama saja dengan deklarasi array satu dimensi atau array dua dimensi.

Cara menyimpan nilai array:
- Insialisasi Array

• Ketika membuat sebuah array, setiap elemen di dalamnya akan diinisialisasi dengan nilai default. Contohnya jika array di definisikan sebagai array dari tipe integer maka nilai defaultnya adalah nol.

Contoh: 

int marks[5] = {1,2,3,4,5};

- Inputting Values

• Ketika kita memiliki variabel tipe array maka kita dapat merujuk pada elemen tertentu pada array dengan menentukan nama variabel dan indeks yang mewakili elemen dari array tersebut.
• Dalam array, kita tidak bisa merujuk pada elemen array yang berada di luar batas ukuran maksimal indeks array.

Contoh:

int i, marks[10];

for(i=0; i<10; i++) scanf("%d", &marks[i]);

- Assigning Values

Contoh:
int i, arr1[10], arr2[10];
for(i=0; i<10; i++) arr2[i] = arr1[i];

Terdapat beberapa operasi pada array, yaitu: Traversal, Insertion, Searching, Deletion, Merging, Sorting.

Pointer

Pointer adalah sebuah variabel yang digunakan untuk sebagai penunjuk alamat dari variabel lain.

Operator yang digunakan dalam pointer adalah & dan *. & digunakan untuk menunjukkan alamat dari suatu nilai sedangkan * digunakan untuk menunjukkan nilai.

Contohnya sebagai berikut:

Jika kita mendeklarasi sebuah tipe data sebagai berikut:

int x; -> integer

int *px; -> pointer integer

Jika kita menentukan:

px = &x;

maka, nilai dari px adalah alamat dari x.