Heap Tree

Heap is a complete binary tree based data structure that satisfies heap property.

Heap Property :

• Min Heap = each node’s element is smaller than its children’s node.
  • It implies that the smallest element is located at the root of the tree.
  • The largest element is located somewhere at one of the leaves node.
  • Insertion in min heap :
    • We would like to insert a new element into the heap, but we should maintain its heap property.
    • Insert the new element at the end of the heap (after the index of the last element).
    • Upheap the new element (fixing its heap property).
  • Deletion in min heap :
    • Here we only concern with deletion of the smallest element which is located at the root.
    • Replace root with the last element of the heap.
    • Decrease the number of element in heap.
    • Downheap root (fixing its heap property).
• Max Heap = each node’s element is larger than its children’s.
  • Each node’s element is larger than its children’s element.
  • It implies that the largest element is located at the root of the tree
  • Max-heap holds the same principle as min-heap and can be used to create priority queue which need to find the largest element instead of the smallest one.
• Min Max Heap :
  • The heap condition alternates between minimum and maximum level to level
  • Each element on even/odd level are smaller than all its children (min-level).
  • Each element on odd/even level are larger than all its children (max-level).The purpose of min-max heap is to allow us to find both the smallest and the largest element of the heap at the same time.
  • The smallest element is located at the root.
  • The largest element is located in one of the root’s child (either left/right child).
  • Note: the largest element may be located at root if there is only one element in the heap.
  • Insertion :
    • Insert the new element at the end of the heap (after the index of the last element).
    • Upheap the new element (fixing its heap property).
    • Upheap in min-max heap is a bit different with min-heap or max-heap.
  • Deletion :
    • Deletion MIN
      • Replace root with the last element in heap.
      • Decrease the number of element in heap.
      • Downheapmin from root.
    • Deletion MAX :
      • Replace either left-child or right child of root (depends on which one is larger) with the last element in heap.
      • Decrease the number of element in heap.
      • Downheapmax from the node.

Data Structures 07 :

• 2-3 Tree
• Red Black Tree

2-3 Tree :

2-3 Tree ada 2 jenis node

• node 2 : tidak punya anak atau punya 2 anak.  contoh node 2. p dan q bisa null bisa ber angka :  
• node 3: tidak punya anak atau punya 3 anak. contoh node 3. p, q dan r bisa null bisa ber angka : 

2-3 Tree harus simetris, alias perbedaan level kiri dan kanan harus sama.

Insert :

• Selalu insert mengisi yang kosong dari paling atas. kalau dari bawah kosong, cek dahulu ke parentnya, apakah kosong atau penuh, jika kosong, naik lagi sampai terisi bagian atas semua.

Delete:

• Jika yang di delete adalah leaf node, bisa langsung dilakukan penghapusan.
• Jika bukan, harus dilakukan reposisi.

Red Black Tree

Kriteria:

• Root selalu berwarna hitam
• Paling bawah selalu terdapat null node (hitam)
• Tree balance tidak balance dihitung dari jumlah lompatan node hitam dari setiap null node. Jumlahnya harus sama.

Insert :

Node yang baru diinsert selalu berwarna merah.

Jika node yang baru masuk, parent dari node tersebut berwarna merah, dan tetangga dari parent tsb juga berwarma merah, maka harus dilakukan color flip : 

Jika node yang baru masuk, parent dari node tersebut berwarna merah, dan tetangga dari parent tsb berwarma hitam, maka harus dilakukan single/double rotation seperti AVL :

Jika setelah melakukan color flip dan mengubah root node menjadi merah, maka harus dilakukan Re-coloring. atau mengubah warna menjadi hitam. re-coloring ini biasa hanya berlaku untuk root node.

AVL TREE

Binary tree -> tidak tersusun, angka lebih besar atau kecil daripada root bisa bebas kiri atau kanan.

Binary Search tree -> tersusun rapih, biasanya angka lebih kecil daripada root ke kiri dan yg lebih besar ke kanan.

BALANCED BST -> Balanced binary search tree terdiri dari yang disebut AVL tree (Georgy Adelson-Velsky and Evgenii Landis‘ tree) dan Red Black Tree.

θ (log⁡ n) -> avl dan red black tree.

Kali ini hanya membahas AVL tree. AVL ada namanya balance factor. Balance factor adalah perbandingan level antara level kiri dan kanan. contoh: child kiri ada 4 level kebawahnya, child kanan ada 3 level kebawahnya, berarti balance factornya adalah 1. Jika balance factor lebih dari 1, berarti tree tsb tidak balance.

ada 2 cara untuk menyeimbangkan tree tsb

