Skip to main content

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

Heap Applications:
- Priority Queue 
  - Selection Algorithms
  - Dijkstra's Algorithm (finding shortest path in graph)
  - Prim Algorithm (finding minimum spanning tree)
- Heap Sort


We can also imply heap into arrays such as :
Formula (x) stands for a node's position :
Parent(x)=x/2
Left Child(x)=2*x
Right Child(x)=2*x+1



UpHeap, is a process that swaps values between current node and it's parents while it doesn't satisfy it's heap's property(min/max heap).

Insertion in Min Heap

UpHeap

Deletion in Min Heap
Delete Node 7
Replace 7 with the last element
UpHeap


Insertion and deletion in max heap have the same algortihm, the difference is in it's comparator (min/max heap)



Min-Max Heap is a complete binary tree which implements both min and max heap


The smallesst element is located at the root, 
the largest element is located in one of the root's child (right/left) 
Upheap min-max heap
  • If new node is on a min level
    • if new node's parent is smaller than it, upheapmax from its parent
    • Else upheapmin from the new node
  • If the new nod is on a max level
    • if new node's parent is larger than it then swap their value and upheapmin from its pareng
    • else upheapmax from the new node
Upheapmin in upheap min-max heap
Compare current node's value with its grand parent's value. While current node's value is smaller than it's grandparent's value, swap their values.
Upheapmax in upheap min-max heap
Compare current node's value with its grand parent's value. While current node's value is larger than it's grandparent's value, swap their values


min max heap insert value 50

Upheapmin, 50 is larger than its parent(28), upheadmax
Upheadmax, 50 is larger than its grand parent(35) so they swap value

Deletion in min max heap
  • Replaceroot with the last element in heap
  • decrease the number of element in heap
  • downheapmin from root
Deletion  of the largest element
  • Replace either left or right child of rood (larger one) with the last element in heap
  • Decrease the number of element in heap
  • Down heapmax from the node

Downheap min/max in min-max heap
The procedure for deleting the root from the heap (effectively extracting the maximum element in a max-heap or the minimum element in a min-heap) and restoring the properties is called down-heap.
•Downheapmin
•Let m is the smallest element in current node’s children and grandchildren (if any).
•If m is grandchildren of current node then
•If m is smaller than current node then
•Swap their value
•If m is larger than its parent then swap their value
•Continue downheapmin from m
•If m is children of current node then
•If m is smaller than current node then
•Swap their value
•Downheapmax is the same except the comparators is reversed.

Min Max Heap delete Max
Replace The value with the last node

Downheapmax
Downheapmax
because 14 parents is larger than 14., swap
done

Tries is an ordered tree data structure that is used to store an associative array (usually strings)
Tries Example
We can see that this tree holds associative data between strings
  • ALGO
  • API
  • BOM
  • BOSAN
  • BOR


Those are the material I learned from data structures at 12/05/2020 (dd/mm/yyyy), sorry if there are mistakes made in this summary. thanks for reading :)









Pertemuan ke-(?),  AVL Tree 
Materi :
- Konsep AVL TREE
- Konsep-konsep Search, Insertion dan Deletion


AVL TREE
AVL Tree adalah sebuah "Binary Search Tree tahap berikut", dengan kata lain, AVL Tree adalah pematangan  dari konsep Binary Search Tree. AVL Tree dalam penempatan datanya akan terlihat persis sama seperti Binary Tree, namun pada saat penempatan data, AVL Tree melakukan langkah merapikan pohon, yang tidak dilakukan pada Binary Tree, sehingga data lebih efisien di AVL Tree. AVL Tree memiliki perbedaan tinggi maksimal 1 antara subtree kiri dan subtree kanan, bila perbedaan tinggi melewati 1, artinya sudah tidak seimbang dan akan dilakukan penyeimbangan. Hal ini dilakukan untuk mencegah sebuah situasi yang tidak baik yang bisa terjadi pada Binary Tree yaitu Skewed Tree.




















AVL TREE : INSERTION
Insertion pada AVL Tree sama seperti Binary Tree (Apabila lebih besar ke kanan, lebih kecil ke kiri) kecuali AVL Tree memiliki Balance(Untuk mencegah Skewed Tree). Balance ini akan di sesudah insertion biasa seperti Binary Tree dilakukan. Bila tidak balance, akan diperbaiki agar balance.

Balance tersebut diperbaiki dengan teknik Rotation
- Single Rotation

- Double Rotation
AVL TREE : DELETION
Deletion di AVL Tree juga sama seperti Deletion pada Binary Search Tree, namun seperti teknik lainnya pada AVL Tree, konsep Balance adalah yang membedakan.



Sekian yang saya pelajari hari ini, maaf bila ada kesalahan kata dan terima kasih atas waktunya. 

REFERENSI
- VIDCON kelas besar data structures Binus
- PPT BINUS





//RAND()SUPERMARKET

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
#include<windows.h>
void clear(){
system("cls");
}
void delay(int second){
int milsec = 1000 * second;
clock_t startTime = clock();
while(clock() < (startTime + milsec));
}
struct item{
char name[31];
int qty;
int price;
struct item *next,*prev;
}*head,*tail,*curr,*curr2;
struct item *news(char name[],int qty){
struct item *temp=(struct item*)malloc(sizeof(struct item));
temp->qty=qty;
temp->price=rand()%100000+1;
strcpy(temp->name,name);
return temp;
}
int countlist(){
curr=head;
int flag=0;
while(curr!=NULL){
flag++;
curr=curr->next;
}
return flag;
}
void drop(int x){
if(x<=countlist()){
if(head==tail){
head=tail=curr=NULL;
}
else if(x==1){
curr=head->next;
free(head);
head=curr;
head->prev=NULL;
}
else if(x==countlist()){
curr=tail->prev;
free(tail);
tail=curr;
tail->next=NULL;
}
else{
curr=head;
for(int i=0;i<x-1;i++){
curr=curr->next;
}
curr->next->prev=curr->prev;
curr->prev->next=curr->next;
free(curr);
}
}
}
bool deletion(char name[]){
curr=head;
for(int i=1;curr!=NULL;i++){
if(strcmpi(name,curr->name)==0){
drop(i);
return true;
}
curr=curr->next;
}
return false;
}
void push(char name[],int qty){
if(head==NULL){
head=news(name,qty);
head->next=NULL;
head->prev=NULL;
tail=head;
}
else {
curr=news(name,qty);
if(strcmp(name,head->name)<0){
head->prev=curr;
curr->next=head;
curr->prev=NULL;
head=curr;
}
else if(strcmp(name,tail->name)>0){
tail->next=curr;
curr->prev=tail;
curr->next=NULL;
tail=curr;
}
else{
curr2=head;
while(curr2->next!=tail&&strcmp(name,curr2->name)>0){
curr2=curr2->next;
}
curr->next=curr2->next;
curr->prev=curr2;
curr2->next->prev=curr;
curr2->next=curr;
}

}
}
void view(){
curr=head;
printf(" ______________________________________________________\n");
printf("| No.  | Item Name                      | qty | Price  |\n");
printf("+======================================================+\n");
for(int i=0;curr!=NULL;i++){
printf("| ");
printf("%d.",i+1);
if(i+1<10){
printf("  ");
}
else if(i+1<100){
printf(" ");
}
printf(" | ");
printf("%s",curr->name);
int len=strlen(curr->name);
for(int t=0;t<30-len;t++){
printf(" ");
}
printf(" | ");
printf("%d",curr->qty);
if(curr->qty>99){

}
else if(curr->qty>9){
printf(" ");
}
else printf("  ");
printf(" | ");
printf("%d",curr->price);
if(curr->price<10){
printf("    ");
}
else if(curr->price<100){
printf("   ");
}
else if(curr->price<1000){
printf("   ");
}
else if(curr->price<10000){
printf("  ");
}
else if(curr->price<100000){
printf(" ");
}
else printf("");
printf(" |\n");
curr=curr->next;
}
printf("+======================================================+\n");
}
bool qtyplus(char name[31],int qty){
curr=head;
while(curr!=NULL){
if(strcmpi(name,curr->name)==0){
curr->qty=curr->qty+qty;
printf("Item already existed...\nUpdating existing item's Qty instead...\n");
if(curr->qty>100){
curr->qty=100;
printf("Uhhh... Qty cant be over 100...\nSorry pal..\n");
}
return false;
}
curr=curr->next;
}
return true;
}

