DATA STRUCTURE 

Argaditya Rezhani F – 1901481661

BLACK RED TREE (RBT)

• Red black tree is a binary search tree that is self-balancing.
• AVL RBT is similar to, but different from her is her node has a color, between red or black.
• In RBT, always imagined that leaf have more children, but the node “is not visible directly. The node could be considered as external nodes or ‘dummy children’ of leaves. The use of dummy use of children is to facilitate the algorithms to operate on RBT. Color of dummy children always black.
• Rules on RBT:
1. Every node is either red or black.
2. Root should be black.
3. All external node or dummy children belonging black leaves.
4. If a node is red, then both her children definitely black. That is when a node is red, then his children should not be red.
• As usual BST, RBT can make the process of searching, insertion, and deletion.
• Insertion:
 The new Node in the insert is always red.
 Find the right position to put the new node, as in the usual BST.
 Check whether there is violation after insertion.
If the parent of a node is black, then there is no violation.
However, if the parent of a node is red, then there is violation (rule number 4).
 If there is a violation, then there should be changes made to the tree.
• Some cases may occur in violation:
 Assume that in the insert node named Q, its parent P, and a sibling of the parent S. If the parent does not have a sibling means S is considered black (dummy children always black).
 When S red, then replace the P and S to black, then the parent of P into the red.
 When S black, do rotation (single or double, depending on the situation). Rotate and change color to black and her child into the red.
• Examples of insertion at RBT:

• Deletion:
 Search will delete nodes, as in the usual BST.
 Check the condition happens and do deletion in accordance with the conditions.
• Conditions that allow:
 Assume that the delete node named her child M and C.
 When M red, then replace it with a C. In these conditions, C must have black as child of the red M may not be red as well.
 When C M black and red, then replace it with C and C was changed to black.
 When the M and C are both black, then replace M with C. Let us give C and its new position we deem named N (N position double colored black). Then consider the parent of N named P. Some possibilities are:
– When the uncle of N is red, the color exchange N and P, and rotate on P.
– When the uncle and nephews of N all black, change the color of his uncle so red.
– When the uncle of N black, and one of his nephew N red, then have to do rotation (single or double).
• Some examples deletion at RBT:

2-3 TREE

• 2-3 tree instead of a binary tree, because it could have 3 children.
• In a 2-3 tree, when its nodes have the children, then there are two possibilities, namely between the node has 2 children and 1 of data, or the node has 3 children and 2 data.
• Each internal node, the node is not a leaf, is a 2-node or 3-node.
 two-node means discount 1 data and 2 children (left and middle child).
 3-node means having 2 data and 3 children (left, middle, and right child).
• All data is always ordered, that is:
 In the 2-node, then left her child has a smaller value and its right child has a greater value.
 In the three-node, then left her child has a smaller value, its right child has a greater value, and her middle child has a value between her parents.
• All leaves there at the same level.
• SearchingSAT at 2-3 tree is similar to searching on a regular binary tree. When the smaller to the left, then to the right when it is smaller. However, his differences with the binary tree is when there is a 3-node. When the data we’re search is worth between 2 data on a 3-node, then we are not left or right, but to the middle of her child.
• Insertion:
 Find the right position to put a new node that would in the insert.
 After the meet, check whether the node 2-node or 3-node.
When the 2-node, then just enter the data, and the nodes directly into a 3-node.
When the 3-node, paste the data, and then move the data that is in the middle to the top, becoming its parent. Then for two of the remaining data, split into two different nodes, and the node into two-node.
 Repeat until it is recursive.

• Examples of insertion in the 2-3 tree:

• Deletion:
 Find the delete node wants. Suppose we want to delete the named key.
 As the BST, we have to look for leaf that could replace the key.
 When the 3-leaf node, then the delete key and then into 2-node.
 If leaf 2-node, there are two possibilities:
– When the parent-node 3, take one value from its parent. When the 3-node sibling, push one sibling value to the parent. When the 2-node sibling, parent change into a 2-node and then merge with a sibling.
– When the parent 2-node, three-node and sibling, take 1 value of parent and push one value from parent to sibling. If the 2-node sibling, merge with the parent.
 Repeat until it is recursive.

• Some examples deletion at 2-3 tree:

Binary Search Tree
Binary search tree (binary search tree, or BST) is a binary tree data structure that has properties as follows:
Each node has a value.
A total arrangement specified in this value.
Sub left tree of a node only contains a smaller value than the value of the node.
Sub tree right of a node contains only values ​​greater than or equal to the value of the node.
2. Pre-order
Print data on root
Recursively print all the data in the left subtree
Recursively print out all the data on the right subtree
3. In-order
Recursively print all the data in the left subtree
Print data on root
Recursively print out all the data on the right subtree
4. Post-order
Recursively print all the data in the left subtree
Recursively print out all the data on the right subtree
Print data on root
5. Insert BST
Insertion of a new node, preceded by a search operation the appropriate position. In this case the new node will be a leaf / leaf.