• Single Rotation 
• Double Rotation

*nama-nama diambil dari wikipedia.

Tree and Binary Tree

• Type of Binary Tree
• Property of Binary Tree
• Representation of Binary Tree
• Threaded Binary Tree Concept

A sample of binary tree with 9 nodes, depth of 3, with 8 on the root. Leaves are nodes which contain 4, 7, 13.

Type of Binary Tree

• Perfect binary tree : is a binary tree that every level are at the same depth
• Complete binary tree : every level except the last level is completely filled, a perfect binary tree must be complete.
• Skewed binary tree : is a binary tree that every depth/each node has only 1 child at most.
• Balanced binary tree : is a binary tree which no leaf is farther away from the root than any other leaf

Maximum number of nodes on level k of a binary tree is 2^k.

Maximum number of nodes on a binary tree of height h is 2^(h+1)  – 1.

Implementation of binary tree using array:

Index on array represents node number

Index 0 is Root node

Index left child is 2p+1, p = parent index

index right child = 2p + 2

index parent is (p-1)/2

Implementation using linked list:

struct tree{

int number;

struct tree *left, *right, *parent;

};

struct tree *root = NULL;

Threaded Binary Tree

• is same as binary tree but with a difference in storing NULL pointers.

BINARY TREE

 <skewed Binary tree

• Node at the top is called as root.
• A line connecting the parent to the child is edge.
• Nodes that do not have children are called leaf.
• Nodes that have the same parent are called sibling.
• Degree of node is the total sub tree of the node.
• Height/Depth is the maximum degree of nodes in a tree.
• If there is a line that connects p to q, then p is called the ancestor of q, and q is a descendant of p.

• Binary tree is a rooted tree data structure in which each node has at most two children.

There are 4 types of Binary Tree:

• Perfect Binary Tree
• Complete Binary Tree
• Skewed Binary Tree and
• Balanced Binary Tree

• Each Node of a binary tree has a maximum of 2 childs.

Perfect :

• This Binary Tree has the same depth for every level

Complete:

• This Binary Tree is almost perfect except the last level.
• Perfect Binary tree is also a Complete Binary tree

Skewed :

• Every level only has one node.

Balanced :

• binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Properties of Binary Tree

• Every level of the binary tree, has its own maximum nodes.
• Those levels start from 0.
• In level 0, maximum 1 node.
• In level k, maximum 2^k nodes.

How to count the maximum nodes in a tree according to its height:

height -> 2^(h+1) – 1

Maximum nodes in binary tree of height 3 is

2^4 – 1 = 15

Maximum height = n-1

Minimum height = 2log(n)

Sources : Binus University

Today we are talking about: LINKED LIST IMPLEMENTATION

Linked List

• there are 2 types of linked list; they are Stack (LIFO) and Queue (FIFO).
• push and pop are linked list functions that are used when adding and clearing datas, push for adding a data, pop for clearing or delete a data.
• there are single and double linked list.

What are the differences between stack and queue?

• Stack:
  • First in, last out
  • Last in, first out
• Queue:
  • First in, first out
  • Last in, last out
  • there is a queue called priority Queue = first in not always first out according to the prioritiness.

Push and Pop

• Push – is also called enstack in stack and enqueue in queue is for adding datas into the linked list.
• Pop – is also called destack in stack and dequeue in queue is for delete datas in the linked list.

Single and Double Linked List

• Single
  • single linked list is a one direction linked list, it only goes to one next either right or left according to the programmer
• Double
  • Double linked list is a 2 direction linked list, it has a next and a prev, meaning it will be easier to add data in anywhere.

INFIX, POSTFIX, AND PREFIX NOTATION

• Infix notation (commonly used) usually we used it in maths equation
• Prefix notation, also known as Reverse Polish notation.
• Postfix notation, also known as Polish notation.

Infix: operator is written between operands example 3+12

Prefix: operator is written before operands example + 3 12

Postfix: operator is written after operands example 3 12 +

Why must prefix and postfix exist?

• Prefix and postfix notations dont need brackets to prioritize operator precedence.
• Prefix and postfix is much easier for computer to evaluate.

SEARCHING

• Deep First Search : searching to the deepest data first then just going up
• Breadth First Search : searching side to side.

Data Structures 02

Guest:  Pak Bong Defendy, Binusian 2007

Topics:

• Big Data (Structured & Unstructured)
• Cloud Platform

Cloud Platform:

• Cloud uses 2 centers to store datas: Data Center and Data Recovery Center.
• Data Center is used to store new datas from customers/users.
• Data Recovery Center is used to prevent in missing or corrupted datas.
• Cloud Platform is a platform for cloud computing.

