1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Asymptotics for finding the successors in a Binary Tree

  1. Oct 22, 2016 #1
    Consider the algorithms :
    Code (Text):
    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 (Text):
    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.
     
  2. jcsd
  3. Oct 22, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  4. Oct 23, 2016 #3
    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.

    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
     
  5. Oct 23, 2016 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Asymptotics for finding the successors in a Binary Tree
  1. Spanning tree? (Replies: 2)

  2. Tree traversals (Replies: 1)

Loading...