Hash tables & Dictionaries

 

Introduction

   Many normal developers simply think that hash tables are something to store a key-value pair. That’s it. What are its applications are not known. Some people directly correlate with C++ STL data structures map and hash map. :)

   hash map is faster than map. But why is that?

We have seen many sorting algorithms already. For searching there are neat data structures available which does our job. What is necessary for a best searching algorithm?

• lookup should be O(1)
• insert should also be O(1)
• delete should also be O(1)

In the sorting case, this is never possible. :) But sorting becomes the basis for searching like binary search. But even that won’t give you O(1).

That’s where we go for the dictionaries. Dictionaries or Hash tables, both mean the same. Don’t confuse!!.. I did that.. :)

Dictionaries are nothing but hash tables which gives you lookup of O(1). Just an another name. :D

Concept

   To explain this simply, take a normal English dictionary. You know the word you need to search for. Just take the dictionary and go directly to the first letter page then continue to scan for the second letter. This means, dictionary is organized in such a way that, your lookup is fast.

   Even hash tables are designed so that your lookup is fast. But you should know the key to look for. For example, Take a normal array. You know that you need to get the 5th element from it. then, you simply do array[5]. This means, your lookup is just O(1).

  Plainly, hash tables are expected to work like arrays. Just give a key, you get a value in O(1) time. But note that, in worst case, in hash tables you get O(n) as well. This happens when, your key doesn’t directly get you the value.

  So, hash tables or linked list both give the same O(n) worst case. But practically hash tables need to be designed so that, the hash or the key used to access the table is unique and can identify clearly a single slot in the table.

  What we are discussing till now, is direct access table. You can always find a value with the key given. If key is not unique, we may need to search a linked list. That’s it.

My understandings

• Just remember bucket sort. Hash tables are similar to that.
• Direct access table is impractical. But the best, if the data set to represent is small. Key’s are mostly embedded part of the table and also the data will be part of the table rather than being a list.
• If the key is not unique, it perfectly matches your bucket sort.
• Upcoming articles we will try direct access tables. Hash map has more concepts like collisions, using a cyclic buffer, rehashing etc. But without understanding direct access tables, studying those are useless.. :D

Division method–5th Grade way

"As you become old, you will definitely forget your primary school rhymes!!.. similar to that, you would also forgot multiplication and division as well!!.. This is the dummy’s way to understand, Division with reminder.. Take 1 in the hand, 5 in the middle.. :)”

Introduction

  Suddenly, i found that i forgot the 5th Grade Long division method. I don’t know about you. But thought of covering it, as its not so simple.. :)

  It’s not a pure dummies or a 5th grade guide. We need to understand Long division method clearly to go in-depth for doing Division of Large numbers or Getting reminder between two large numbers.

  As you might guessed, division of large numbers (as heavy as 2048-bit size) are used now in RSA which is also proven to be cracked within years!!.. :)

  As this method is required basics for RSA encryption algorithm, this article will be useful for a computer geek as well as a 5th grader!!..

Concept

  The way we do long division is simple. But underlying logic behind division is very important one to understand. Multiplication if you take,

  how we come up with 4*3 = 12 ? 4 + 4 + 4 or 4 added 3-times gives you 12. So for a successful multiplication, just successive additions are more than enough. Even in current systems, they just use the adder circuit at ALU to do this.

Then what does 12/3 does ? There are 2-types are division a system categorized into,

• integer division
• floating point division

12/3 will yield you just an integer. So, based on programming language and system, it selects to use integer division where floating point is completely ignored.

Try, int z = 12/5

You will just get z=2. At the same case, if you convert these to float, you get the mantissa & exponential part which might require more than 32-bit. (float is just 32-bit, double is 64-bit).

Try this now,     float z=12.0/5.0;

The above is an example of floating point division.

At the core, division happens using subtraction. 12/3 means.. how many times subtracting three yields zero.

“Ok, i understood int, float. What is quotient and reminder ?”

