泛型Binary Search Tree实现，And和STL map比较的经营业绩

问题叙述性说明：

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 = minNode->value; Delete( root->rightNode, minNode->key ); } else { pBSTNode node = root; root = root->leftNode ? root->leftNode: root->rightNode; delete node; node = 0; m_size--; //very important } } } /* * Implement find operation * */ pBSTNode Find( pBSTNode root, const T& key ) { if( 0 == root ) return root; if( root->key < key ) { return Find( root->rightNode, key ); } else if( root->key > key ) { return Find( root->leftNode, key ); } else { return root; } } /* * Find implement no recursive * */ pBSTNode FindUtil( pBSTNode root, const T& key ) { if( 0 == root ) return root; pBSTNode cur = root; while( root ) { cur = root; if( root->key < key ) { root = root->rightNode; } else if( root->key > key ) { root = root->leftNode; } else { break; } } if( cur && cur->key == key ) return cur; return 0; } /* * Implement find max element operation * */ pBSTNode FindMax( pBSTNode root ) { if( 0 == root ) return root; while( root->rightNode ) { root = root->rightNode; } return root; } /* * Implement find min element operation * */ pBSTNode FindMin( pBSTNode root ) { if( 0 == root ) return root; while( root->leftNode ) { root = root->leftNode; } return root; } /* * Implement inorder traversal * */ void InorderVisitor( pBSTNode root, void (*visitor)( const T&, const V& ) ) { if( 0 == root ) return; InorderVisitor( root->leftNode, visitor ); visitor( root->key, root->value ); InorderVisitor( root->rightNode, visitor ); } /* * Implement preorder traversal * */ void PreOrderVisitor( pBSTNode root, void (*visitor)( const T&, const V& ) ) { if( 0 == root ) return; visitor( root->key, root->value ); InorderVisitor( root->leftNode, visitor ); InorderVisitor( root->rightNode, visitor ); } /* * Implement postorder traversal * */ void PostOrderVisitor( pBSTNode root, void (*visitor)( const T&, const V& ) ) { if( 0 == root ) return; InorderVisitor( root->leftNode, visitor ); InorderVisitor( root->rightNode, visitor ); visitor( root->key, root->value ); } protected: pBSTNode m_root; size_t m_size; }; /* * Test STL map * */ void TestSTLMapBST() { const int Len = 200000; //int key[Len]; //int value[Len]; int* key = new int[Len]; int* value = new int[Len]; for( int i = 0; i < Len; i++ ) { key[i] = i; value[i] = i; } std::random_shuffle( key, key + Len ); std::random_shuffle( value, value + Len ); unsigned long start = GetTickCount(); std::map<int, int> treeObj; for( int i = 0; i < Len; i++ ) { treeObj.insert( std::make_pair( key[i], value[i] ) ); } size_t count = treeObj.size(); for( int i = 0; i < Len; i++ ) { std::map<int, int>::iterator iter = treeObj.find( key[i] ); assert( iter != treeObj.end() ); assert( iter->second == value[i] ); } for( int i = 0; i < Len; i++ ) { if( !(i % 15) ) { treeObj.erase( key[i] ); std::map<int, int>::iterator iter = treeObj.find( key[i] ); assert( iter == treeObj.end() ); } } unsigned long interval = GetTickCount() - start; printf( " STL map consume time is %d \n", interval ); delete [] key; delete [] value; } /* * vistior function for output information when traversal tree * */ template<class T, class V> void Visitor( const T& key, const V& value ) { std::cout << "key: " << key << "," <<"value: " << value << std::endl; } /* * unit test * */ void TestBST() { const int Len = 200000; //int key[Len]; //int value[Len]; int* key = new int[Len]; int* value = new int[Len]; for( int i = 0; i < Len; i++ ) { key[i] = i; value[i] = i; } std::random_shuffle( key, key + Len ); std::random_shuffle( value, value + Len ); unsigned long start = GetTickCount(); BinarySearchTree<int, int> treeObj; for( int i = 0; i < Len; i++ ) { treeObj.Insert( key[i], value[i] ); } for( int i = 0; i < Len; i++ ) { int* val = treeObj.Find( key[i] ); assert( *val == value[i] ); } int minKey = -1; int* minValue = treeObj.FinMin( minKey ); assert( minKey == 0 ); int maxKey = -1; int* maxValue = treeObj.FindMax( maxKey ); assert( maxKey == Len - 1 ); size_t size = treeObj.Size(); assert( size == Len ); int flagCount = 0; for( int i = 0; i < Len; i++ ) { if( !(i % 15) ) { treeObj.Delete( i ); int* val = treeObj.Find( i ); assert( !val ); flagCount++; } } unsigned long interval = GetTickCount() - start; printf( " binary search tree consume time is %d \n", interval ); size = treeObj.Size(); size_t count = treeObj.GetSize(); BinarySearchTree<int, int> newTreeObj; for( int i = 0; i < 10; i++ ) { newTreeObj.Insert( key[i], value[i] ); } treeObj = newTreeObj; newTreeObj.Clear(); std::cout<< "begin inorder traversal " << std::endl; treeObj.InorderVisitor( Visitor<int, int> ); std::cout<< "begin postorder traversal " << std::endl; treeObj.PostOrderVisitor( Visitor<int, int> ); std::cout<< "begin preorder traversal " << std::endl; treeObj.PreOrderVisitor( Visitor<int, int> ); treeObj.Clear(); delete [] key; delete [] value; } void TestBSTSuite() { TestSTLMapBST(); TestBST(); } #endif