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: