Pertemuan 5-Binary Search Tree-2101640952-Stephanus Nico Budiarso

Tree is different with graph. Graph can have loop, meanwhile a tree can't have any loop.

Binary tree is different with binary search tree. Binary search tree has some rules that must be fullfilled. The rules are:

• The left leg must contain the node that has less value than the root. The right leg must contain the node that has greater value than the root.
• The data is sorted.

Operation in Binary Search Tree

1. find(x)       : to find node that contain x value
2. insert(x)    : to insert node with x value
3. remove(x) : to remove node with x value.

How find (x) works

1. x value will be checked whether it's greater or less than the root.
2. If x value is less than the root, then the searching will be continued in the left side.
3. If x value is greater than the root, then the searching will be continued in the right side.
4. The search continue with the same rule until the x value is found.

How insert (x) works

1. x value will be checked whether it's greater or less than the root.
2. If x value is less than the root, then it will be inserted in the left side.
3. If x value is greater than the root, then it will be inserted in the right side.
4. This rule must also be fullfilled in the children node.

Example:

How remove (x) works

There are three conditions that we should consider:

1. If x value is the leaf, just delete the node.
2. If x value is in the node that only have one child, just delete the node and replace it with the child.
3. If x value is in the node that have two children, do these several steps:

• First, we need to find the x value by using find(x) function.
• Then we delete the x value and replace it with the greatest value in the left side or the least value in the right side.

Example:

Pertemuan 4-Introduction to Tree, Binary Tree and Expression Tree-2101640952-Stephanus Nico Budiarso

Tree Concept

Tree is a collection of one or more nodes.

Example:

The degree of tree is 3. Height is the same as degree of tree. The topmost node is called as root. The line that connect the nodes are called edge. Nodes that have children are called parents and children with same parent are called sibling. Nodes that have no children are called leaf.

Binary Tree

Binary tree is a tree that each node has at most two children. Maximum number of nodes on level k of a binary tree is 2k. Maximum number of nodes on binary tree height is 2h+1 - 1. Minimum height of a binary tree of n nodes is 2log(n). Maximum height of binary tree of n nodes is n-1.

There are four types of binary tree. Those are:

• Perfect binary tree

Perfect binary tree is a binary tree that all levels are full filled. Every parent nodes has two children.

• Complete binary tree

Complete binary tree is a binary tree that all levels are full filled except the last level may not be full filled. A perfect binary tree is also a complete binary tree.

• Skewed binary tree

Skewed binary tree is a binary tree which each node has at most one child.

• Balanced binary tree

Balanced binary tree is a binary tree which has the same amount of leaf in the right and left side.

Implementation Using Array

Index on array represents node number.

Index 0 is root node.

Index left child is 2p+1.

Index right child is 2p+2.

Index parent is (p-1)/2.

p is parent index.

Implementatiton Using Linked List

Expression Tree Concept

Prefix   : *+ab/-cde