6. Delete BST
Delete operation has three possibilities:
– Delete the node without children / child (leaf / leaf): node can be instantly removed
– Delete the node with one child / child: the child node will replace him.
– Delete the node with two children / child: then the node will be replaced by the leftmost node of Sub Tree Right or can also be replaced by the rightmost child of Sub Tree Left.

Stack:

• An important data structure which stores its elements in an ordered manner.
• Linear data structure which can be implemented using an array or linked list.
• Last In First Out (LIFO)
• 

Stack Operation:

• Push(x)         : add an item x to the top of the stack.
• Pop()  : remove an item from the top of the stack.
• Top()  : reveal/return the top item from the stack.

Array Representation:

• Top: Used to store topmost element of the stack
• Max: Used to store the maximum number of elements that the stack can hold.
• When Top is NULL, it means the stack is empty.
• When Top = Max – 1, it means the stack is full.

Linked List Representation:

• Linked list is more dynamic.
• One part of node stores data.
• One part of node stores the address of the next node.
• Top in linked list is the START pointer
• When Top is NULL, it means the stack empty.

Infix, Postfix, Prefix:

• Prefix notation, also known as Reverse Polish notation.
• Prefix : operator is written before operands
• Infix notation (commonly used)
• Infix  : operator is written between operands
• Postfix notation, also known as Polish notation.
• Postfix         : operator is written after operands
• 

Depth First Search

• An algorithm for traversing or searching in a tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore as far as possible along each branch before backtracking.
• 

Queue

• An important data structure which stores its elements in an ordered manner
• The elements in a queue are added at one end called the rear and removed from the other one end called front.
• FIRST IN FIRST OUT (FIFO)
• Two Variable in queue are Front and rear that point to the position where deletions and insertions can be done respectively.
• push(x)         : add an item x to the back of the queue.
• pop()  : remove an item from the front of the queue.
• front()         : reveal/return the most front item from the queue.
• 

Type Of Queue:

• Regular Queue
• Circular Queue
• Priority Queue

Priority Queue:

• An abstract data type in which the each element is assigned a priority.
• An element with higher priority is processes before an element with lower priority
• Two elements with same priority are processed on a first come first served (FCFS) basis

Breadth First Search

• An algorithm for traversing or searching in a tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore all neighboring nodes level per level until we find the goal.
• 

2 Maret 2016 kami kedatangkan Guest Lecturer bernama Bong Defendy yang juga merupakan alumni Bina Nusantara, Beliau adalah seorang TI profesional yang sudah berpengalaman di bidang TI.

Berikut rangkuman yang beliau sampaikan,
Big Data

adalah data dengan ciri berukuran sangat besar, sangat variatif, sangat cepat pertumbuhannya dan mungkin tidak terstruktur yang perlu diolah khusus dengan teknologi inovatif sehingga mendapatkan informasi yang mendalam dan dapat membantu pengambilan keputusan yang lebih baik

Arduino
adalah sebuah platform open source (sumber terbuka) yang digunakan untuk membuat proyek-proyek elektronika.
Raspberry Pi
sering juga disingkat dengan nama Raspi, adalah komputer papan tunggal (Single Board Circuit /SBC)yang memiliki ukuran sebesar kartu kredit. Raspberry Pi bisa digunakan untuk berbagai keperluan, seperti spreadsheet, game, bahkan bisa digunakan sebagai media player karena kemampuannya dalam memutar video high definition
Latex

adalah bahasa markup atau sistem penyiapan dokumen untuk peranti lunak TeX. Tex merupakan program komputer yang digunakan untuk membuat typesetting suatu dokumen, atau membuat formula matematika
Cloud Storage
Cloud Storage adalah sebuah teknologi penyimpanan data digital yang memanfaatkan adanya server virtual sebagai media penyimpanan.
Augmented Reality
Augmented Reality teknologi yang menggabungkan benda maya dua dimensi dan ataupun tiga dimensi ke dalam sebuah lingkungan nyata tiga dimensi lalu memproyeksikan benda-benda maya tersebut dalam waktu nyata. Tidak seperti realitas maya yang sepenuhnya menggantikan kenyataan, realitas tertambah sekadar menambahkan atau melengkapi kenyataan.
SASS (Syntactically Awesome Stylesheets)
Sass (Syntactically Awesome Stylesheets) adalah sebuah pengembangan dari CSS3 dengan menambahkan nested rules, variables, mixins, selector inheritance, dan banyak lagi. Dia menerjemahkan CSS dengan struktur yang lebih baik

Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.

Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna. Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record). Lebar kolom untuk data dapat berubah dan bervariasi. Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap. Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis. Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data

