Skip to main content
GSLC KE-2 Data Structure, Pertemuan ke-6
Materi :
- Hashing and Hash Tables
- Tree and Binary Tree

Hashing and Hash Tables

Hashing is a method used to store data so it can be added, search and delete in a short time.
There are many ways of hashing.
 Hash Functions :

  • Mid-square : Squaring the value of key, taking the middle part.

  • Division : (key) mod (value).

  • Folding : Done by taking parts of a number, adding it, and ignoring some digits of it.

  • Digit Extraction : Extract some digit from a number. for example, given x=219382. We want to extract some of it's digit and make it a hash key, so we extract 1st digit and 4th digit. From that the number we get is 23. 
  • Rotating Hash : Do any of the method above, then rotate the digit. For example, given that x=23354. If we rotate x, it would be 45332.
In some case, Collision will happen... What is a collision ? Collision is when several data have the same hash-key. What can we do to handle it ?
  • Linear Probing : Search the next empty slot and put the data there.
  • Chaining : Put the string n a slot as a chained list (Linked List).
Trees & Binary Tree

Tree ? What is it ? A tree is a non-linear data structure that represents the relationships ammong data objects.
Root = Node at the top (A)
Leaf = Nodes that do not have Children(E,F,G)
Degree = Total sub tree of a node
Height/Depth = maximum degree of nodes in a tree

Meanwhile, Binary Tree is a rooted tree data structure which each node has at most(max) two children.
Type of Binary Tree
- Perfect binary tree, which every level of the binary tree are at the same depth
- Complete binary tree, a binary tree in which every level except the last(optional), is completely filled. If a binary tree is perfect, it is also a complete binary tree.
- Skewed binary tree, a binary tree which each node has at most one children.
- Balanced binary tree, a binary tree which has no leaf far from the root.

In code, Binary tree can be first initialized by
struct node{
  int data;
  struct node *left;
  struct node *right;
};

Then, we can start adding a node by adding a function.
struct node* newNode(int data){
  struct node* node = (struct node*)malloc(sizeof(struct node));
  node->data = data;   
  node->left = NULL;
  node->right = NULL;
  return(node);
}
A simple program to first understand Binary Tree
int main(){
  struct node *root = newNode(1);     
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
}




Comments

Post a Comment

Popular posts from this blog

Rankuman Akhir

Rangkuman Akhir 10 Juni 2020 Nama: Johanes Peter Vincentius NIM: 2301864461 Nama Dosen:Henry Chong(D4460) & Ferdinand Ariandy Luwinda (D4522) Before continuing to my summary, i just want to make a clarification that I did not copas, and if the language is simillar, it's just because I summarize directly from PPT and use a bit of internet for clarification. The point is, I studied while making this summary, sorry if it might have a slight resemblance to the ppt. The summary : Heaps And Tries, both are a data structures algorithm concept In this blog I will be summarizing : Heap Concept Min Heap  Max Heap Min-Max Heap Heap Applications Tries Concept Tries Applications Heap is a complete binary tree which impliments the "heap" property. Heap property ?  Min Heap and Max Heap Min Heap means every node's element is smaller than its children's Max Heap means every node's element is larger than its children's ...
Post a Comment
Read more

Pertemuan III Mengenai pengaplikasian Linked List

Linked List, banyak hal dapat dilakukan dalam linked list, seperti push(insert), pop(delete). memahami konsep Singly Linked List dapat dibilang relatif mudah, namun pengaplikasian kodingnya perlu waktu untuk pemahaman. Saya Johanes Peter akan merangkum apa yang diajarkan di kelas besar pertemuan 3, yaitu mengenai koding linked list. Struct struct Data {     int value;     struct Data *next,*prev; }*head,*curr,*tail; Push tail (insert sebuah data di paling belakang) void push(int a) {     curr = (struct Data*)malloc(sizeof(struct Data));     curr->value = a;     if(head==NULL){         head = tail = curr;     }     else{         tail->next = curr;         curr->prev = tail;         tail = curr;     }     head->prev = tail->next = NULL; } Print isi dalam...
Post a Comment
Read more

HALF SEMESTER SUMMARY

Data Structures Summary Dear reader, due to the recent outbreak of the COVID-19 pandemic, we've all been forced to study at home. It is a challenge to keep track of the subject matter, so in this blog, I will be putting all my summary about what I've learned in this half semester from Data Structures. I've been thinking about the final project of making a pacman game using linked list... I can make a pacman game with 2d arrays, but a Linked List as a map ? It still leaves me in confusion ... For now I'll be studying more too be closer on approaching the final project Linked List II,  a linear data structure where each element is a separate object. Materials : - Circular Linked List - Circular Single Linked List - Doubly Linked List - Circular Doubly Linked List Circular Linked List Circular Single Linked List is a variation of linked list which its first element points to the last element and the last element points to the first element. In this list, there is...
Post a Comment
Read more