Postfix : ab+cd-e/*

Infix     : (a+b)*((c-d)/e)

How to read:

Prefix: read from the root then go down to the left side until the leaf on the left side. Continue with the right node.

Postfix: read from the most left bottom. Continue to the right node.

Infix: read from the left to right.

Pertemuan 3-Linked List: Implementation II-2101640952-Stephanus Nico Budiarso

Stack
Stack concept is Last In, First Out (LIFO).

Stack Using Array and Linked List 

1. Array
Top is the topmost data of the stack. Max is the maximum number of elements that the stack can hold.

If TOP=NULL, then means the stack is empty.
If TOP=MAX-1, then the stack is full.
If TOP=0, then the stack have one data.

2. Linked List
In a linked list stack, every node has two parts:
- one that stores data
- one that stores the address of the next node (pointer to the next node).

If TOP=NULL, then means the stack is empty.

Stack Operation
- push(x) : add x to the top of stack
- pop() : remove the top data of stack
- top() : reveal the top data of stack.

Example:

Prefix, Infix, Postfix
Prefix: Operator is written before operands.
Syntax: operator, left operand, right operand.

Infix: Operator is written between operands.
Syntax: left operand, operator, right operand.

Postfix: Operator is written after operands.
Syntax: left operand, right operand, operator.

Example:

Prefix	Infix	Postfix
* 4 10	4 * 10	4 10 *
+ 5 * 3 4	5 + 3 * 4	5 3 4 * +
+ 4 / * 6 – 5 2 3	4 + 6 * (5 – 2) / 3	4 6 5 2 – * 3 /  +

Depth First Search

Using the stack concept.

Algorithm:

Prepare an empty stack

Push source/root into stack

Mark source/root

While stack is not empty

  Pop an item from stack into P

  For each node X adjacent with P

  If X is not marked

  Mark X

  Push X into stack

Queue

Queue concept is First In, First Out (FIFO).

Queue Operation

- push(x) : add x to the back of queue.

- pop() : remove the front data of queue.

- front() or peek() : reveal the most front data of queue.

Example:

Breadth First Search

Using queue concept.

Algorithm:

Prepare an empty queue

Push source/root into queue

Mark source/root

While queue is not empty

  Pop an item from queue into P

  For each node X adjacent with P

  If X is not marked

  Mark X

  Push X into queue

Pertemuan 2-Linked List: Implementation I-2101640952-Stephanus Nico Budiarso

Linked list is a linear collection of nodes. Nodes consist of data and pointer that points to the other nodes.

Single Linked List
Single list consists of nodes which contain only one pointer and a data.
To insert the nodes, we can use 4 methods:

1. The new node is inserted in the beginning
2. The new node is inserted in the end
3. The new node is inserted after given node
4. The new node is inserted before given node.

This is the logic example of the new node that is inserted in the beginning assuming that there is a linked list containing 10,35,27. We want to insert 31.

To delete a value, first we need to find the location of node which store the value we want to delete, remove it, and connect the remaining linked list.

This is the logic example of deleting the node in the beginning. In this example, we want to delete 31.

Circular Single Linked List

In circular, last node contains a pointer to the first node. There is no storing of NULL values in the list.

Double Linked List

Double linked list is also known as two-way linked list, because the nodes contain two pointer, one pointer points to the next node, the other one points to the previous node.

The way to insert data is the same like in single list, first we should allocate the new node and assign a value to it, then we connect the new node with the existing linked list.

To delete a value, there are 4 things that we need to pay attention :

1. The node to be deleted is the only node in the linked list
2. The node to be deleted is head
3. The node to be deleted is tail
4. The node to be deleted is not head or tail

Circular Double Linked List

In circular, the first node contains a pointer to the last node and the last node contains a pointer to the first node.

Pertemuan 1-Pointer, Array and Introduction to Data Structure-2101640952-Stephanus Nico Budiarso

Array

Array is a collection of similar data elements (homogenous data type). Value of array stored in consecutive memory locations and are referenced by an index. Index starts from zero (0) and ends with index-1.

• One Dimensional Array

Syntax: type var[index];

Declaration: int a[10];

Accessing:
a[0] = 8;
a[1] = 10;
a[2] = 6;
a[3] = 2;

• Two Dimensional Array

Syntax: type var[index1][index2];

Declaration: int a[10][20];

Accessing:

a[0][12] = 8;

a[1][2] = 10;

a[2][11] = 6;

a[3][8] = 2;

• Multi Dimensional Array

Syntax: type var[index1][index2][index3][...];

Declaration: int a[10][20][12][9];

Accessing:

a[0][12][0][5] = 8;

a[1][11][6][8] = 10;

a[2][14][5][2] = 32;

a[3][2][7][5] = 24;

The maximum dimension of multi dimensional array is nineteen (19).

Operations that can be performed on arrays are: traversal, insertion, searching, deletion, merging, and sorting.

Pointer

Pointer is a data type whose value refers to another value stored 

elsewhere in computer memory using its address.

The two most important operators used with pointer type are:

• &  the address operator

• *   the dereferencing operator

The difference between single pointer and double pointer:

Variable with single pointer points to the value of another variable which address it

stores. Meanwhile, variable with double pointer points to the value of another variable

which address is already being stored in other variables.

Introduction to Data Structure

Array
The lack of using array: memory that needed is much bigger.

Linked lists
The benefit of using linked lists is dynamic allocation. With dynamic allocation, the memory that used will be added as soon as it used.

The difference between queue and stack:
queue: first in, first out.
stack: first in, last out.

The elements that added at one end called the rear and removed on the other end called the front.

Binary trees will be disscussed after the midterm exam.

Why we should learn data structure?

Social media holds the important role in these days on the internet. The basic of social media is data.
When we use the search engine, such as google, then the ads that shows up are based on what we search, our interest. This happens because our search data were stored using data structure.