CSC 311 DATA SRUCTURES

Definition of binary search tree.

A binary tree T is called a binary search tree if, and only if, in-order 
traversal with listing of T lists the nodes of T in an increasing order.

FACT 1

T is a binary search tree if, and only if, 

- T is empty, or

- The left and the right subtree of T are both binary search trees, and no node 
in the left subtree is larger than the root of T, and no node in the right 
subtree is smaller than the root of T.


FACT 2

The number of comparisons while successfully inserting a new value x into a 
binary search tree is equal to the level of the newly inserted node with value 
x.

In particular, the number of comperisons while building a binary searcg tree T 
as a sequence of consecutive insertions is: 

	level(1) + level(2) + ... + level(n),
	
where level(i) is the level number to which i belongs.

FACT 3

The number of comparisons while unsuccessfully searching for a value x in a 
binary search tree T is equal to the number of comparisons while successfully 
inserting x into T.

FACT 4

The number of comparisons while sucessfully searching for value x in a binary 
search tree is equal to 1 plus the number of comparisons made while inserting x 
into T, the is, one plus the depth of the first node that contains that value.