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