(Take example: 12/3) - quotient(4) is the number you get after you divide with divisor (3) the dividend(12). Sometimes, just subtracting denominator with numerator will not yield zero. Subtract as much as you can so that, the value is less than your quotient. This value will become your reminder.If you want to continue subtracting, then it must be after a decimal point.

In the above division, 10 is the reminder and 17 is the value you get in integer division. now to find the exponential part, you can further divide from there, 10/25.. :) you get 0.4. So the resultant of this division is 17.4.

More explanation

  Division is just a concept of finding out how many values are inside a value

Just take the below long division example,

This is the normal way, we have learnt the division. But actually what happens here is different and this needs to be understood to write code to do large number division.

The above is the right way our teachers should have explained. We don’t just take the first 2 digits, we always assume that we have 0’s to complement as. 23*3 = 69 if we do and just subtract the first 2 digit simply means that there are 0’s in the other places. we have to finally add, all these 300 + 60 + 8 to get the actual quotient. Remember that, 11 is the reminder we have got. If we further divide, 11/23.. you get decimal pointed values.

Thus, it doesn’t mean that you need to always have 23*3 for your operation. you can even do like the above way, if you want to step in a easy multiplicative way.

References

http://en.wikipedia.org/wiki/Binary_multiplier

http://www.conceptualstudy.org/Elementary%20Math/Understanding%20Division.htm

Some exercises

“Now, how would you find the reminder between 56.74 / 45.67647”

In C++, you have fmod. Normally, you can do the following,

• first do integer division of the above numbers - 56/45
• now to get the reminder do this, 56.74 – 45.67647 * quotient (which is 1 in our case)
• this gives out our reminder as, 11.06

 

 

 

   

Tail recursion–in detail

“The beauty of recursion is that!!.. - the beauty of recursion.”

Author speaks

  Sorry for not publishing any post nowadays. Tied up with lots of personal work. Now, would love to continue the series without gaps at least for some time. This promise is Without any GURANTEE, WARENTEE or any BONDS. :)

Metaphor

  If you catch something by tail, it tries to attack you using its head. :D

I think the below image will make you remember very well what is tail recursion.

Introduction

   Tail recursion is something that is more native to functional programming languages. In Maths, a tail recursive function is a function that expands itself.

Say, g(x) = f(x)

Then, tail recursion happens like this formula,        f(x) = f(g(x))

