penjelasan lebih jauh tentang heap n deap lalu penjelasan dekilas tentang leftist, tries, hashing, dan btree

pert 10
heap n deap
ciri:
heap = complete binary tree
min - tree ascending
max - tree descending

index parent =  index child /2
child left = index parent * 2
child right = index parent * 2+1
(upheap = ngecek parent, downhead = ngecek child)
fungsi:
buat ngebantu cari nilai max n min

implementasi:
index dari 1

insertion:
min heap = node di tempat index terakhir, banding dgn parent ,parent lbih besar dari child tukar, sampai parent lbih kecil dari child.

max heap = node di tempat index terakhir, banding dgn parent ,parent lbih kecil dari child tukar, sampai parent lbih besar dari child.

deletion:
root di hapus (cuma bisa root yang di hapus), langsung di tukar dengan index terakhir lalu tukar dengan child bila child lbh kecil sampai tree sesuai urutan nilainya antara parent node & child .

min - max heap = gabungan min & max heap
ciri :
root berawal dari min lalu childnya max lalu min lagi lalu max lagi dan seterusnya

insertion:
kalau masuk di level min banding dengan parent, kalau parent lbih kecil swap , terus banding dengan granparent kalau grand parent (sama - sama level min) lbih besar ga swap

kalau masuk di level max banding dengan parent, kalau parent lbih besar swap , terus banding dengan granparent kalau grand parent (sama - sama level max) lbih kecil ga swap

deletion
min = root hapus , index terakhir gantiin ,trus root baru bandingin sama grandchild ke satunya (sama - sama level min) cari sama yang paling kecil di level tsb , lalu bila ada yg lbih kecil daripada root maka tukar dengan root node yg paling kecil
bila masih 1 level di bawahnya lagi maka banding dengan childnya kalo lebih kecil childnya maka swap

max = pilih yang paling besar di level max teratas, lalu hapus, lalu ganti dengan index terakhir, terus index yang di ganti itu banding dengan grandchildnya lalu bila ada yg lbih besar daripada node maka tukar dengan node yg paling besar
bila masih 1 level di bawahnya lagi maka banding dengan childnya kalo lebih besar childnya maka swap

deap (dable ended heap)
root selalu null
sebelah kanan min, kiri max
pratner = kalau node di tumpuk ada di titik yang sama
level min = index - index/2
level max = index + index/2

kalau partner kosong maka partner jadi parent dari partner seharusnya
level min =(index - index/2) /2
level max = (index + index/2) /2

insertion deap :
node masuk di index trakhir, lalu banding dengan partner, kalo partner lebih besar maka swap , lalu cek dengan parent kalau ga cocok maka swap

deletion
min = seperti heap lalu di cek dengan partner kalo lebih besar maka swap
max = seperti heap lalu di cek dengan partner kalo lebih kecil maka swap


Btree :
ciri -> orde (m) , key(m-1),
node sejumlah m
insertion:
masuk ke key yang sudah ada, kalau node penuh
deletion:
tandai,



leftist tree , tries , hashing

leftist tree :
s(kiri ) >= s(kanan)
penjelasan lebih jauh di lihat dapat di lihat di:
certifiedshare.blogspot.com
soundia

tries (previx tree):
auto correct di hp

hashing :
(hashing table)
collision(2 data yang sama) -> linear probing (baca slide)
   -> chaining (linked list)

                                                                   

b tree & heap n deap

->B- tree

> b-tree mempunyai beberapa sifat sebagai berikut
- setiap node mempunyai jumlah node dalam tree yang sempurna
- mempunyai ciri yang sama deperti 2-3 tree
- setiap node paling tidak mempunyai 2 child
- bila dalam 1 node mempunyai jumlah nilai sebanyak 'i' maka jumlah anaknya 'i+1'
- semua nilai data terurut

insert
- cara memasukan nilai yang baru tergantung dalam nilai yang i dimasukan itu sendiri
- bisa dimsukan dalam node diatas atau child


delete
- cara menghilangkan nilai tergantung dalam nilai yang i dimasukan itu sendiri
- dalam mendelete nilai bisa mempengaruhi seluruh struktur tree itu sendiri


->heap & deap

> heap & deap adalah suatu tree yang mempunyai struktur yang sangat bergantung pada urutan nilai dalam nodenya
>min heap = nilai node paling kecil d atas
>max heap = nilai node paling besar di atas
>min-max heap = mempunyai nilai ascending di 1 sisi dan descending di sisi lainnya
>piq =  fungsi buat ngambil plg atas (min)
>maxim = fungsi buat ngambil plg atas (max)

pembelajaran sesi 8 RBT dan 2-3 tree

