I Asymptotics for finding the successors in a Binary Tree

AI Thread Summary
The discussion focuses on the efficiency of the TREE-SUCCESSOR algorithm for finding successors in a Binary Search Tree, emphasizing its time complexity of O(h) for a single call. It explores the implications of making k successive calls, proposing that the total time complexity is O(k + h). Participants debate the accuracy of an approximation method used to derive this complexity, with suggestions to refine the approach by considering the distribution of nodes and their respective heights more precisely. The conversation highlights the need for a robust proof that holds for any range of nodes, not just the entire tree. Ultimately, the goal is to clarify the assumptions and calculations to establish a stronger upper bound for the algorithm's performance.
mooncrater
Messages
215
Reaction score
18
Consider the algorithms :
Code:
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

Code:
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.
FullBinary.jpg

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.
 
Mathematics news on Phys.org
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.
 
  • Like
Likes mooncrater
mfb said:
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.

mfb said:
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
 
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.
 
  • Like
Likes mooncrater
Thread 'Video on imaginary numbers and some queries'
Hi, I was watching the following video. I found some points confusing. Could you please help me to understand the gaps? Thanks, in advance! Question 1: Around 4:22, the video says the following. So for those mathematicians, negative numbers didn't exist. You could subtract, that is find the difference between two positive quantities, but you couldn't have a negative answer or negative coefficients. Mathematicians were so averse to negative numbers that there was no single quadratic...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Thread 'Unit Circle Double Angle Derivations'
Here I made a terrible mistake of assuming this to be an equilateral triangle and set 2sinx=1 => x=pi/6. Although this did derive the double angle formulas it also led into a terrible mess trying to find all the combinations of sides. I must have been tired and just assumed 6x=180 and 2sinx=1. By that time, I was so mindset that I nearly scolded a person for even saying 90-x. I wonder if this is a case of biased observation that seeks to dis credit me like Jesus of Nazareth since in reality...
Back
Top