This means, f(x) = f(f(x)) = g(f(f(x)) = f(f(f(x))) … it goes on

This is purely useful for writing an mathematical logic which has a specific end condition. But this kind of recursion is majorly used in optimization of stack space in C++ and similar languages. Even some dynamic languages support this recursion type. But python doesn’t support it because of simple inherent problems for developers while using tail recursion.

Concept

   As i explained, tail recursion is mostly used for optimization & mathematical problem and widely popular in functional programming. The most and the perfect way a tail recursion works is really good for designing mathematically a computer program. But if you are normal novice software engineer, you just use this for optimization and only when its necessary because of its demerits:

• Stack doesn’t contain any footprint of the recursion happening. Compiler tries to expand the cycling recursion into instructions without using stack
• As there is no stack data, no way to debug such programs easily.
• Compilers might sometime fail to make the right jumps and data corruption can never be captured.

Already developers fight with pointers when this havoc adds more headache to it.

Programmers can think tail recursion as, just processing things using arguments itself and keep the returned value as the recursive call to the function. This makes the compiler to process the return value which expands the recursive calls in the single stack frame!!

Code

#include <iostream>

int fib(int n)

{

    if(n==0)

        return 0;

    else if(n==1)

        return 1;

    else 

        return fib(n-1) + fib(n-2);

}

int main()

{

    std::cout<<fib(7);

    return 0;

}

• Assembly is generated with tail optimization only when release mode is selected with Visual Studio C++.
• You can note that there is no stack footprint by the executable created by this, by tracing the disassembly.

Conclusion

Is it good or bad? based on the need and stack space savings requirement.

Convert a binary tree to threaded binary trees

“We know the important property of binary tree. Each level has 2^n nodes. If that is the case, what is the number of empty nodes in the leaves. empty nodes mean left or right null near the tree leaves. If its a perfectly balanced tree, you get around 2^<height of the tree> nodes. Which is huge!! and goes for a big waste!!”

See first

http://analgorithmaday.blogspot.com/2011/06/applications-of-traversals.html

Introduction

   This is another memory optimization concept where you need to reuse unused space present in the linked list and get easy traversal to parents. And remember the complex problem you would have heard about,

Converting a binary tree to a doubly linked list in-order way without using extra space & reusing the empty left& rights.

Problem Description: http://nirmalthacker.wordpress.com/2007/03/31/algorithm-problem-binary-tree-to-list/

This problem is simply nothing but making a binary tree a threaded binary tree with some extra linkages done for getting the doubly linked list property.

There is one more problem for more interested people,

http://www.careercup.com/question?id=3424767

Find the pre-order traversal of a tree without using recursion, stack, extra memory. You can reuse the space already present in the tree and create temporary nodes if required.

There are many applications & interview questions like this which requires prior & complete knowledge of threaded binary trees.

Concept

  How threading is done? We know that around 2^<height of the tree> nodes are empty. Which mostly constitutes 50% of the nodes in the tree. There is a mathematical proof for this.

 Let a null LEFT reference point to the predecessor in in order, and
  let a null RIGHT reference point to the successor in in order.

We need to use the concepts of in-order predecessor and successor to do this threading of trees. Please read through http://analgorithmaday.blogspot.com/2011/06/applications-of-traversals.html carefully.

Code

We will see the code in next section. There are two types of threaded binary tree,

• Single threaded with only in-order successors connected
• Double threaded with both in-order successors and predecessors connected

Applications of Traversals

 

Author Note

  Instead of just studying about traversals, thought of writing about various applications of traversals. So that, we can slowly move into self-balancing search trees. But, in-between will bring in some Stack/Queue and Interview Problems to break the monotonous mode of the blog. :) That gives more fun as well!!

See Also

http://analgorithmaday.blogspot.com/2011/05/construct-binary-tree-from-pre-order.html

Introduction

  Unlike normal array/linked list data structures where we traverse linearly, in a tree we have different combinations of traversals possible. Without knowing these clearly, we cannot use trees effectively. As we already know more about trees & traversals, we will see the example based introduction to where it is used.

   Pre-order traversal

      As we already know. root-left-right. If from in-order traversal, we can extract the sorted values in a BST. Similarly There are many things we can derive from pre-order as well. Many operations which needs to visit all the root nodes first use pre-order traversals.

We will see some of the following applications now,

• Tree copying
• Counting the number of nodes
• Counting the number of leaves
• Prefix notation from a expression tree

   Post-order traversal

     Post order first finishes the left-right and then visits the root. Its similar to popping elements from a tree. You take the leaves first and then the root.

  The common applications are

• Deleting a binary tree
• All stack oriented programming languages – mostly functional languages which fully works on nested functions.
• Calculator programs
• postfix notation in an expression tree – used in calculators

More concepts

   More than just traversal, there are other necessary things we need to learn clearly from these traversals.

• in-order successor/predecessor
• pre-order successor/predecessor

post-order is not having any common applications as such. But we will still see that as well

Here are some image snapshots from http://www2.hawaii.edu/~sugihara/course/ics311f08/notes/ThreadedTrees.html#S2

 

In-order successor/predecessor

1. Find the in order successor of v ? s is the in-order successor

 

2. Find the in order predecessor of v ?

 

Preorder successor and predecessor

1. Find the pre-order successor of v?

  If a left node is there, then,

If there is no left node, then,

If there is no child for v, then,

There is a concept called Threaded trees which we will see in the next articles. It’s very useful in cases where you don’t have a parent attribute part of the node.