-> Red Black Tree
ciri2:
> dalam sebuah rbt setiap nodenya mempunyai warna  yaitu warna merah atau  hitam
> bagian root dalam sebuah rbt  selalu berwarna hitam
> dalam rbt juga mempunyai 2 fungsi yaitu insert dan delete
> dalam rbt juga ada yang namanya external nodenya, yaitu node yang selalu ada di paling akhir yang berwarna black.
> kalau parent (merah) maka anak2nya hitam.
> parent(merah) tidak boleh ketemu anak(merah)

a>dalam fungsi insert di rbt ada beberapa rules seperti:
- setiap node yang baru warnanya merah
- kalau paman (merah) maka parent dan paman di buat jadi warna hitam, lalu grand parent jadi merah
- kalau node pertama selalu merah tapi karena root langsung di ubah ke  hitam
- kalau paman (hitam) maka lakukan rotasi (double / singgle) setelah itu parentnya jadi warna hitamda kedua warna anaknya jadi merah.
note :

double akan di gunakan kalau ketemu bentuk node:
o
 \
  o
 /
o

single
o
 \
  o
     \
      o

b>dalam fungsi delete di rbt ada beberapa rules seperti:
- parent (merah) kalau punya child maka di ambil penggantinya dulu dari child sebelah kiri yang punya nilai terbesar atau child sebelah kanan yang punya nilai terkecil.
- kalau parent (black) dan child (red)  kalau parent delete maka child  akan naik dan jadi hitam
- kalau parent (merah) dan child (hitam) kalau parent delete child naik dan tdak berubah warna
- kalau yang di hapus berwarna hitam maka dilihat dulu dari sibingnya:
  :- jika sibling merah maka tukar warna parent dan sibling dan rotasi dari(doube atau singgle) parent (warna menempel pada node)
  :- jika sibling dan 2 anak nya hitam maka ubah warna sibling jadi merah

->2-3 tree
> adalah suatu tree yang dalam satu nodenya mengandung 1 atau 2 nilai
> kalau dalam 1 node mengandung 1 nilai maka anaknya ada 2 node sedangkan kalau mengandung 2 nilai maka anaknya ada 3 node
> dalam 2-3 tree juga mempunyai 2 fungsi yaitu insert dan delete

TREE

TREE di bagi menjadi banyak jenis tetapi saya kali ini saya ajan membahas binary tree dan binary search tree, yang membedakan antara keduanya adalah kalau binary tree posisi penempatannya bebas sedangkan binary search tree punya beberapa peraturan sendiri.

Binary search tree yang saya pelajari mempunyai peraturan sebagai berikut  :

->Binary search tree punya minimal left dan right, tetapi bisa juga di tammbah parent & child(akan saya jelaskan lebih lanjut di kesempatan lainya).


struct MLM{
char nama[25];
int usia;
int level;
struct MLM *left, *right, *parent;
}*root;


-> Binary search tree mempunyai peraturan bahwa sebelah LEFT dari CURR nilainya lebih kecil sedangkan RIGHT nilainnya harus lebih besar dari curr


void push(struct MLM **curr, char nama[], int usia, int level){
if(*curr == NULL){
(*curr) = (struct MLM*)malloc(sizeof(struct MLM));
// Presendence (kurung)
strcpy((*curr)->nama, nama);
(*curr)->usia = usia;
(*curr)->level = level;
(*curr)->left = (*curr)->right = NULL;
}else{
if(usia < (*curr)->usia){
if(*curr != NULL){
(*curr)->left->parent = (*curr);
}
push(&(*curr)->left,nama,usia,level+1);
}else if(usia > (*curr)->usia){
if((*curr) != NULL){
(*curr)->right->parent = (*curr);
}
push(&(*curr)->right,nama,usia,level+1);
}else{
printf("Angka %d sudah ada\n",usia);
}
}
}

->Lalu penampilan printnya bisa di gunakan postfix, infix atau prefix


void preorder(struct MLM *curr){
if(curr == NULL){
//printf("Maaf, kosong.. coba lagi besok.\n");
//getchar();
}else{
printf("%s %d %d\n",curr->nama, curr->usia, curr->level);
preorder(curr->left);
preorder(curr->right);
}
}

void inorder(struct MLM *curr){
if(curr == NULL){
//printf("Maaf, kosong.. coba lagi besok.\n");
//getchar();
}else{
inorder(curr->left);
printf("%s %d %d\n",curr->nama, curr->usia, curr->level);
inorder(curr->right);
}
}

void postorder(struct MLM *curr){
if(curr == NULL){
//printf("Maaf, kosong.. coba lagi besok.\n");
//getchar();
}else{
postorder(curr->left);
postorder(curr->right);
printf("%s %d %d\n",curr->nama, curr->usia, curr->level);
}
}

inilah yang saya pelajari dari pertemuan hari ini terima kasih

