Binary Search Tree

Rooted Tree

A rooted tree is an abstract data type which consists of nodes arranged in hierarchical order.

A picture I drawed using Word.

As the picture shows, the tree is like a tree reversed. The single node at the top is called root. Nodes that have nodes connected to it below is called parent nodes; the one or two nodes below a parent is called child node. If a node doesn’t have any child node, it is called a terminal node or a leaf.

Binary Tree

Given the concepts above, each parent in a binary tree has at most two child nodes – that’s why it is binary.

A binary tree can be divided into three subsets, or it can be empty, as shown above.

How Is Binary Tree Useful?

Firstly, it can represent the order of mathematical calculation. For example, brackets are calculated first, then the power, then multiplication and division, and at last addition and subtraction.

To operate this arithmetic expression, we should start from the bottom to the top and from left to right. The actual numbers are stored in the terminal nodes of the binary tree. Using this binary tree, the expression is presented unambiguously. 

Retrieved from Mr. Pete’s presentation

This is a diagram that shows the binary tree as a data type. Each item is the actual value and is stored with two pointers which serve as addresses. If there is no child node below, the value of the pointer is zero.

Traversal

Tree traversal means to visit all the nodes of a tree in particular order. Here are three ways of traversing a binary tree.

• Pre-order traversal
  • The root is visited first
• In-order Traversal
  • The root is visited in the middle
• Post-order traversal
  • The root is visited at last

To illustrate the difference between these traversals clearly, we can imagine a flag on each of the nodes.

To visit the nodes in the correct order, we just need to follow the flags along the tree, as shown in this picture:

For the original presentation, click me

By using these traversals, we can visit all the nodes in different ways in each of which there is only one and single order.

Exercises

Here are the exercises for binary tree.

2+3*6-2
(8/2)+(5*2)
3*5-(17*(21-5))

 

My answer to the exercises

An exercise for tree traversal:

Pre-order:DBACFEG

In-order: ABCDEFG

Past-order:ACBEGFD

 

Binary Search Tree

BST is a dynamic data structure used for quicker research and easier addition.

Here are several requirements for a BST:

• it is a binary tree;
• each node contains a value;
• a total order is defined, which means each two values can be compared with each other;
• there is no duplicate;
• the left subtree of a node is always smaller than the node,
• the right subtree of a node is always greater than the node.

To use a binary tree, there are several operations that we are going to look at:

• search for a value;
• add a value;
• remove a value;
• arrange all values in particular order (tree traversal)

Look Up Operation

To look up a value in a binary search tree, we would start at the root and do the followings:

1. check, whether the value in current node and searched value are equal. If so, the value is found. Otherwise,

2. if searched value is less than the node's value:

   • if the current node has no left child, searched value doesn't exist in the BST;

   • otherwise, handle the left child with the same algorithm.

3. if a new value is greater than the node's value:

   • if the current node has no right child, searched value doesn't exist in the BST;

   • otherwise, handle the right child with the same algorithm.

(retrieved from algolist.net)

Insertion Operations

The steps for insertion operation is similar to the searching operation. We we found that the searched value doesn’t exist, we insert one.

Removal Operations

In a similar way, if we want to remove something, we first find it and then remove it. However, there are three situations:

When the node has no child: Just deleting it.

When the node has one child: Connecting the single children to its parent.

When the node has two children: Finding the minimum value of the right subtree and replace it. (Since the value of the node is the middle of the left subtree and right subtree.)

Linked List

This website, visualgo, is very useful since it teaches you about many CS concepts and provides a simulation. After I tried binary tree, I explored linked list. Generally, there are five types of linked list. Single linked list has one-direction arrows while doubly linked list has two-direction arrows. For stack, we can only add, remove, search the head of the list. For queue, we can search the head value, remove it, or add new value to the tail. For deque, both head and tail can be added value, removed, or searched.