If you have a parent link then, you have to just identify the parent of v who has a right child. This is simply because, a node without left or right ends the recursion at either left or right. So, it needs to go to the parent and check the right which is the successor. Note that, if we are ending at the right recursion, we need to go to a parent where we have a right node which is not visited.

We will see code for all these in coming articles.

Probability for Dummies

"The various possible ways are decided using permutation or combination. But what is the possibility that a arrangement can occur is called probability.. Randomness in this world requires probability to predict..!! All game plays are made with some defined principles and randomness..But how to measure at least well defined randomness so that to predict something? plainly with probability"

See Also
http://analgorithmaday.blogspot.com/2011/05/set-theorya-dummies-guide.html
http://analgorithmaday.blogspot.com/2011/05/permutations-combinations-for-dummies.html

Introduction

  In mathematics, you have deterministic or non-deterministic problems. All non-deterministic problems are called probabilistic problems. Simply, All math done with formula's are deterministic..!! Even for generating randomness, we use formula's. But note that these are non-deterministic formulas!!.. You can never say when they will fail!!.. a formula should never fail right ? :)

   The beauty of probability is to check how much we can pass/fail rather than simply pass!!.. It is sometimes just a condition over permutations/combination. That is, reason we studied about permutation & set theory well before.

 Pass/Fail means Probability.. Which means.. Pass = 1, Fail = 0. So the value of probability will lie between 0 and 1.

If probability of some event is 0, then it means it will never occur (utter fail or flop). If its 1, then it will definitely occur(success).

What is the event a probability measure? By now, you would have guessed. Random and known time interval occurring events. But we need to put some question for which we need to calculate probability (it can be either % failure or % success calculation).

The common example, flipping coin. The probability of getting tail 50%. The probability of getting head is 50%. Because the event is equally likely. You will either get a tail or head with equal probability.

But not all events are equally likely like this. Lets take an example question like this.
A couple has 2 kids and atleast one is a boy. What is the probability that both are boys?
Get the permutations of 2 kids: GG, BG, GB, BB.. 4 arrangements. Since we only care about probability of getting 2 boys, Ignore GG. Total 3 arrangements in which we find a boy out of which only 1 has both of them as boys.
So the probability is: 1/3

Concepts (Math)
Some more math about Probability Point-by-Point.

• Probability values are always between 0 and 1. So, it also like 0% possible, 100% possible
• It operates over a sample space called Experiment(E). It's nothing but the set of all the permutations. The set of permutation changes based on the kind of probability question we ask!!
• We call some thing as event if it occurs once in the experiment. Event is nothing but subset in the Experiment set. We calculate the probability of an Event in the experiment!!
• All set theory concepts applies to our experiment set(sample space). You can combine two experiments (Union). You can take common events across Experiments(Intersection). You can even take difference between two experiments.
• Disjoint sets as we already studied means empty set when you take intersection between them. Same case applies here, disjoint events means no relation between the two events.
• If you have two events and you know that always 1 event occurs, then we can use conditional probability. Conditional probability is nothing but taking intersection between the two events. (take randomness of only common events)

Some more concepts
  Sampling is a statistical concepts. Probability too works with samples. There are many more mathematics part of statistics like  differential equations and integrals. Distributions are all defined with differentials and integrals. Distributions are basically used to generalize the function. The same distributions can be used to generalize a probability function as a random variable. This is called Probability distributions.

  Whatever probability you have, the probability distribution runs from 0 to 1 and also there will be a mean value between these two numbers.
Example: If there are large number of trails of tossing the coin, then heads will be the max with probability around 50%.

Where it is used ?
Probability and expected value function is a must to know to analyze the random algorithms. We studied all this just because we are going to study randomized algorithms :).

It is known that the randomized algorithms perform really well in average case for specific problems.

More about Probability
  I would suggest referring a better math book rather than me writing about it. There are many more formulas and most used probability functions. Please refer a proper book.

Permutations & Combinations for Dummies