binary tree

saya akan menjelaskan tentang jenis2 binary tree;

Ada 3 jenis tree yaitu :
skewed tree (masing2 punya satu anak di tap turunannya)
perfect tree (masing2 punya 2 anak di setiap turunannya)
complete tree(sebuah bynari tree yang tidak sempurna)

dalam pengaplikasiannya tree juga bisa digunakan dalam oprasi perhitungan seperti:
infix(perhitungan biasa)
=> A + B x C
prefix(perhitungan yang memposisikan tanda oprasi hitungan di depan angka)
=> + A x B C
postfix(perhitungan yang memposisikan tanda oprasi hitungan di belakang angka)
=>A B C x +

linked list part 3

link list
: singgle(next), double(next, prev), multi(left, right, parent, child);
implementasi
: stack(enstack(nambah), destack(ngurang)) , queue(front(depan) , rear(belakang)) ;

berikut saya berikan contoh kodingan program push dalam link list yang nantinya bisa menentukan pisisi pushnya secara manual:

int jumlahData=0

void push(char vegeName[], int qty, int posisi)
{
struct grocery *curr=(struct grocery*)malloc(sizeof(struct grocery));
strcpy(curr->vegeName,vegeName);
curr->qty=qty;

if(head==NULL)
{
head=tail=curr;
tail->next=NULL;
head->prev=NULL;
}
else
{
if(posisi==1)
{

curr->next=head;
head->prev=curr;
head=curr;
head->prev=NULL;
}
else if(posisi==jumlahData+1)
{
tail->next=curr;
curr->prev=tail;
tail=curr;
tail->next=NULL;
}
else
{
temp=head;
int i=1;
while(temp!=tail && i!=posisi-1)
{
temp=temp->next;
i++;
}
curr->next=temp->next;
temp->next->prev=curr;
temp->next=curr;
curr->prev=temp;
}
}
jumlahData++;
}



berikut adalah kodingan program yang inngin menghapus (pop) suatu spesifik data:


void pop(char vegeName[])
{
if(head==NULL)
{
printf("not found");
}
else
{
if(strcmpi(head->vegeName,vegeName)==0)
{
if(head==tail)
{
free(head);
head=tail=NULL;
}
else
{
head=head->next;
free(head->prev);
head->prev=NULL;
}
}
else if(strcmpi(tail->vegeName,vegeName)==0)
{

tail=tail->prev;
free(tail->next);
tail->next=NULL;
}
else
{
temp=head;
int isFound=0;
while(temp!=NULL )
{
if(strcmpi(vegeName,temp->vegeName)==0)
{
isFound=1;
break;
}
temp=temp->next;
}
if(isFound==1)
{
temp->next->prev=temp->prev;
temp->prev->next=temp->next;
free(temp);
}
else
{
printf("\nnot found ");
getch();
}
}
}
}

link list part 2

QUEUE:
adalah sebuah system linked list system yang  menganut system FIFO (first in first out);
queue menggunakan system pushHead dengan popTail selain itu bisa juga menggunakan system pushTail dengan  popHead;
queue menggunakan system priority queue jadi dalam sytem ini kita bisa langsung mensorting node yang di masukan , contoh kodingnya adalah:

void priority(char nama[], int usia){
struct Facebook *curr = (struct Facebook*) malloc(sizeof(struct Facebook));
strcpy(curr->nama,nama);
curr->usia = usia;
if(head == NULL){
head = tail = curr;
head->prev = NULL;
tail->next = NULL;
}else{
if(curr->usia > head->usia){
//pushHead
curr->next = head;
head->prev = curr;
head = curr;
head->prev = NULL;
}else if(curr->usia < tail->usia  ){
//pushTail
tail->next = curr;
curr->prev = tail;
tail = curr;
tail->next = NULL;
}else{
//push mid
struct Facebook *temp=head;
while(temp->next->usia > curr->usia){
temp = temp->next;
}
curr->next = temp->next;
temp->next->prev = curr;
temp->next = curr;
curr->prev = temp;
}
}
}

jadi secara logika bisa disimpulkan sebagai berikut:

//if(strcmp(curr->nama,head->nama) < 0){
// //push head
//}else if(strcmp(curr->nama,tail->nama) > 0){
// //push tail
//}else{
// //push mid

//}

STACK:

adalah sebuah system linked list system yang  menganut system LIFO (last in first out);
stack menggunakan system pushHead dengan popHead selain itu bisa juga menggunakan system pushTail dengan  popTail;

DOUBLE LINKED LIST:
adalah system linked list yang cara menyambungnya mempunyai 2 cara dengan next dan prev;
ini contoh kodingnya:


struct Facebook{
char nama[25];
int usia;
struct Facebook *next,*prev;
}*head,*tail , *curr;