Binary Search Tree (TreeMap-1)

Binary Search

Array as data structure

It's quick to search such an array for a particular value, using a binary search. You check in the center of the array; if the object you're looking for is greater than what you find there, you narrow your search to the top half of the array; if it's less, you narrow your search to the bottom half.

Binary Search Tree (TreeMap-1)

Assuming we have n elements, the first step will divide it into n^'=n/2 elements. Second step will further divide n^' into n'/2 elements = (n/2)/2 = n/2²
At k^th step, number of elements would be n/2^k.
This can go on till we end up with just one element, so at the last step m^th, we will have
n/2^m = 1 n = 2^m log(n) = m

Thus we can say binary search finds the object in O(logN) time
Insertion would take more time as we first need to find where the object will go, and then move all the objects with greater keys up one space in the array to make room for it. These multiple moves are time consuming. Deletion involves the same multiple move operation, and is thus equally slow. If you're going to be doing a lot of insertions and deletions, an ordered array is a bad choice.

LinkedList as data structure

Insertions and deletions are quick to perform on a linked list. They are accomplished simply by changing a few references. Unfortunately, however, finding a specified element in a linked list is not so easy. You must start at the beginning of the list and visit each element until you find the one you're looking for.

Binary Tree

Binary Tree combines the advantages of two other structures: an ordered array and a linked list. You can search a tree quickly, as you can an ordered array, and you can also insert and delete items quickly, as you can with a linked list.

Data Structure

Binary Search Tree (TreeMap-1)

New Entry

Binary Search Tree (TreeMap-1)

Unbalanced Tree

When a tree has more nodes on one side of the root than the other we call the tree un-balanced.
Trees become unbalanced if data is inserted in already sorted order. Suppose the order of insertion is 5,17,19,24,26,27,28,29,30,34, we will get the below structure which is more like a LinkedList. With an unbalanced tree, the capability to quickly find (or insert or delete) a given element is lost. It will now take time proportional to n, O(n).

Binary Search Tree (TreeMap-1)

If these key values are inserted randomly, the tree will be more or less balanced.
Next chapter will explore Red-Black Tree which is one of the way to solve the problem of unbalanced trees.