Cloud Computing

• is a kind of Internet-based computing that provides shared processing resources and data to computers and other devices on demand.
• Every data we have can be stored in cloud storages that will be stored in a Data Center.
• Microsoft Azure and Google Cloud Platform are the examples of Cloud. The nearest Microsoft’s data center is at Singapore.
• Cloud computing has become a highly demanded service or utility due to the advantages of high computing power, cheap cost of services, high performance, scalability, accessibility as well as availability.

Disadvantages of Cloud Computing

• DOWNTIME :

This may be one of the worst disadvantages of cloud computing. No cloud provider, even the very best, would claim immunity to service outages. Cloud computing systems are internet based, which means your access is fully dependent on your Internet connection.

• SECURITY AND PRIVACY :

Any discussion involving data must address security and privacy, especially when it comes to managing sensitive data. We mustn’t forget code space and what happened to it after its AWS EC2 console was hacked and its data eventually deleted, forcing the company to close doors forever. Of course, your cloud service provider is expected to manage and safeguard the underlying hardware infrastructure of a deployment, however remote access is your responsibility and, in any case, no system is perfectly secure. You’ll have to carefully weigh all the risk scenarios.

• Etc

Advantages of Cloud Computing

• Flexible
• Disaster Recovery
• Work from ANYWHERE
• Etc

BIG DATA

• Big datais a term for data sets that are so large or complex that traditional data processing applications are inadequate. Challenges include analysis, capture, data curation, search, sharing, storage, transfer, visualization, querying and information privacy.
• Big Data are growing rapidly in part because they are increasingly gathered by cheap and numerous information-sensingmobile devices, aerial (remote sensing), software logs, cameras, microphones, radio-frequency identification (RFID) readers and wireless sensor networks.
• Big Data has structured and unstructured data, every data connects to each other.
• Big data usually includes data sets with sizes beyond the ability of commonly used software tools to capture, curate, manage, and process data within a tolerable elapsed time.

Pointer, Array and Introduction to Data Structures

• Array: stores data in consecutive memory locations and are referenced by index. It is more efficient then storing manually. Index always starts from 0.

In example:

Program manually stored without array:

#include <stdio.h>

main()
{
   int  number1;
   int  number2;
   int  number3;
   int  number4;
   int  number5;
   
   number1 = 10;      
   number2 = 20;   
   number3 = 30;   
   number4 = 40; 
   number5 = 50;     

   printf( "number1: %d\n", number1);
   printf( "number2: %d\n", number2);
   printf( "number3: %d\n", number3);
   printf( "number4: %d\n", number4);
   printf( "number5: %d\n", number5);
}

Program using array: 

#include <stdio.h>
 
int main ()
{
   int number[10]; /* number is an array of 10 integers */
   int i = 0;
 
   /* Initialize elements of array n to 0 */         
   while( i < 10 )
   {
      /* Set element at location i to i + 100 */
      number[ i ] = i + 100;
      i = i + 1;
   }
   
   /* Output each array element's value */
   i = 0;
   while( i < 10 )
   {
      printf("number[%d] = %d\n", i, number[i] );
      i = i + 1;
   }
 
   return 0;
}

There are some operation that can be performed in arrays :

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

Pointer: is a programming language object, whose value refers to (or “points to”) another value stored elsewhere in the computer memory using its address

2 symbols in pointer:

&: Address Operator

*: Deferencing Operator

Using Pointer:

in example a declaration:

1. int x;
2. int*p = &x;

So there is an integer x, and a pointer p. P took a value from an integer that is pointed. In this case P is pointed to x’s address. In conclusion, the value of x will be also the value of pointer P.

If we declare that x=10; or we can write *p = 10;

then *p and x has a value of 10.

Data Structure:

• A data structure is an arrangement of data, either in the computer’s memory or on the disk storage
• is a particular way of organizing data in a computer so that it can be used efficiently

Here are some examples of data structures:

• Arrays
• Linked Lists
• Queues
• Stacks
• Binary Trees
• Hash Tables

Linked Lists:

