hansadvent

RED BLACK TREE

Red Black Tree bisa disebut sebagai Binary Search Tree yang mempunyai fungsi yang sama.

Ciri-ciri dari Red Black Tree adalah:

1. Setiap node mempunyai warna yang antara lain adalah merah atau hitam

2. Root (external node) selalu berwarna hitam

3. Leaf atau akar dari root berwarna hitam

4. Jika suatu node berwarna merah, maka anak-anaknya berwarna hitam

5. Node yang baru dimasukkan selalu berwarna merah

Insertion

Ada beberap violation yang dapat terjadi dalam insertion:

1. Jika parent dan uncle dari new node adalah merah, maka violation dapat dihindari dengan cara merubah wanr dari parent dan uncle menjadi hitam

• Jika parent dari new node adalah merah dan unclenya adalah hitam (external node termasuk warna hitam), lalu new node lebih kecil daripada nilai dari parentnya, maka yang harus dilakukan adalah melakukan single rotate seperti pada gambar

• Jika parent dari new node adalah merah dan unclenya adalah hitam (external node termasuk warna hitam), lalu new node lebih besar daripada nilai dari parentnya, maka yang harus dilakukan adalah melakukan double rotate seperti pada gambar

Deletion

Deletion pada Red Black Tree umumnya sama seperti pada BST

Dalam Deletion pada Red Black Tree, ada dua hal yang dapat terjadi pada umumnya

• Jika node yang ingin di-delete adalah node merah, maka dapat langsung dihapus
• Jika node yang ingin di-delete adalah node hitam, maka dapat terjadi double black

Pada gambar dibawah, terjadi double black pada node a. Jika saudara dari a adalah merah, maka terjadi single rotatation dan X menjadi warna merah.

Pada gambar di bawah, jika a adalah double black dan Y beserta anak-anaknya adalah hitam juga, maka Y akan menjadi warna merah dan double black berpindah kepada parent dari a dan Y.

Pada gambar di bawah, a adalah double black, saudara dari a (Z) adalah hitam dan mempunyai anak yang berwarna merah. Pada kondisi tersebut, harus dilakukan double rotation.

2-3 Tree

2-3 Tree:

• Setiap internal node merupakan 2 node yang punya 1 data dan 2 anak, atau 3 node yang punya 2 data dan 3 anak
• Semua leaf harus berada dalam level yang sama
• Semua node ter organisir seperti halnya dengan BST

Insertion

• Jika tree kosong, insert new node pada letaknya
• Jika tree sudah terisi satu value, maka buat node barunya di sebelah value dalam node tersebut
• Jika tree sudah terdapat 2 value, dan masih ingin diletakkan node baru, maka value tengah dari ketiga tersebut akan split

 Binary Search Tree

Binary Search Tree adalah tree yang dipergunakan untuk memudahkan dan mempercepat komputer dalam melakukan perncarian suatu data.

Searching

Pencarian (Searching) dimulai dari rootnya (di gambar adalah angka 50).

Jika angka yang dicari belum ditemukan, maka pencarian akan dilanjutkan, jika angka yang dicari lebih kecil dari root, maka pencarian akan ke sebelah kiri root, jika sebaliknya maka akan dicari ke sebelah kanan root. Begitu seterusnya samapi ditemukan angka yang dicari.

Misal jika angka yang dicari adalah 23, maka pencarian akan dimulai dari:

• 23 != root, maka 23 dibandingkan dengan root
• 23 < 50, maka pencarian dilanjutkan ke sebelah kiri
• 23 != 17, maka 23 dibandingkan dengan 17
• 23 > 17, maka pencarian dilanjutkan ke sebelah kanan
• 23 == 23, maka pencarian telah berhasil dan selesai

Insertion

Metode Insert

Misal angka yang ingin kita insert adalah 35, maka:

• Insertion dimulai dari root, 35 > 30 maka akan dilanjutkan ke sebelah kanan

• Setelah itu, 35 dibandingkan dengan 37 (35 < 37)

• Dilanjutkan ke angka 32 dengan cara yang sama (35 > 32). 35 akan dilanjutkan ke sebelah kanan 32 yang merupakan ujung dari tree (leaf)