“I never understood concepts like permutation, combination which is quite confusing. But permutation is nothing but just a way to count all possibilities of a nested iteration!!”

Introduction

  Just take, the following nested for loops

for(int i=0;i<m; i++) {

 for(int j=0; j<n;j++) {

   cout<<i<<":"<<j<<endl;

 }

}

Simply we can tell directly the total iterations are m*n. But the traversal done by the loop with an array will be like..

REPEAT –> read the row –> read from left to right –> move to next row –> UNTIL i*j == m*n

These are the various values comes out considering m=3, n=3,

{0,0}, {0,1}, {0,2}

{1,0}, {1,1}, {1,2}

{2,0}, {2,1}, {2,2}

Keeping i, we iterate with changing symbols in j.. Doesn’t it look like Cartesian Product with a Condition?

This kind of rearrangement of numbers are necessary to traverse the array. Similarly you need rearrangement of numbers in various applications!!..

For example, say, you need to find all possible rearrangements of a shuffled 56 deck card.. There are numerous ways if you need to find the rearrangements of all the 56 cards(56!).. But if you want to know rearrangements possible when the cards are distributed within 14 people..

You just need to count 14 possible rearrangements out of 56 cards to calculate. This is where you need permutation..

To understand permutation well, you need to understand set theory!! Especially Cartesian Product!.. Learn about set theory first: http://analgorithmaday.blogspot.com/2011/05/set-theorya-dummies-guide.html

Concept

   Every multiplication can be represented with a set of additions. When you add a number that much times, you get the multiplied value. Similarly, if you have a set of 3 numbers.. how would need to find the number of ways it can be rearranged?

Strings

   If you take Cartesian product of same set k times with each set having some n symbols in it, you get strings. S^k sets with each having n items.

i.e, If the set is S, S x S x S is a 3-set product. If you have only 2 elements in it, then total you get 2^3 distinct elements as a result of this product. This count of distinct elements can be got from n^k equation. Example, Take a binary string of length 3. You have max 2 symbols possible in a binary. Total possible sets are,

000,001,010,011,100,101,110,111

Which is 2^3.

Permutation

Permuting means, simply re-arranging without missing any symbols!!.. if you want the number of rearrangements what would you do ? That’s where permutation comes into picture.

For example, saw you have a set {a,b,c}. The total number of ways, you can order this variables are,

abc, acb, bca, bac, cab,cba

Total 6 ways, the above 3 char array can be permuted. This gives as a pattern, the first element is chosen n ways, the next ignoring the first element chosen in n-1 ways, the next in n-2 ways. This means, you get n(n-1)(n-2) which is nothing but n!

If in the same above array, you just need to know the permutation of only k-elements instead of all n elements. (n is the total elements in the array).  ex: this is similar to finding the 14 cards possible rearrangements in 56 card deck..

then, the total ways are,

ab, ac, bc, ba, ca, cb

Again the same, 6 ways. But now, n, n-1, n-2 and upto n-k+1 is what required. So, The formula becomes like below,

Combination

We already saw about Strings which we get by Cartesian product of the same set and get the unique items out of the set with each symbol in an order.

Combination has the same property of getting unique items with each item at one place but ignores the order of items requirement. It considers symbols in both the set and takes out in-order uniquely!!.. i.e, You should remove transitive, symmetric symbols in a combination!!

Ex: Permutation for 2 element in a 4 element set, {a,b,c,d}

ab,ac,ad,ba,bc,bd, ca,cb,cd,da,db,dc

Total 12 sets are possible since we need to consider every re-arrangement in any order.

Combination for 2 element in a 4 element set, {a,b,c,d}

ab, ac, ad, bc,bd, cd

There are only 6 sets!!.

Formula:

Examples

Some real world example!!

http://betterexplained.com/articles/easy-permutations-and-combinations/

You have 8 players.. and 3 different cups to be won. Gold, Silver, Bronze. You give each cup to only one of the players and the cups will be given in the order, Gold->Silver->Bronze.

