Undergrad Asymptotics for finding the successors in a Binary Tree

[mooncrater]

Consider the algorithms :

TREE-SUCCESSOR(x)
1. if x.right_child !=NIL
2.        return TREE-MINIMUM(x.right_child)
3. y=x.parent
4. while y != NIL and x == y.right_child
5.        x = y
6.        y = y.parent
7. return y

TREE-MINIMUM(x)
1.  while x.left_child != NIL
2.         x = x.left_child
3.return x

This algorithm finds the successor of an element in a Binary Search Tree. Here, x is the pointer to the node whose successor we have to find, and TREE-MINIMUM(x) finds the minimum in a tree whose root is x. The running time of this algorithm is $O(h)$, where h is the height of the tree.

Now the question is:

Prove that no matter what node we start at in a height-h binary search tree, k successive calls to TREE-SUCCESSOR take $O(k+h)$ time.(where h is the height of the tree.)
(clrs 12.2-8)
I've assumed that "successive calls" mean that we find the successor of the element, which came out to be the successor in the last use of TREE-SUCCESSOR.
Now, we know that in a BInary Search Tree, the left most element is the least element. Thus, starting from the leftmost element.

In this image, we've a tree of height 3. When we start from the left-most node, we get the following number of loop runs for successive elements:
$1,1,2,2,1,1,3,3,1,1,2,2,1,1$
thus we can group sub-parts of this sequence :
$(1,1,2,2,1,1),3,3,(1,1,2,2,1,1)$
For maximum number of total loop runs for k successive calls, we start from the $3,3$, i.e. the $h,h$, where h is the height of the tree.For example,
If $k=2$
then we take the $3,3$
If $k=4$ then we include the $1,1$ from either of the sides.
Similarly, if $k=8$ we take one of the $2,2$ from either of the sides.
Now, we assume that $(1,1,2,2,1,1)$ are whole blocks, and that the sequence is symmetric, so it's basically the two times of:
$3,1,1,2,2,1,1$
Thus generally, two times of:
$h,1,1,2,2,1,1,h-1,h-1,1,1,2,2,1,1,h-2,h-2,...$
Since, I halved the sequence, values of $k$ are also halved.
Thus an approximate value of this summation would be:
$$ 2 \times \frac {(k/2 -1)} {6} \times 8 + 2 \times (\frac { k/2} {8})( h + \frac { k/2} {8} -1 ) $$
Number of such blocks are : $2 \times (\frac { k/2 -1} {6}) \times 8$
as we go through the halved sequence, we used $k/2$ and multiplied by 2. Since there are 6 elements in each block and their sum is 8, therefore division by the former and multiplication by the former is done.
We tackle the $h,h-1,h-1,h-2,h-2$ by finding the number of such terms, i.e $\frac { k/2 }{8}$ and the summation of such terms is done using the summation of an Arithmetic progression.(Though only $h$ is used, instead of $2\times h$.)
This summation yields an upper bound of $O(k\times h)$ instead of $O(k+h)$.
So, where am I wrong? Any help appreciated.

 

[mfb]

Your approximation is not strong enough. In your half-tree, h occurs only once, h-1 occurs only twice, and so on. You can use this to derive a stronger bound (you can also find the precise number of steps).

Note that it is not sufficient to just consider the case where k is the whole range of the tree, O(h+k) should hold for every range in it as well.

 

[mooncrater]

Note that it is not sufficient to just consider the case where k is the whole range of the tree, O(h+k) should hold for every range in it as well.

Well, that's what I tried to do. Instead of taking the whole range of the tree, I considered a range $k$ that is less than $n$ (the total number of elements), By starting from the elements who need $h$ loop runs, in order to find their successor. And as $k$ increases, I included other elements from the left and right. This was done to find an upper bound of the summation.

Your approximation is not strong enough. In your half-tree, h occurs only once, h-1 occurs only twice, and so on. You can use this to derive a stronger bound (you can also find the precise number of steps).

But, I did count them in the second summation. Should I only count them? It's not clear to me, can you please elaborate?
Thanks for replying though. :)
Moon

 

[mfb]

I would first show that going through the full tree is O(k+h), then showing that going through more than half of the whole tree is O(k+h), then show that you can split every other sequence into those cases plus O(k+h) steps overhead.