Analysis of Binary Search Tree

For analysis of time complexity for operations on BST we explore the following questions.

What could be a worst-case scenario?, and
What could be a best-case scenario?

Search is the critical first step any operation including both insertion and deletion on a binary search tree. A successful or unsuccessful search depends on the length of the tree path from the root to the farthest leaf node. A right-skewed or a left-skewed BSTs exhibit pathological cases for insertions and deletions. These cases occur as follows:

Perform an ascending sequence of n insertions on an initially empty BST it generates a right-skewed tree.
Perform a descending sequence of n insertions on an initially empty BST it generates a left-skewed tree.

A completely skewed tree requires a time of O(n) for any operation. On the other hand, an operation on a balanced binary search tree takes O(log n). Therefore,

A right-skewed or a left-skewed BST provides the worst-case scenario, and
A balanced BST gives a best-case scenario for BSTs.

When we have a random input source, all distributions of the values are equally likely. So, it is important to analyze the average case time complexity. The average case analysis of BST depends on the average path length traversed on a BST for performing an operation. We begin with an example. Consider the tree shown below. The total internal path length of the tree is 15.

The first problem we need to address is:

How to compute the internal path length of a BST in a dynamic situation where an operation can choose to traverse any section of a BST?

We capture such a dynamic situation by considering the possibilities of insertions and deletions happening in any possible order. We use the following assumptions:

P(n): the average path length of a node in a BST with n nodes
Initial values are: P(0) = 0 and P(1)=1.
x: is the root of the BST or the first node to be inserted
x: may equally likely to be 1st, 2nd, 3rd or nth element in the input

Now consider ith insertion for a fixed i for i = 0, 1, 2, …, n-1. The configuration of BST at this point is illustrated in the figure below:

Consider how the subsequent insertion occurs.

The root node will be probed in any case.
If left subtree of the root is probed for i+1 insertion then path length is 1+P(i)
If right subtree of the root is probed for i+1 insertion then path length is 1+P(n-1-i)
The probability of searching any element is 1/n.

So the average number of probes for i+1the insertion would be:

$\begin{array}{ll} P(n,i) & = \frac{1}{n} + \frac{i}{n}(1 + P(i)) + \frac{(n-i-1)}{n}(1+P(n-i-1))\\ \\ & = \frac{1 + i + n - i - 1}{n} + \frac{i}{n}P(i) + \frac{n-i-1}{n} P(n-i-1)\\\\ & = 1 + \frac{i}{n}P(i) + \frac{n-i-1}{n}P(n-i-1)\end{array}$

The average value is obtained by letting i to be any of the n elements. So, the average value is given by the expression:

$P(n)=\frac{1}{n}\sum_i P(n,i)$

In the above equation, we use the expression found earlier to replace P(n,i). Since the pair of sums for P(i) and P(n,i) are symmetric, the simplified expression for P(n) becomes:

$P(n)= 1+\frac{2}{n^2}\sum_i iP(i)$

Now apply induction to prove $P(n) = O(\log n)$ . The induction requires a base case, an induction hypothesis and a proof for the induction step.

Base case: We know P(1) = 1, and evaluation of the expression for n=1 gives us:

$1+\frac{2}{n^2}\sum_i iP(i) = 1$

Induction hypothesis: Assume

$1 + 4\log i$

for any i less than n.

Proof of induction step: With the induction hypothesis in mind we apply to terms of the sum in the expression for P(n) and simplify it further to obtain:

$\begin{array}{ll} P(n) & = \frac{1}{n} \sum_{0}^{n-1} P(n, i)\\\\ & = \frac{1}{n}\sum_{0}^{n-1}\left(1+ \frac{i}{n} P(i) + \frac{n-i-1}{n} P(n-i-1)\right)\\\\&= 1 + \frac{1}{n^2}\sum_{i=0}^{n-1} \left(iP(i) + (n-i-1) P(n-i-1)\right)\\\\&= 1+ \frac{2}{n^2}\sum_{i=0}^{n-1} iP(i)\end{array}$

Consider the sum on the right-hand side of previous inequality and apply simplification:

$\begin{array}{ll} \sum_{i=1}^{n-1} i\log i &= \sum_{i=1}^{\lceil\frac{n}{2}\rceil-1} i\log i + \sum_{\lceil\frac{n}{2}\rceil}^{n-1} i\log i\\\\ & \le \sum_{i=1}^{\lceil\frac{n}{2}\rceil-1} i\log\frac{n}{2} + \sum_{\lceil\frac{n}{2}\rceil}^{n-1} i\log n\\\\ & \le\frac{n^2}{8}\log\frac{n}{2} + \frac{3n^2}{8}\log n\end{array}$

Replacing the sum by the final expression, we finally get

$P(n) = 1 + 4\log n$

Therefore, the average case complexity of an operation on BST is of the order of log n

Back to Index