Gold: When you need to give Gold, you have all 8 players competing for it. So, total 8 options possible.

Silver: When you need to give Silver, you have already given Gold, so only 7 options possible

Bronze: When you need to give Bronze, you have already given Silver, so only 6 options possible.

Total ways in which the 8 players can win will be 8! ways..

But, there are only 3 cups, so Total ways in which the top 3 cups can be won, if given one-by-one in order to the persons will be: 8 * 7 * 6.

This is where Permutation comes into Picture!

If the price money is same, i.e, a Stainless steel plate. You don’t need to care about the order in which the 3 cups are given. So, its 3 cups given to 8 players. But 3 cups re-arrangement don’t need to be taken into account as all are equal. So 3! ways of arranging the cups(6 ways) are useless when it comes to just picking some 3 out-of-8.

This is combination and you get only: 8*7 ways according to the formula.

Concept behind Order Statistics

“How many times you would have required to get a kth smallest number in a set of numbers? It’s a must in many applications. Moreover, the most used is the minimum & maximum in a set of numbers. Although we have lots of O(1) data structures to get min/max, if we get numbers as an array!! we need to reorganize which still takes more time. This is where Order statistics comes into picture”

Introduction

We have seen lots of sorting methods, String analysis algorithms. As we see that the most common algorithmic methods are: sorting & searching. But there is one more, which is selection methods!!

Selecting what is max or min in a set is really simple and also the most used operation in any big programs.

Let’s see an example of a selecting problem in an interview perspective. One of the most asked question is:

Find the buying and selling price of the stock so that we maximize profit. We are given the array of stock prices. (with O(n) time and no extra space)

How would you solve this problem? There are many more related problems like selecting football team members based on the score profiles they have. In Cricket especially, the initial members considered by the board would be the players who have good economy and the computer basically prepares that list. :)

Even you can run an algorithm to find the players in the panel if you know all of their economies!!.

For this a layman way could be to use sorting and then select the top 10 or 20. But it’s not just sorting and elimination since all comparison based sorts take O(n log n) time.

What we need is O(n) time which is linear time.

So the main problem here is, How would you get k-th smallest or largest element in an array with O(n) linear time ?

Concept

What does it mean by k-th smallest element ?

If k=1, then it means the smallest element..

if k=n, then what we get would be the largest element in the array

This ‘k’ which can even decide the sorted order of the elements in the array is the base concept of Order Statistics.

Quick sort, Merge sort and almost all comparison sorts tries to find this ‘k’ of each element in the array so that we can place the elements in the right positions.

We also studied about O(n) sorting methods(counting sort, radix sort) which tries to find this ‘k’ without comparisons. :) Similar to those, we need a selecting method, if our requirement is to just find the k-th position code.

First we will see basic code of finding max & min with lesser constant time.

Code

void getRange(int *arr, int size)

{

    int min=INT_MAX;

    int max=INT_MIN;

    for(int i=0; i < size; i++)

    {

        if(arr[i] < min)

            min = arr[i];

        if(arr[i] > max)

            max = arr[i];

    }

    cout<<min<<","<<max;

}

void main()

{

    int A[] = {2,5,1,8,9,13,4,14,6};

    getRange(A, 9);

}

• The above code takes O(n) time and n comparisons as well to determine min & max
• This can be made faster!! Yes!! Avoiding constant time in a code really optimizes the code!!.. Always try remove constant time when you want optimize code!! :)
• The optimizations possible
  • Setting up initial values of max & min don’t need to at extremes
  • If the size is odd, set min & max to A[0]
  • If the size is even, compare first 2 elements, minimum goes to min & maximum goes to max
  • The above kind of initialization reduces comparisons to n-1.
  • But still we need both max & min here, so we still have 2n-2 comparisons (from n comparisons).
  • next optimization is: comparing in pairs!! which would bring down our comparisons to 3(n/2) :).. Below code does all these optimizations

void getRange(int *arr, int size)