• 35 kemudian di insert ke sebelah kanan angka 32

Stack

Stack adalah tumpukan objek yang di insert dan di remove dengan prinsip LIFO (Last in First out).

Pada stack, dikenal Top merupakan sebutan untuk item / elemen untuk menyimpan alamat paling atas dari suatu stack.

Jika TOP == NULL, maka berarti stack kosong.

Jika TOP == Max-1, berarti stack sudah full.

Ada beberapa operasi / fungsi dalam Stack:

• Push() : Menambah item ke tumpukan paling atas
• Pop()   : Menghapus / mengambil item dari tumpukan paling atas
• Top()  : Mengembalikan item paling atas dari stack

Queues

Queue sesuai namanya adalah kebalikan dari Stack.

Queue menggunakan prinsip FIFA (First in First out) dan dapat diimplementasikan dengan array atau Linked List.

• Front: Item / Elemen yang akan di remove terlebih dahulu (jika di pop(), akan yang pertama di remove)
• Rear : Tempat dimana item akan dimasukan pertama kali (jika di pop(), akan menjadi yang terakhir di remove)

Ada beberapa operasi / fungsi dalam Queues:

• Push() : Menambah item ke belakang barisan
• Pop()   : Menghapus / mengeluarkan item paling depan
• Front()  : Menunjukan item paling depan dari barisan

Infix, Prefix, Postfix

Dalam Struktur Data, ada 3 notasi operasi aritmatika, yaitu:

• Infix     : Operator yang ditulis di antara 2 operand
• Prefix   : Operator yang ditulis sebelum operand
• Postfix : Operator yang ditulis setelah operand

DFS & BFS

DFS (Depth-First-Search) mencari atau berjalan dalam struktur tree secara ke bawah (ke dalam) terlebih dahulu dan dapat diselesaikan dengan bantuan struktur data Stack.

BFS (Breadth-First-Search) mencari atau berjalan dalam struktur tree secara horizontal / menyamping terlebih dahulu dan dapat diselesaikan dengan banturan struktur data Queues.

Contoh-contoh Data Structures:

1. Arrays
2. Linked lists
3. Queues
4. Stacks
5. Binary Trees
6. Hash Tables

Queues

Sesuai dengan namanya, data struktur ini berbentuk seperti antrian.

Elemen yang pertama kali dimasukkan ke satu sisi (disebut rear), akan dikeluarkan terlebih dahulu sebelum yang lain di sisi yang lain (disebut front).

Stacks

Stack (tumpukan) bisa dibilang sebagai kebalikan dari Queues (antrian).

Data struktur ini menggunakan sistem LIFO (Last In First Out) / FILO (First In Last Out).

Jika ingin mengeluarkan yang pertama kali masuk, maka harus mengeluarkan dulu yang lain, begitu juga sebaliknya.

Binary Trees

Data struktur yang terdiri dari kumpulan elemen yang disebut Nodes yang masing-masing node mempunyai left pointer, right pointer, dan elemen data.

Array dan Linklist

Array dan Linklist dapat dibedakan berdasarkan sifat dan Memory allocationnya.

Array:

• Mempunyai elemen data dengan tipe data yang sama (Homogen)
• Static memory allocation
• Mempunyai index yang merupukan urutan data dalam array

Linked List:

• Berupa kumpulan node yang elemen datanya bersifat heterogen (tipe data bisa berbeda)
• Dynamic memory allocation
• Tidak mengenal index

Array merupakan kumpulan dari elemen data yang mirip (masing-masing data mempunyai tipe data yang sama untuk setiap array).

Ada beberapa operasi di Array:

• Traversal
• Insertion
• Searching
• Deletion
• Merging
• Sorting

Pointer adalah tipe data yang valuenya menunjuk kepada value yang tersimpan di dalam memori komputer menggunakan alamat.

2 operator yang paling penting dalam menggunakan tipe data pointer adalah:

1. & Address operator
2. * Dereferencing operator

Linked List adalah sebuah data structure yang elemennya (disebut sebagai node) bisa ditambahkan atau dihapus sesuai dengan keinginan.

Single Linked List hanya mengandung single link (bisa disebut juga hanya punya pointer next) secara satu arah.