Results.txt

Results for Tests on 5000 values

Depth = depth of tree, Cost = average #comparisons per search


             Ascending Order        Prefix Order        Random Order
Insert
Method       Depth      Cost     Depth      Cost     Depth      Cost

L         5000/5000      3114      13/13      12      28/28      16

A         5000/5000     1887     2954/2954     1115     28/28     16

R         204/204       62       20/20       14       23/23       13

B         2492/2492      952      1774/1774      674      27/27      15

S         4999/33       24       3977/29       23       31/1146       23

V         13/13        12        14/14        12        15/15        12


Notes (what the above indicates):
The Corse of the search is directly associate with the Depth of the tree. 
spaning tree would decrease the tree's height by the operation expect insert, so it gain better and better performance for each search. But not the random search, due to the spaning tree would bring up the neighbour of the result, while the random search is no connection between this search and next search, so it doesn't decrease the height and didn't get a good performance.
The leaf inseart in the ascending order is getting the worst tree, also in the insert at root. Random insert just the situation in between.