My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
July 16th, 2013, 05:25 AM   #1
Newbie
 
Joined: Jul 2013

Posts: 1
Thanks: 0

Average search cost of an unsuccessful search in a BST?

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

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

Prove that

and just for a reminder, , where is the external path length of a binary search tree.

Thanks a lot for your help!

REMINDER:
Attached Images
File Type: jpg mathforum.jpg (22.9 KB, 160 views)
flexdec is offline  
 
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
average, bst, cost, search, unsuccessful



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Article search sigma123 Math Books 1 October 4th, 2012 05:39 AM
search index sigma123 Linear Algebra 0 August 7th, 2012 01:53 AM
In search of a formula. Mr. Clueless Algebra 4 May 22nd, 2012 06:09 PM
In search of a formula. Mr. Clueless Calculus 0 December 31st, 1969 04:00 PM





Copyright © 2018 My Math Forum. All rights reserved.