• is a linear collection of data elements, called nodes pointing to the next node by means of pointer
• Each element is called a node
• is a data structure that consists of a sequence of data records such that each record there is a field that contains a reference to the next record in the sequence
• Linked lists are the best and simplest example of a dynamic data structure that uses pointers for its implementation
• Linked lists have a few advantages over arrays:
  1. Items can be added or removed from the middle of the list
  2. There is no need to define an initial size

  However, linked lists also have a few disadvantages:

  1. There is no “random” access – it is impossible to reach the nth item in the array without first iterating over all items up until that item. This means we have to start from the beginning of the list and count how many times we advance in the list until we get to the desired item.
  2. Dynamic memory allocation and pointers are required, which complicates the code and increases the risk of memory leaks and segment faults.
  3. Linked lists have a much larger overhead over arrays, since linked list items are dynamically allocated (which is less efficient in memory usage) and each item in the list also must store an additional pointer.

The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list.

A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.

Queue:

• is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position
• The elements in a queue are added at one end called the rear and removed from the other end called the front

Binary Trees:

• is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
• data structure which is defined as a collection of elements called the nodes
• Every node contains a left pointer, a right pointer, and a data element

Abstract Data Types:

• is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.
• C/C++ has a concept called class and struct which assist the programmer in implementing abstract data type.
• For example, integers are an ADT, defined as the values …, −2, −1, 0, 1, 2, …, and by the operations of addition, subtraction, multiplication, and division, together with greater than, less than, etc., which behave according to familiar mathematics (with care for integer division), independently of how the integers are represented by the computer.

Talking about Structure:

• Structure
• Nested Structure
• and Array of Struct

Example of a Structure:

struct x{

int x;

char b;

};

x data;

x is a data type like integer and float, and data is the variable.

Example of a Nested Structure:

There is a struct inside a struct.

struct profile {

int   age;

char  name[100];

};

struct student {

struct profile p;

int  score;

char grade;

};

student x;

x.score = 92;

x.grade = ‘A’;

x.p.age = 20;

strcpy(x.p.name,”budi”);

Example of Array of Structure:

struct profile {

int   age;

char  name[100];

};

struct student {

struct profile p;

int  score;

char grade;

};

student arr[10];

arr[0].score = 92;

arr[0].grade = ‘A’;

arr[0].p.age = 20;

strcpy(arr[0].p.name,”budi”);

arr[1].score = 83;

arr[1].grade = ‘b’;

arr[1].p.age = 19;

strcpy(arr[1].p.name,”chandra”);

Dalam Blog ini, saya ingin membahas nih tentang pengalaman saya kemarin pas FEP Binusian 2019. Nah, pertama-tama saya ingin berbagi pengalaman kepada kalian yang ingin masuk binus jurusan Computer Science dan teman-teman.

1. FEP Binusian 2019 General Orientation

Nah, kebetulan saya sendiri mendapat giliran orientasi pada saat 18 Agustus kemarin atau bisa disebut Batch 4 (DAS). Awalnya dalam mindset saya, FEP GO itu membosankan, harus bangun pagi dan pulang sore. Memang harus bangun pagi karena saya sendiri mendapat jadwal yang kurang beruntung. FEP GO yang harusnya selama 6 hari, saya hanya menyelesaikannya dalam 5 hari karena tanggal 17 Agustus (hari senin) itu tanggal merah jadi jadwal pasti dibuat lebih padat daripada biasanya. Jauh-jauh hari sebelum FEP GO berlangsung, admin Gabung_Binus di line invite kami para peserta GO untuk masuk ke grup Batch masing-masing agar tidak ketinggalan informasi apapun dan juga untuk mengenali satu dengan yang lain agar pas di kelas sudah kenal. Di grup itu pun kami saling berkenalan sampai kami mengumpulkan teman-teman yang sekelas untuk membuat grup baru. Pada tanggal 18 Agustus kami pun masuk ke kelas dan sudah cukup kenal satu dengan yang lain, dan dengan berkenalan sebelum kelas berlangsung pun membuat kelas kami lebih kompak dan seru. Saya berada di kelas DAS 04 pada saat itu yang berisi mahasiswa dari jurusan Teknik Informatika, Sistem Informasi, dan Management. Di GO ini kami pun bertemu BC (Buddy Coordinator) yang amat baik. Kami dibimbing dari 0 yang artinya kami memang benar-benar tidak mengerti dunia perkuliahan dan sistem binus seperti apa. Mulai dari awal berdirinya binus, UKM/HMJ, Binusmaya, sampai dijelaskan PTTKK Binus. Awal mindset orang-orang pasti kalau mendengar orientasi, selalu teringat dengan Ospek, tapi lebih baik hapus mindset tersebut karena di FEP GO ini, mahasiswa baru sama sekali tidak dikerjai sama sekali. Tambah hari kami tambah dekat, tambah kenal satu dengan yang lain. Saat hari terakhir, tepatnya hari Sabtu, kami ada acara kebersamaan yaitu kami mempersembahkan Yel-Yel setiap kelas. Dengan membuat yel-yel bersama juga membuat kami lebih dekat dan yang pasti lebih heboh dari awal kami FEP GO. Satu persatu kami mempersembahkan yel-yel per kelas. Setelah acara kebersamaan itu pun kami ada Expo, yang merupakan pameran dari UKM dan HMJ di Binus University. Nah apa itu UKM/HMJ? Akan saya jelaskan setelah ini.

