Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By johng

Math Help - Internal and external path length of a binary search tree

  1. #1
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Internal and external path length of a binary search tree

    I'm really bugging on a question I hope somebody here can help me!

    If we note by S_N the average search cost in the case of a successful search in a binary search tree and U_S in the case of an unsuccessful search, we can say that
    S_N = I/N, where I is the internal path length and N is the number of nodes in the tree.

    Prove that U_N=\frac{N}{N+1}(S_N+2).

    and just for a reminder, E =I+2N, where E is the external path length of a binary search tree.

    REMINDER:
    Internal and external path length of a binary search tree-mathforum.jpg
    Last edited by Flexdec; July 15th 2013 at 05:17 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    627
    Thanks
    253

    Re: Internal and external path length of a binary search tree

    Hi,
    What do you mean by average cost? The usual idea is to count the number of key comparisons in a search. I'm taking my answer directly from D. E. Knuth, Vol.3, Searching and Sorting, p. 410. I have 100% confidence in this source. So if you let SN be the average number of comparisons in a successful search of a binary search tree with N nodes (assuming each of the N keys is equally likely as a search argument), then

    S_N=1+{I\over N} -- this is 1 more than your formula??

    Next assume that an unsuccessful search is for a key that is equally likely to be in any of the N+1 intervals determined by the N keys of the tree. Then

    U_N={E\over N+1}={I+2N\over N+1}={N\over N+1}(S_N-1+2)={N\over N+1}(S_N+1)

    If you read a few more pages in Knuth, you get the nice formula (assuming the tree was built initially by inserting the N keys in random order):

    S_N=2(1+{1\over N})H_N-3 where H_N is the Nth partial harmonic sum.
    Thanks from Flexdec
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2013
    From
    montreal
    Posts
    10

    Re: Internal and external path length of a binary search tree

    Thanks!! I guess my teacher just forgot about the +1 haha
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Binary Tree Question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 5th 2011, 07:40 PM
  2. Replies: 0
    Last Post: December 8th 2010, 07:48 AM
  3. Working with external and internal direct sums
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 6th 2010, 01:18 PM
  4. Induction for binary tree.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 30th 2010, 11:17 AM
  5. Binary Search Algorithm
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 11th 2006, 10:57 PM

Search Tags


/mathhelpforum @mathhelpforum