My Math Forum  

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

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
July 16th, 2013, 06:25 AM   #1
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!

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

  My Math Forum > College Math Forum > Applied Math

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 06:39 AM
search index sigma123 Linear Algebra 0 August 7th, 2012 02:53 AM
In search of a formula. Mr. Clueless Algebra 4 May 22nd, 2012 07:09 PM
In search of a formula. Mr. Clueless Calculus 0 December 31st, 1969 04:00 PM

Copyright © 2019 My Math Forum. All rights reserved.