Struktur data terdiri dari:

1. Static memory allocation (array)
2. Dynamic memory allocation (linier dan non linier)

Contoh struktur data yang biasa digunakan:

Array

Linked list

Queue

Stacks

binary tree

• ARRAY

-bersifat homogen (memilki tipe data yang sama)

-merupakan kumpulan data yang sejenis

-bisa diakses dengan mudah (contoh: nama[1])

-indeksnya dimulai dari nol “0”

-array juga memiliki alamat yang saling bersebelahan

• Array Satu Dimensi seperti halnya variabel biasa, array juga harus didefinisikan sebelum ia dapat digunakan. Untuk mendefinisikan array : TipeData namaArray [ukuran]; Contoh : string namaPemain[9]; Perlu diingat bahwa ukuran array adalah max index + 1. Hal ini dikarenakan index selalu dimulai dari nol.
• Array Dua Dimensi, Array dapat dibuat berdimensi dua, dimana array ini mempunyai dua buah index / subscript. Sama seperti array dimensi satu, array dua dimensi juga merupakan kumpulan elemen-elemen yang bertipe data sama dengan satu nama variabel, tetapi terdiri dari dua index. Contoh : int posisi [3][4]; int tipe data array posisi variabel, nama array [3] index (menyatakan jumlah baris) [4] index (menyatakan jumlah kolom)

Storing Array Values

• Initialization of Arrays

Contoh:  int marks[5] = {90, 82, 78, 95, 88};

• Inputting Values

Contoh:  int i, marks[10];

for (i=0; i<10; i++)

scanf(“%d”, &marks[i]);

• Assigning Values

Contoh:  int i, arr1[10], arr2[10];

for(i=0; i<10; i++)

arr2[i] = arr1[i];

Operations in Array

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

• Pointer

Pointer adalah sebuah variabel yang menyimpan alamat dari variabel lain.

Terdiri dari 2 operators penting di pointer adalah:

• & the address operator
• * the dereferencing operator

• Linked list

Linked list adalah sejumlah simpul (node) yang dikaitkan dengan simpul yang lain dengan bantuan pointer dalam suatu urutan tertentu. Suatu linked list dikatakan single linked listapabila hanya ada satu pointer yang menghubungkan setiap node (satu arah “next”).

• Queue

Queue / Antrian adalah suatu kumpulan data yang mana penambahan elemen hanya bisa dilakukan pada satu ujung (disebut dengan sisi belakang atau tail/rear) dan penghapusan atau pengambilan elemen dilakukan lewat ujung lain (disebut dengan sisi depan atau head/front). Antrian menggunakan prinsip Pertama Masuk Pertama Keluar – First In First Out (FIFO). Dengan kata lain urutan masuk sama dengan urutan keluar. Antrian banyak dijumpai dalam kehidupan sehari-hari. Mobil-mobil yang mengantri digerbang tol untuk membeli karcis tol; orang-orang yang mengantri di loket untuk membeli karcis film juga membentuk antrian. Elemen yang pertama kali masuk ke antrian akan keluar pertama kalinya. DEQUEUE adalah mengeluarkan satu elemen dari suatu antrian. Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya sehingga membutuhkan variabel Head dan Tail.

• Stack

Stack dapat diartikan sebagai tumpukan dari benda atau data yang seolah-olah diletakkan di atas data yang lain dimana data yang pertama kali masuk akan terakhir. Secara sederhana sebuah stack bisa digambarkan sebagai tumpukan buku yang disimpan dengan cara ditumpuk keatas. Dimana buku yang pertama kali disimpan atau ditumpuk ada di paling bawah dan yang selanjutnya ditumpuk diatasnya. Dan ketika kita melakukan pengambilan buku ototmatis buku yang terkahir ditumpuk atau disimpan terakhir akan mejadi yang pertama diambil, istilah ini kemudian disebut FILO (First In Last Out) dan bertambah atau berkurangnya data melalui satu ujung yang sama yaitu ujung atas tumpukan (Top of Stack).

• Binary Tree

Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiridan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Selamat Datang

untuk lebih lanjut bisa click di panel kanan di bawah kolom index, atau click link dibawah ini:

1.HTTP – Click disini

2.General Orientation – Click disini

3. Organizational Skill- Click disini

4.Academic Orientation – Click disini

Terima Kasih sudah berkunjung di blog saya, jangan lupa untuk share blog saya dan comment ya!