大家好，又见面了，我是全栈君。
问题叙述性说明：
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
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116647.html原文链接：https://javaforall.net
