Date: Fri, 17 Nov 2006 15:13:16 -0600 (CST) From: Mark Jacobson To: 810-080-02-FALL@uni.edu Subject: Binary Search Trees shapes and performances.... You will NOT ever have to calculate the average unsuccessful search performance for a binary search tree (BST) for 810:080. The average sucessful search performance for a BST is quite simple. 88 / \ / \ 33 99 / \ \ / \ \ 11 55 101 / / 44 What is the average successful search performance of the above BST? 1 + 2 + 2 + 3 + 3 + 3 + 4 -------------- 18 probes and there are 6 items or 6 searches that can be done, so the 18 4 answer is ------- = 2 --- probes per search (successful search average 7 7 performance). Can you do better than 2 4/7 for a BST of size 7? Yes. 17/7 or 2 3/7 is the best you could ever do for 7 items. Can you do worse? Yes. 1 + 2 + 3 + 4 + 5 + 6 + 7 28 ------------------------- = ------ 7 7 is the worst you could possibly get for a size 7 BST. 4 probes/search would be the average ( 28/7 = 4 ). http://www.cns.uni.edu/~jacobson/c080.html http://www.cns.uni.edu/~jacobson/trees.html Mark