AVL Tree

AVL Tree dapat dikatakan sebagai self balancing BST (Binary Search Tree) dimana perbedaan ketinggian di setiap node tidak boleh lebih dari 1.

Jika ada node yang lebih dari 1, maka AVL akan membalance dianya sendiri saat insertion atau deletion node dengan cara rotation:
- Right Rotation
- Left Rotation
- Right Left Rotation
- Left Right Rotation
- Double Rotation

Contoh AVL

Ini merupakan AVL karena perbedaan ketinggian setiap node tidak lebih dari 1.

Contoh Non-AVL

Ini merupakan Non-AVL karena perbedaan ketinggian di node 12 -> 4-2 = 2, 8 -> 3-1 = 2.

Hashing Table & Binary Tree

Before knowing about Hashing Table we first must understand what hashing is. Hashing is a technique used for storing and retrieving keys in a fast manner. In hashing, a string of characters are transformed into shorter length values or key that represents the original string of characters.

Example: "H"ello. H will be defined as the key to the string of characters and placed in to the Hash Table.

Hashing Table

Hashing Table is an array where we store the original string. The index of the table is the hashed key, the value is the original string.

Example: I[ ]       Value
                  0         alphabet
                  ...        ...
                  8         hello

There are many ways to define the key of a string, some of the important one are:
-Mid Square
-Division
-Folding
-Digit Extraction
-Rotating Hash

Mid Square
The string of characters are converted into numbers and squared. After being squared, the middle part of the value is extracted. Example: Key -> @(64) -> 64^2 -> 4"09"6 -> "09" is extracted.
Extracting the middle part can be easily done with mask and shift operations.

Division
The string is divided using the modulus operator. We take each character of the string and total it, then we use the modulus operator(we will be dividing it by 64). It is by far the simplest method to hash an integer x.
Example: "HELLO" -> 72(H) + 69(E) + 76(L) + 76(L) + 79(O) =  372 % 64 = 52.

Folding
Partition the string into each parts, then sum each parts to obtain the hash key.
Example: "HELLO" = 372 -> 37 + 2 = 39.

Digit Extraction
Extraction through a given digit. Example: 1976542 we take the xth digit, in this case we'll be using 2nd,3rd and 5th. That will give use 975 for our hash key.

Rotating Hash
Using any hash method, we then rotate the digits. Example: 12345 -> 54321.

What would we do if a collision happened. Example : The hash table I[1] already has "b"ounty, while we want to insert another string that is "b"elieve. There are two ways to deal with this situation, that is : Linear Probing and Chaining.

Linear Probing
Going back to the Example of having I[1] already filled with "b"ounty. We will insert "b"elieve into the next available Index that is I[2].

Chaining
In this method we will not be inserting the string "b"elieve into I[2]. Instead we will be inserting the string into a linked list node in I[1].

According to my research there are no difference in using Hash Table nor Blockchain. Both are reliable.

Binary Tree

Simply, binary tree is s rooted tree that has atmost two branches. Those two branches are distinguished as left and right. A branch that is cut off will be named a leaf.

Example: This binary tree's main root is the node 18, while the leaves are (9,12,23).

Linked List II

According to the material that has been passed on to me about Linked List. Here's what i can conclude from the materials:

Struct for previous and next

Code:

struct tnode node{
      int nim;
      tnode *next,*prev;
}*head,*tail,*curr;

Before learning the other type of Linked List we must understand how to Insert,Delete,Push,Pop the Data in the List.

Linked List: Insertion

Code:

struct tnode *node =

(struct tnode*) malloc (sizeof(struct tnode));

node->value = x;

node->next = head;

head = node;

Linked List: Delete

Code:

struct tnode *curr = head;

if ( head->value == x ) {

head = head->next;

free(curr);

}

Linked List: Push

Code:

void Push();

struct tnode *node = (struct *node) malloc(sizeof(struct node));

if(head==NULL){

      head = nim;

}else{

head->next=nim;

}

void PopHead();

//set global variable *temp;

struct tnode *node = (struct *node) malloc(sizeof(struct node));

      temp = head;

      head=temp->next;

      free(temp);

After learning how to Insert,Delete,Push,and Pop, we can now proceed to the other type of Linked List.

Double Linked List

In Double Linked List, every node has a pointer to it's previous and next node.

References: BinusMaya

Linked List

Linked List merupakan data struktur yang isinya ialah urutan data yang saling berhubungan. Cara 

Linked List kerja ialah secara Urutan/Sequence.

Linked List dapat digunakan untuk masalah sehari-hari.

Kekurangan menggunakan Linked List ialah:

· Mereka menggunakan lebih banyak memori daripada array karena penyimpanan yang digunakan oleh pointer mereka.

· Node dalam daftar tertaut harus dibaca secara berurutan karena daftar tertaut secara inheren merupakan akses berurutan.

· Node disimpan secara tidak bersamaan, sangat meningkatkan periode waktu yang diperlukan untuk mengakses elemet individual dalam daftar, terutama dengan cache CPU.

· Kesulitan muncul dalam daftar tertaut ketita datang untuk membalikkan traverse. Misalnya, daftar yang ditautkan secara tunggal sulit untuk dinavigasi ke belakang dan sementara daftar yang ditautkan agak lebih mudah dibaca, memori dikonsumsi dalam mengalokasikan ruang untuk penunjuk-belakang.

Setelah mengenal Linked List, ada juga beberapa kategori Linked List yaitu: Single Linked List, Double Linked List,  Circular Linked List, Circular Double Linked List.

Single Linked List

Single Linked List hanya memiliki satu hubungan yaitu antara data sebelumnya atau di sesudahnya, tidak kedua-duanya. Dengan kata lain, dalam setiap data memiliki Satu Pointer.

Contoh codingan untuk membuat urutan integer:

Struc tnode {

int value;

Struct tnode *next;

};

Struct tnode *head = 0;

Single Linked List: Insert

Codingan:

struct tnode *node =

(struct tnode*) malloc (sizeof(struct tnode));

node->value = x;

node->next = head;

head = node;

Single Linked List: Delete

Codingan:

struct tnode *curr = head;

ff ( head->value == x ) {

head = head->next;

free(curr);

}

Double Linked List

Double Linked List sama seperti Single Linked List tetapi, Double Linked List memiliki dua hubungan yaitu data sesudah dan sebelumnya secara bersamaan.

Dengan kata lain satu, dalam setiap data memiliki Dua Pointer.

Circular Single/Double Linked List

Didalam Circular Single Linked List, data terakhir(tail) berisi pointer ke data pertama(head).Sedangkan Circular Double Linked List, sama dengan Circular Single Linked List tetapi bedanya, Circular Double Linked List. Data pertama(head) berisi pointer ke data terakhir(tail).

 

Contoh Circular Single Linked List

                                               Contoh Circular Double Linked List 

Reference:

- https://en.wikipedia.org/wiki/Linked_list

- BinusMaya