问题描述：

1.binary search tree是一种排序二叉树。对于key值，当前节点的小于左孩子的大于右孩子的；

 2.binary search tree不是自平衡树。所以，当插入数据不是很随机时候，性能会接近O(N)，N是树中节点数目;

 3.理想状态下，时间复杂度是O(lgN), N是树中节点的数目；

4.下面给出一个简单的实现，并比较其和STL map的性能，一样的操作，大约耗时为STL map 的2/3；

代码如下：

#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_

#include <functional>
#include <algorithm>
#include <iostream>
#include <map>

#include "windows.h"


template<class T, class V, class Cmp = std::less<T> > 
class BinarySearchTree
{
public:

	// node struct
	typedef struct tagBSNode
	{
		T    key;
		V    value;
		tagBSNode*  leftNode;
		tagBSNode*  rightNode;

		tagBSNode():key(), value(),
			        leftNode(0),
					rightNode(0)
		{

		}

		tagBSNode( const T& _key, const V& _value ):key(_key), 
			                                        value(_value),
													leftNode(0),
													rightNode(0)
		{

		}

	}BSTNode, *pBSTNode;


	/*
	* Constructor
	*
	*/
	BinarySearchTree():m_root(0), m_size(0)
	{

	}

	/*
	* Copy constructor
	*
	*/
	BinarySearchTree( const BinarySearchTree& rhs )
	{
		m_root = Clone( rhs.m_root );
		m_size = rhs.m_size;
	}

	/*
	* Destructor
	*
	*/
	~BinarySearchTree()
	{
		Clear();
	}

	/*
	* assignment operator overload
	*
	*/
	BinarySearchTree& operator = ( const BinarySearchTree& rhs )
	{
		if( this != &rhs )
		{
			Clear();

			m_root = Clone( rhs.m_root );
			m_size = rhs.m_size;
		}

		return *this;
	}

	/*
	* Clear all node 
	*
	*/
	void Clear()
	{
		Clear( m_root );
		m_size = 0;
	}

	/*
	* check whether or not empty
	*
	*/
	bool IsEmpty() const 
	{
		return m_size == 0;
	}

	/*
	* Retrieve the number of node in tree
	*
	*/
	size_t Size() const 
	{
		return m_size;
	}

	/*
	*
	*
	*/
	size_t GetSize() const  // only for test
	{
		return Size( m_root );
	}

	/*
	* Insert key and value pair to tree
	*
	*/
	void Insert( const T& key, const V& value )
	{
		Insert( m_root, key, value );
	}

	/*
	* Delete node from tree for given key
	*
	*/
	void Delete( const T& key )
	{
		Delete( m_root, key );
	}

	/*
	* Find element from tree for given key
	*
	*/
	V* Find( const T& key )
	{
		pBSTNode node = Find( m_root, key );
		if( node )
			return &node->value;

		return 0;
	}

	/*
	* Find the the element of max key 
	*
	*/
	V* FindMax( T& key )
	{
		pBSTNode node = FindMax( m_root );
		if( node )
		{
			key = node->key;
			return &node->value;
		}

		return 0;
	}

	/*
	* Find the the element of min key 
	*
	*/
	V* FinMin( T& key )
	{
		pBSTNode node = FindMin( m_root );
		if( node )
		{
			key = node->key;
			return &node->value;
		}

		return 0;
	}

	/*
	* inoder traversal
	*
	*/
	void InorderVisitor( void (*visitor)( const T&, const V& ) )
	{
		InorderVisitor( m_root, visitor );
	}

	/*
	* preoder traversal
	*
	*/
	void PreOrderVisitor( void (*visitor)( const T&, const V&  )  )
	{
		PreOrderVisitor( m_root, visitor );
	}

	/*
	* postoder traversal
	*
	*/
	void PostOrderVisitor( void (*visitor)( const T&, const V& ) )
	{
		PostOrderVisitor( m_root, visitor );
	}

protected:

	/*
	* Implement clone operation
	*
	*/
	pBSTNode Clone( pBSTNode root )
	{
		if( 0 == root )
			return root;

		pBSTNode node = new BSTNode( root->key, root->value );
		node->leftNode = Clone( root->leftNode );
		node->rightNode = Clone( root->rightNode );

		return node;
	}

	/*
	* Implement clear opreation
	*
	*/
	void Clear( pBSTNode& root )
	{
		if( 0 == root )
			return;

		Clear( root->leftNode );
		Clear( root->rightNode );

		delete root;
		root = 0;

	}


	/*
	* Retrieve the number of node by way of recursive
	*
	*/
	size_t Size( pBSTNode root ) const 
	{
		if( 0 == root )
			return 0;

		return 1 + Size( root->leftNode ) + Size( root->rightNode );
	}

	/*
	* Implement insert operation
	*
	*/
	void Insert( pBSTNode& root,const T& key, const V& value )
	{
		if( 0 == root )
		{
			root = new BSTNode( key, value );
			m_size++;
		}

		if( root->key < key )
		{
			Insert( root->rightNode, key, value );
		}
		else if( root->key > key )
		{
			Insert( root->leftNode, key, value );
		}
	}

	/*
	* Implement delete operation
	*
	*/
	void Delete( pBSTNode& root, const T& key )
	{
		if( 0 == root )
			return;

		if( root->key < key )
		{
			Delete( root->rightNode, key );
		}
		else if( root->key > key )
		{
			Delete( root->leftNode, key );
		}
		else
		{
			if( root->leftNode && root->rightNode )
			{
				pBSTNode minNode = FindMin( root->rightNode );
				root->key  = minNode->key;
				root->value = http://www.mamicode.com/minNode->value;>

泛型的Binary Search Tree的实现，并与STL map进行操作性能上的比较