{

    int min;

    int max;

    int start=0;

    if((size & 1) == 1) {

        min = arr[0]; 

        max = arr[0];

        start = 1;

    }

    else {

        if(arr[0] < arr[1]) {

            min = arr[0];

            max = arr[1];

        }

        else {

            min = arr[1];

            max = arr[0];

        }

        start = 2;

    }

    for(int i = start; i < size; i+=2)

    {

        int smaller;

        int larger;

        if(arr[i] < arr[i+1]) {

            smaller = arr[i];

            larger = arr[i+1];

        }

        else {

            smaller = arr[i+1];

            larger = arr[i];

        }

        if(min > smaller)

             min = smaller;

        if(max < larger)

            max = larger;

    }

    cout<<min<<","<<max;

}

void main()

{

    int A[] = {2,5,8,9,13,4,14,6};

    getRange(A, 8);

}

• Although the above code looks bigger, the comparisons are lesser and our problem domain got divided. n/2 :)
• We have some how divided the problem /2 using optimization. But more cleaner optimization possible if we know the Median!!
• We will learn about Median in next article!!

MIT Video

MIT order statistics lecture

The above video explains all algorithms in selection method. We will see all these methods in coming blog entries.

Relation between Binary Search Tree and Quicksort–MIT lecture series (hand picked)

 

Related links

http://analgorithmaday.blogspot.com/2011/02/partitioning-algorithmin-place.html

http://analgorithmaday.blogspot.com/2011/02/quick-sort.html

http://analgorithmaday.blogspot.com/2011/03/binary-search-treeintroduction.html

Introduction

   We have studied lots of logarithmic performing algorithm which internally use binary trees which is the reason for logarithmic time. But we have studied into it more, about how the performance is log n for a tree ? How does recurrence relation work? What math does Quick sort involve ?

Lets start studying some math behind algorithms with some interesting hand picked MIT lectures.

Video

Binary Search Tree and Quicksort

Explanation

   How would you create a BST using an array ?

A[n] = 3 1 8 2 6 7 5, where A is an array and n is the size of it

BST insert comes out like this,

                        3

                 1               8

                     2       6     

                         5        7

When you do an in-order traversal of the above BST, you get the sorted array..

In-order: 1 2 3 5 6 7 8

So, this means, we have to do n BST inserts and then do an in-order traversal to get a sorted array. This itself is a new sorting method named BST sort. :)

BST-Sort

   Tree T

   array A

   for i = 0 to n

      do Tree-Insert(T, A[n])

   Inorder-Traverse-Tree(T)

What is the performance of the above sort?

There are ‘n’ Tree inserts, so its O(nh) where h is the height of the tree.

and then an in-order traversal is done which is O(n) . So it will be O(2nh).

But we know that height of the tree can be computed from number of nodes in it: h = log n.

Example,

Here, the number of nodes = 7, so the height would be, =  log 7

                                                                                    =   log 2^3 (approx.)

                                                                             So, h = 3

But, take an example of an sorted(or reverse sorted) array.

A[n] = {1,2,3,4,5,6}

If you create a BST with these values, you get a tree like this,

1

    2

       3

          4

              5

                    6

What is the performance of the Tree-Insert in the above for loop? In such a case, Height of the tree is equal to the number of nodes!!

height of tree, h = log n, holds approximately only for trees which are partially balanced. So, if height equals number of nodes, you get O(n2) even for this BST sort.

Can’t you recollect that, This is matching with performance of the Quicksort algorithm ?

Yes, it is matching!! :) Quick sort gives O(n2) performance if the array is already sorted. This means, Quick sort as well creates a BST internally. Just way comparisons are made is different. This video explains that beautifully.

So to avoid that, randomized quick sort came into picture.

Randomized quick sort is the basis for all kinds of self-balancing trees!!!

If you understand how randomized quick sort work, we can understand AVL, red-black trees etc..

From the above example, its also clear that why self balancing tree is a must for getting a log n time complexity!!