Month: May 2016

Heap, Tries and Hashing

Heap adalah sebuah Complete Binary Tree yang memenuhi persyaratan heap. Heap terdiri dari dua jenis, yaitu max heap, min heap dan ada pula min-max heap.

Tries adalah struktur datayang tersusun yang digunakan untuk menyimpan array yang bersifat asosiatif. Root nya dibuat 0 untuk memudahkan proses pencarian menggunakan formula search nantinya.

Hashing adalah transformasi dari string karakter menjadi nilai panjang biasanya lebih pendek atau kunci yang mewakili string asli. Fungsi dari Hash adalah sebagai berikut:

1. Divison : dengan modulus ( h(x) = x Mod M)
2. Mid-square : dengan mengkuadratkan setelah itu ambil digit tengah hasil kuadrat (h(k) = s)
3. Folding : dengan cara mememisahkan angka menjadi dua bagian, lalu jumlahkan angka tersebut. Ambil beberpa digit dari halsilnya.

 

Red-Black Tree

A self-balancing tree like AVL Tree

Every node has a black and red circle with the root having a black circle. Any external nodes are colored black and every red node can’t have red node as its children or else it is unbalanced.

Insertion:

Every new node is red.

If (1): parent and uncle of new node is red, change parent’s or uncle’s color to black and grandparent’s color to red.

If(2): parent of the new node is red and uncle is black, do rotation (L – L, R – R, L -R or R – L).

Deletion:

If(1): the node being deleted has a red-colored parent and a black-colored  child (excuse the racism), then the child can be replaced directly.

If(2): the node being deleted has a black-colored parent (wow, again with the racism) and a red-colored child, the child could replace the node but it has to change color from red to black (my god the racism on this post is off the roof).

 

2-3 Tree

Tree where the node has one element of data and two children or two element of data and three children.

Insertion:

If the leaf has 2 nodes, insert the new data until the leaf has 3 nodes.

If the leaf has 3 nodes, push the middle data between A and B to the parent. Then, split the 2 data left to become 2-node. Repeat until parent is correct.

Deletion:

If the leaf has 3 nodes, then delete the data so it becomes 2 nodes.

If the leaf has 2 nodes, then:

If parents has 3 nodes, take one of the data, if the sibling has 3 nodes, then push the data to parent. If sibling has 2 nodes, make a parent to have 2 node and combine the node we have now with the sibling.

If parent has 2 nodes and sibling has 3 nodes, then take one of the data from the parent and push a data from the sibling to its parent. Then combine both of the parent and the sibling.

Last time we learned about: Binary tree and Binary Search Tree

New topic is BST  (Balance)

Most common Balanced BST is AVL.

AVL is founded by Georgy Adelson-Velsky and Evgenii Landis in 1962. It is the first self-balancing binary search tree. In Binary search tree there is a height. empty sub-tree = 0 and leaf = 1. If the height is > 1, then the tree is overloaded, and needs balancing. There is two condition on balancing tree:

A key word from the BULE MALAYSIA:

If L – L / R -R = Cut the middle part, push it to the top, then balance it.

If L – R / R – L = Child becomes parent, parent becomes child