Binary Search Tree

Binary Search Tree or BST is one of the Data Structure that have the same properties as Binary Tree, but more organized. The difference on BST is they are made for easier and faster search. This is accomplished by seperating the data using the root node. If there's already a root node on the tree, then you need to see whether the new node you want to insert is larger or smaller than the root. If the new node is smaller, then you place it on the left side of the root as the child. If the new node is larger, then it goes to the right. This way the tree will be sorted easily.

Binary Search Tree has the following properties:

1. The left subtree of a node contains only nodes with keys lesser than the node’s key.
2. The right subtree of a node contains only nodes with keys greater than the node’s key.
3. The left and right subtree each must also be a binary search tree.

There are 3 functions that BST has:

Search

If you already have BST, you can proceed by searching the node that you're looking for.  You need to pay attention on whether the node that you're looking for is larger or smaller than your current nodes. This mean that everytime you do the search per nodes, check it whether its larger or smaller.

(courtesy of GeeksforGeeks)

Insert

(Courtesy of GeeksforGeeks)

Deletion

As almost the same as insert, you first need to search for the nodes that you want to delete. After you found the nodes that you want to delete, procceed by connecting the childs (If exist) of the node to the parents of the node.

Reference

https://www.programiz.com/dsa/binary-search-tree

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

Hash Table

Due to class being a bilingual-language class, I'm going to use English for this point onward. Some may be in Indonesian but mostly it will be in English.

Hash table is one of the several types of Data structures that stores its value in array manner. Usually we use Hash table to store string values. In Hash table, there's a method which called Hashing. In Hash table, we will use the spesific "key" to acquire it's information, so in this type of data structure, you will need a "key". This key can be something like names,code,etc. Every array can be set into certain "key". that array can contain something like attribute and such. For example, if you set your key into names, like "Dave" and you calculate the total amount of their ascii number then modulo it to the amount of array, that way we can tell which array do "Dave" attribute stored at. This way we can search faster than that of the normal linear search for array.

There are 3 basic operations for Hash table: Search, Insert, Delete.

Search

There are several methods on how you do the searching in Hash table, but for the sake of simplicity I will use the division method. What this does is as you can read above in the example, you can convert each character of the string into their ascii numbers. Then you can modulo it to the amount of array or array size. If you formulized it. it can be something like (Ascii) Mod (ArrSize). If you don't know how this can be implemented in C language, then I will show you how :

Insert

Insertion can be as simple as the picture above. As you can see in the last part, you can just use that to put some value into the array that you already have using the previous method. For example: in the last line of the code, we can insert the value into the array that the key has been modulo by the amount of array.

Deletion

Deletion is as the same as insertion, only here you can clear the value inside the array that you want to delete.

Linear Probing

This is one of the solution if you ever have the "Collution" problem. Collution problem is a problem when you already have a value inside a certain array that you want to insert. This will cause a collution between values. This can be avoided using the Linear Probing method. How this works is whenever you find collution, you can always place the same "key" into the next array. This may cause some problem if you have a limited amount of array but a large number of key and its attribute you want to add.

Chaining

This solution is a bit better than Linear Probing. Instead of adding it into the next array, you can make those array into some Linked List where you can store undinifed amount of value that has the same key in the same array.

Binary Tree

Binary tree is the type of data structure that divide the node into some binary node tree. The way it works is you have a root as your base to expand later. then if you want to add another node, you can add it on the left or the right depends on how the value react to the root. If the value is lower than the root, that usually it goes to the left. But if the value is larger than the root, they goes to the right. THE most important part of this tree is that you cannot have more than TWO CHILDS for each node.

The first node or "1" node, is the root of the tree. And the last level of nodes (Such as 8,9,10,11,13,14) is the leaf of the tree.

Types of Binary Tree

There are several types of Binary Tree, some of which are :

Perfect Binary Tree

Complete Binary Tree

Skewed Binary Tree

References :

https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

https://www.geeksforgeeks.org/binary-tree-data-structure/

Binusmaya resource powerpoint

Pictures are from geektogeeks

Single Linked List

Single Linked List adalah jenis linked list yang hanya bisa menunjuk ke node berikutnya, berbeda dengan Double Linked List yang bisa menunjuk sebelumnya.Di dalam Rangkuman ini, kita akan melakukan beberapa fungsi seperti men-insert node baru, men-delete node baru, dan mengeprint semua isi node nya.

1. Insert

Untuk melakukan insert di dalam Single Linked List, kita bisa melakukannya dengan men-insert di depan (pushHead), menginsert di belakang (pushTail).

Membuat fungsi createaccount untuk node baru

Disini kita akan membuat fungsi yang berguna untuk membuat node baru. Di baris pertama, kita ingin mengalokasikan memory yang akan digunakan untuk node baru kita. Caranya adalah dengan syntax malloc. malloc berguna untuk memberi tahu kepada mesin untuk menyediakan memory untuk node yang akan kita buat. Berikutnya kita melakukan strcpy untuk mengcopy email dan password yang kita masukkan kedalam email dan password yang merupakan atribut  node. kemudian kita set node->next = NULL untuk memberi tahu mesin bahwa setelah node itu tidak ada apa-apa. Ini berguna untuk melakukan insert. dan terakhir kita return node kita tadi untuk dimasukkan kedalam pushHead.

pushHead

untuk membuat pushHead, dapat dilihat sebagai berikut :

Disini saya membuat fungsi pushHead untuk struct yang memiliki atribut email dan password. Tahap pertama dalam membuat pushHead adalah membuat pointer baru dimana kita mengunakan fungsin createaccount yang sudah di contohkan diatas. setelah kita mendeklarasikan pointer node nya, kita melakukan selection. Jika head == NULL, maka kita akan membuat Head dan Tail yang baru. Tapi jika sudah ada, maka kita akan bilang bahwa node->next = head dan head = node. Ini berguna untuk mendorong head yang lama sehingga node yang baru kita masukkan menjadi head yang baru.

pushTail

untuk membuat pushTail, dapat dilihat sebagai berikut :

Disini saya membuat fungsi pushTail yang berfungsi untuk memasukkan node baru di setelah Tail (node terakhir). ini bisa dilakukan dengan struktur codingan yang sama dengan pushHead namun bedanya di else kita membuat next dari tail sebagai node yang baru, dan node yang baru kita jadikan tail.

2. Delete

Delete dapat dilakukan dengan 3 cara : yaitu popHead, popMid, dan popTail.

popHead

untuk membuat popHead, dapat dilihat sebagai berikut :

popTail

uintuk membuat popTail, dapat dilihat sebagai berikut :

popMid

untuk membuat popMid, dapat dilihat sebagai berikut :

3. Print

untuk membuat fungsi print, dapat dilakukan sebagai berikut :

4. Inisiasi

untuk menggunakan semua fungsi ini, kita dapat memanggilnya di main dengan cara sebagai berikut :