Asymptotics for finding the successors in a Binary Tree

In summary, the algorithms TREE-SUCCESSOR(x) and TREE-MINIMUM(x) are used to find the successor and minimum element in a Binary Search Tree, respectively. The time complexity for finding the successor of an element in a height-h binary search tree is O(k+h), where k is the number of successive calls and h is the height of the tree. This can be proven by considering a range of k elements starting from the leftmost element and finding the maximum number of loop runs for each successive element. The upper bound of this summation is O(kh), but a stronger bound can be derived by considering the full tree, more than half of the tree, and splitting every other sequence into these cases plus an overhead of O
  • #1
mooncrater
217
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
  • #2
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
  • #3
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
 
  • #4
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

Related to Asymptotics for finding the successors in a Binary Tree

1. What is a Binary Tree?

A Binary Tree is a type of data structure used to store data in a hierarchical manner. It consists of nodes, each of which can have at most two children nodes, referred to as the left and right child. The topmost node is called the root, and the nodes at the bottom with no children are called leaf nodes.

2. What does it mean to find successors in a Binary Tree?

In a Binary Tree, the successor of a node is the next node in the tree that comes after it in the in-order traversal. In other words, it is the node that would be visited next if we were to perform an in-order traversal of the tree starting from the given node.

3. What is the significance of asymptotics in finding successors in a Binary Tree?

Asymptotics is a way of measuring the performance of an algorithm in terms of its input size. In the case of finding successors in a Binary Tree, asymptotics can tell us how the time and space complexity of the algorithm scales with the number of nodes in the tree. This can help us determine if the algorithm is efficient and can handle larger inputs.

4. How can asymptotics be used to find successors in a Binary Tree?

One way to use asymptotics in finding successors in a Binary Tree is by analyzing the time complexity of the algorithm. For example, if the algorithm has a time complexity of O(log n), where n is the number of nodes in the tree, then we can say that it is efficient and can handle larger inputs. On the other hand, if the time complexity is O(n), then the algorithm may struggle with larger inputs.

5. Are there any other approaches to finding successors in a Binary Tree besides asymptotics?

Yes, there are other approaches to finding successors in a Binary Tree, such as using recursion or iterative algorithms. While asymptotics can give us an idea of the algorithm's efficiency, it is important to consider other factors such as the programming language used, the hardware and software environment, and the specific implementation of the algorithm when choosing an approach to finding successors in a Binary Tree.

Similar threads

Replies
4
Views
843
  • Engineering and Comp Sci Homework Help
Replies
11
Views
1K
  • Programming and Computer Science
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Replies
1
Views
2K
Replies
19
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
Replies
36
Views
6K
  • Programming and Computer Science
Replies
1
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
Back
Top