2. UKM (Unit Kegiatan Mahasiswa) & HMJ (Himpunan Mahasiswa Jurusan) (Organisation Skills)

Nah di binus, ada yang namanya UKM dan HMJ, kalau pas SMA, kita bisa sebut UKM adalah ekstrakurikuler. Di Binus, kurang lebih sama, banyak UKM yang tersedia, seperti olahraga Futsal, Basket, Badminton, juga ada komunitas-komunitas agama, dan ada UKM bela diri asal indonesia yaitu Merpati Putih. Kebetulan saya sendiri beragama Buddha, jadi saya mengikuti komunitas Buddha Binus yang bernama KMBD (Keluarga Mahasiswa Buddhis Dhammavaddhana), tidak hanya KMBD, saya juga mengikuti UKM Futsal sebagai hobi saya bermain Futsal. Nah kita beralih ke HMJ, himpunan itu bisa dibilang organisasi seperti OSIS. Setiap jurusan mempunyai HMJ masing-masing, contohnya, karena saya anak Computer Science, maka saya bisa mengikuti HMJ HIMTI (Himpunan Mahasiswa Teknik Informatika), nah jadi total saya mengikuti 3 UKM&HMJ yaitu Futsal, KMBD dan HIMTI pastinya. Nah, HIMTI pun mengadakan acara welcoming party untuk mahasiswa baru Binus yang bernama HTTP (HIMTI Togetherness and Top Performance) pada tanggal 12 September kemarin.

3. HTTP (HIMTI Togetherness and Top Performance)

Nah acara HTTP ini diselenggarakan oleh HIMTI hanya untuk Mahasiswa baru Binus University di semua kampus Binus. Acara ini hanya bisa diikuti oleh mahasiswa CS (Computer Science/Teknik Informatika), GAT (Game Applications and Technology), MAT (Mobile Applications and Technology), Cyber Security, CS-Mathematics dan CS-Statistics. Makanya sangat sayang bila acara yang sangat diprioritaskan untuk anak TI dan teman-teman dilewatkan begitu saja, kami pun hanya cukup mengeluarkan uang 150rb dan kami mendapatkan banyak keuntungan menarik seperti PBC (Pembelajaran Bahasa C), T-Shirt SHINE, HIMTI Kit dll). Nah, acara ini bertema SHINE atau Strengthening Harmony and Inspiring New Experiences yang berarti mendapat jaringan baru (teman baru) dan juga mendapatkan pengalaman-pengalaman baru dari acara tersebut. Di acara ini, tidak hanya ditampilkan pertunjukan menarik dari HIMTI tetapi juga ada diadakan Talkshow yang sangat bermanfaat untuk memotivasi kita untuk ke depannya. Akhir acara pun ada Guest Star yang sangat membuat gedung acara berguncang. Hampir lupa, acara ini diselenggarakan di gedung BPPT II di Jl. M.H Thamrin, Jak-Pus pada tanggal 12 September kemarin. Acaranya memang sangat membuat kami lelah karena jam 9 acara sudah dimulai dan jam 8.30 kami harus sudah siap di gedung acara. Tetapi acaranya memang bermanfaat, pastinya seru dan sangat sayang untuk dilewatkan.

4. FEP Academic Orientation

7 September kami masuk kuliah kembali untuk mengikuti Academic Orientaion atau bisa disebut orientasi sesi 2. Nah, di orientasi ini, kami sudah mulai diajarkan bahan kuliah yang akan kami pelajari. Kebetulan, bahan pertama yang akan kami belajar nanti adalah Algorithm and Programming, di AO ini, kami diajarkan basic-basic tentang algoritma dan bahasa c. Tidak hanya belajar, kami juga dibimbing lagi dengan beberapa sesi tentang center-center yang ada di binus, academic advisory dan juga tentang kurikulum yang akan kami pelajari selama kuliah 4 tahun ini. Memang pelajaran yang diajarkan oleh dosen lebih susah dari yang saya pikirkan, tetapi saya yakin lama kelamaan saya akan terbiasa dengan pelajaran tersebut.

Terima Kasih sudah membaca blog pertama saya 🙂 Sampai bertemu di blog berikutnya.

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