Data Structure : Tree and Binary Tree: Part 1

In the last post we discussed Advance Sorting, an algorithm; we are shifting back our focus to data structure. The fundamental data storage structure used in programming language: Binary Tree. If you are wondering why discuss one more data storage structure when we know two data storage array and linked list, you will get the answer by end of this post.

There is an issue with array, specially ordered array: Slow insertion. Steps you need to insert a new data in ordered array are

1.      Search for the right place: An ordered array can be quickly searched using binary search algorithm. Compare the new data with the value in the middle of array, if it is less narrow your search to top half of the array. Repeatedly executing the process will complete the search in O(log N) time.

2.      Create Space: Shift all the data 1 block to the right of identified place to create space for new record. This is very time consuming steps.

3.     Now insert the data.

Step 2 & 3 are the reasons, insertion is slow in ordered array. This insertion issue is tackled using linked list as data structure. Insertion and deletion in linked list require O(1)  as insertion and deletion in linked list is accomplished by changing references.

Unfortunately, finding a data in linked list is not so easy. You have to start at the beginning of the list and visit each element until you find the right place/data. Even an ordered list cannot help, you have to start at the beginning and visit each element in order.

So is there any data structure with quick insertion and deletion of linked list and also quick searching of an ordered array?

 Yes, Binary Tree.

Before, we start discussing Binary Tree, lets go through from some basics of Tree

Tree is collection of nodes connected by edges. Nodes represent the value and edges between the nodes represent the way nodes are related. Conventionally nodes are represented by bubbles or circles and edges are represented by lines.

Below diagram presents the tree terminology

Root – Root is a node which does not have any parent.

Parent – Node in the tree that is one step higher in hierarchy and lying on the same branch

Child – As in the diagram above: B & C are the child of A, D & E are the child of B and F & G are the child of C. A child is node which is directly linked with its parent and it is below parent in structure. Data structure tree is upside down version of actual tree. Root on top, branches growing downward and leaf at the bottom.

Sibling – Nodes that share same parent. As in the diagram above D & E are siblings

Leaf – Nodes without children are called leaf node.

We will discuss rest in next week.