bool qtyupdate(char name[31],int qty){
curr=head;
while(curr!=NULL){
if(strcmpi(name,curr->name)==0){
curr->qty=qty;
return true;
}
curr=curr->next;
}
return false;
}
int keypress(){
int benar=0;
while(benar==0){
int hit = kbhit();
int ch;
if (hit){
ch = getch();
benar=1;
return ch;
}
}
}
int main(){
srand(time(NULL));
int menu=0;
int mulai=0;
printf("Welcome, shop will you ?\n");
printf("Press any key to continue...?\n");
keypress();
while(menu!=5){
clear();
printf("Welcome to random shop...\n");
printf("1. Add item\n");
printf("2. View items\n");
printf("3. Delete an item\n");
printf("4. Change item qty\n");
printf("5. Check Out\n");
char input[20]={0};
do{
printf(">>");
if(mulai==1)getchar();
mulai=1;
scanf("%[^\n]",&input);
}while(strcmp(input,"1")!=0&&strcmp(input,"2")!=0&&strcmp(input,"3")!=0&&strcmp(input,"4")!=0&&strcmp(input,"5")!=0);
menu=input[0]-48;
if(menu==1){
clear();
char inp[100]={0};
int qty=0;
do{
printf("If you input an existing item (Not case sensitive),\nit will add qty into the existing one...\n");
printf("(Word length : 5-30)>>");
getchar();
scanf("%[^\n]",&inp);
}while(strlen(inp)>30||strlen(inp)<5);
while(qty<1||qty>100){
printf("(QTY (MIN 1, MAX 100)))>>");
scanf("%d",&qty);
}
if(qtyplus(inp,qty)){
push(inp,qty);
printf("Add Success !\n");
}
else{


printf("Item succesfully updated...\n");
printf("Press any key to continue...\n");
keypress();
}
}
if(menu==2){
clear();
if(countlist()>0){

view();
}
else printf("no data....\n");
printf("Press any key to continue...\n");
keypress();
}
if(menu==3){
clear();
if(countlist()>0){
view();
char inp[100]={0};
int qty=0;
do{
printf("Which one do you want to delete(Not case sensitive)?\n");
printf("(Word length : 5-30)>>");
getchar();
scanf("%[^\n]",&inp);
}while(strlen(inp)>30||strlen(inp)<5);
if(deletion(inp)){
printf("Delete Succes...\n");
}
else {
printf("No such data...\n");

}
}
else printf("No data to delete...\n");
printf("Press any key to continue...");
keypress();
}
if(menu==4){
clear();
if(countlist()>0){
view();
char inp[100]={0};
int qty=0;
do{
printf("Which one do you want to update(Not case sensitive)?\n");
printf("(Word length : 5-30)>>");
getchar();
scanf("%[^\n]",&inp);
}while(strlen(inp)>30||strlen(inp)<5);
while(qty<1||qty>100){
printf("(QTY (MIN 1, MAX 100)))>>");
scanf("%d",&qty);
}
if(qtyupdate(inp,qty)){
printf("Update success !\n");
}
else{
printf("No such item exist...\n");
}
}
else printf("No data to update....");
printf("Press any key to continue...");
keypress();
}
}
}

Comments

Post a Comment

Popular posts from this blog

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