Linked list - 004

-

Linked List

Rangkuman tanggal 10 Maret 2020

Materi GLSC 17 Maret 2020 (Binary Search Tree)



Binary Search Tree

Setelah kemarin kita belajar tentang tree, sekarang kita belajar tentang binary search tree. apa itu binary search tree?

Binary search tree adalah data structure mirip seperti tree, namun ini adalah versi sorted nya. jadi data yang ada di dalam BST ini adalah data yang sudah di sort.

lalu bagaimana konsep sort nya?
pertama kita punya yang nama nya Root. biasanya data pertama yang masuk akan menjadi Rootnya.

jadi konsepnya adalah (ini berlaku untuk insertion)

1. Bandingkan data yang ingin dimasukkan dengan ROOT / Parent.
2. Jika data yang lebih kecil dari ROOT / Parent, data akan masuk ke sebelah kiri.
2.5. Jika data yang lebih besar dari ROOT / Parent, data akan masuk ke sebelah kanan.

proses ini akan di ulang terus sampai data berada di paling bawah atau menjadi leaf.







Lalu untuk Deletion konsepnya adalah :

Lakukan pencarian, dengan konsep insertion (jika data lebih kecil dari Root/parents ke sebelah kiri, dan jika lebih besar cari ke sebelah kanan). lalu setelah ketemu hapus node nya.

ada beberapa kasus dalam masalah deletion ini.

Kasus 1 : bila yang dihapus adalah node leaf.


Di kasus ini, yang ingin dihapus adalah data 21, dimana ini adalah leaf atau data yang paling bawah.

Lakukan pencarian, lalu delete node nya.

Kasus 2 : Bila yang dihapus adalah parent.


Di kasus ini, data 35 yang berupa parent akan dihapus, lalu bagaimana cara menentukan node pengganti nya?

Biasanya orang mempunyai 2 metode, 
Pilih node cabang kiri lalu cari data yang paling besar
Atau
Pilih node cabang kanan lalu cari data yang paling kecil.

Di gambar, kita menggunakan metode pertama.

Kasus 3 : Bila yang dihapus adalah rootnya.


Di kasus ini, yang dihapus adalah root nya, sama seperti kasus 2, pilih dari kiri yang paling besar, Atau dari kanan yang paling kecil.
Di gambar kita memilih kiri yang paling besar.

sekian dari saya, dan maaf bila ada kesalahan karena saya juga masih belajar :) .

Comments

Post a Comment

Popular posts from this blog

Source code untuk Tugas GSLC

-
Source code untuk Tugas GSLC Aplikasi untuk jual beli barang Nama : Leander Ignacio Jose Antonius NIM : 2301922285 #include<stdio.h> #include<string.h> #include<stdlib.h> struct item { char namabarang[20]; int hargabarang; int quantitybarang; struct item *next; struct item *previous; }*head=NULL, *tail=NULL; void Printitem() { if(head==NULL&&tail==NULL) { printf("No Data\n"); } else { struct item *curr=head; int nomor=1; printf("==========================================\n"); while(curr!=NULL) { printf("Data %d\n",nomor); printf("Nama barang : %s\n",curr->namabarang); printf("Harga barang : %d\n",curr->hargabarang); printf("Jumlah barang : %d\n",curr->quantitybarang); curr=curr->next; printf("==========================================\n"); nomor++; } nomor=1; } } void Updateitem() { ...
Read more

Heaps and tries

-
Image
Video conference 12-5-2020 Heaps and Tries Heaps adalah sebuah binary tree yang isinya (nodenya) dapat direpresentasikan dalam sebuah array. cara memasukkan datanya adalah masukkan data dari array secara berurutan dari index 1-10 data pertamanya sebagai root, data ke 2 dan 3 sebagai left child dan right child, dan seterusnya. cara menghitung index x sebagai index menghitung index parent : x/2 menghitung index left child : 2*x menghitung index right child : (2*x)+1 misal kita mengambil node 18 yang memiliki index 4 (dari gambar di atas) untuk menghitung index parent (node 15) : 4/2=2 untuk menghitung index left child : 4*2=8 untuk menghitung index right child : (4*2)+1=9 Min heap dan max heap Min heap : setiap node pasti lebih kecil dari pada child node. angka terkecil yang ada di min heap pasti ada di rootnya. Insertion di Min heap ada 2 cara untuk insert di min heap cara 1 : Upheap Masukkan node seperti biasa, lalu bandingkan dengan node di atas...
Read more

Linked list - 002

-
Image
Linked list Rangkuman tanggal 3 maret 2020 Jadi di post ini saya akan merangkum materi yang disampaikan hari ini, dan juga materi yang ada di minggu pertama. Rangkuman minggu pertama Mulai dari cara mendeclare struct untuk linked list dan cara menambahkan node meng-set value ke node yang sudah dibuat dan meng-set penunjuk dari node ke node lain dengan ini kedua node yang baru saja kita buat sudah terhubung, dan jika kita print kedua node tadi kita bisa mengeprint node dengan cara printf("%d",node->value); printf("%d",node->next->value); Namun jika kita ingin membuat banyak node, akan lebih mudah jika kita membuat fungsi untuk membuat node fungsi ini untuk membuat node baru,cara menggunakannya adalah : struct tnode* node=node_maker(1); struct tnode* node1=node_maker(2); dan secara otomatis akan terbuat (node) yang berisi 1 dan (node1) yang terisi 2 namun disini kita tetap harus memberi tahu bahwa nod...
Read more