首页 > 代码库 > 支持泛型AVL Tree的简单实现，并和STL map比较了插入，删除，查找的性能

支持泛型AVL Tree的简单实现，并和STL map比较了插入，删除，查找的性能

2024-07-01 21:30:33   218人阅读

1.问题描述：

   1）AVL tree是一种自平衡树。它通过左右子树的高度差来控制树的平衡，当高度差是不大于1的时候，认为树是平衡的。树的平衡保证了树在极端情况下
         （输入序列不够随机）的性能。很显然当左右子树高度平衡，保证了任何插入，删除，查找操作平均性能呢个，当不平衡时（有的子树很高），当
          要操作的元素在这个子树时，性能会很差；

  2）AVL tree 和Red black tree 都是一种平衡树，它的操作的时间复杂度是：O(lgN) ，N是树的节点的数目；
  3）本文实现了AVL Tree, 并和STL map做了操作性能上的比较，结果发现:AVL tree 的消耗时间稍微多一些大约比Red Black tree多出8%；
  4）本文没有封装迭代器（iterator），随后可以完成这个工作；
  5）由于表达力有限，关于AVL tree的算法详述请参见维基百科；


2：程序代码

#ifndef _AVL_TREE_H_
#define _AVL_TREE_H_

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

#include "windows.h"


#define Max( a, b ) ( (a > b )? (a):(b))

template<class T, class V, class Cmp = std::less<T> > 
class AVLTree
{
public:
	typedef struct tagAVLNode
	{
		T      key;
		V      data;
		int    height;
		tagAVLNode* leftChild;
		tagAVLNode* rightChild;

		tagAVLNode():key(), data(), height(0), 
			         leftChild(0),
					 rightChild(0)
		{

		}

		tagAVLNode( const T& _key, const V& _data ):key( _key ), 
									 data(_data),
			                         height(1),
									 leftChild(0),
									 rightChild(0)
		{

		}

		~tagAVLNode()
		{
	
			key.~T();
			data.~V();
		}


	}AVLNode, *pAVLNode;



	AVLTree():m_root(0), m_size(0)
	{

	}

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

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


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

			m_root = Clone( rhs.m_root );
		}

		return m_root;
	}

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

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


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


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

	/*
	* Find the pointer of value for given key
	*
	*/
	V*  Find( const T& _key )
	{
		return Find( m_root, _key );
	}

	/*
	* Find the min value
	*
	*/
	V& FindMin( T& key )
	{
		pAVLNode node = FindMin( m_root );
		if( node )
		{
			key = node->key;
			return node->data;
		}
	}

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


protected:


	/*
	* Clone avl tree 
	*
	*/
	pAVLNode Clone( pAVLNode root )
	{
		if( 0 == root )
			return 0;

		pAVLNode newNode = new AVLNode( root->key, root->data );
		newNode->leftChild = Clone( root->leftChild );
		newNode->rightChild = Clone( root->rightChild );

		return newNode;
	}


	/*
	*
	*
	*/
	size_t Size( pAVLNode root ) const 
	{
		if( 0 == root )
			return 0;

		return 1 + Size( root->leftChild ) + Size( root->rightChild );
	}


	/*
	*
	*
	*/
	int GetBalance( pAVLNode root )
	{
		if( 0 == root )
			return 0;

		return GetHeight( root->leftChild )  - GetHeight( root->rightChild );
	}


	/*
	*
	*
	*/
	int GetHeight( pAVLNode root )
	{
		if( 0 == root )
			return 0;

		return root->height;
	}


	/*
	* Left Rotate
	*
	*/
	pAVLNode LeftRotate( pAVLNode node )
	{
		pAVLNode y = node->rightChild;	
		node->rightChild = y->leftChild;
		y->leftChild = node;

		node->height = Max( GetHeight( node->leftChild ), GetHeight( node->rightChild ) ) + 1; // important 
		y->height = Max( GetHeight( y->leftChild ), GetHeight( y->rightChild ) ) + 1;

	
	
	
		return y;

	}


	/*
	* Right rotate
	*
	*/
	pAVLNode RightRotate( pAVLNode node )
	{
		pAVLNode y = node->leftChild;
		node->leftChild = y->rightChild;
		y->rightChild = node;

		node->height = Max( GetHeight( node->leftChild ), GetHeight( node->rightChild ) ) + 1; // important 
		y->height = Max( GetHeight( y->leftChild ), GetHeight( y->rightChild )) + 1;


		return y;
	}


	/*
	* Clear all node 
	*
	*/
	void Clear( pAVLNode root )
	{
		if( 0 == root )
			return;

		Clear( root->leftChild );
		Clear( root->rightChild );

		delete root;
		root = 0;
	}


	/*
	* Insert key value pair to avl tree
	*
	*/
	pAVLNode Insert( pAVLNode root, const T& _key, const V& _value )
	{
		if( 0 == root )
		{
			root = new AVLNode( _key, _value );
			m_size++;
			return root;
		}
		else if( root->key >  _key  )
		{
			root->leftChild = Insert( root->leftChild, _key, _value );
		}
		else if( root->key < _key )
		{
			root->rightChild = Insert( root->rightChild, _key, _value );
		}

		// update height
		root->height = Max( GetHeight( root->leftChild ), GetHeight( root->rightChild ) );

		// rebalance tree
		int balance = GetBalance( root );
		if( balance > 1 )  //left child tree more high 
		{
			if( _key < root->leftChild->key  ) //left left case
			{
				return RightRotate( root );
			}
			else if( _key > root->leftChild->key ) // left right case
			{
				root->leftChild = LeftRotate( root->leftChild );
				return RightRotate( root );
			}
			
		}
		else if( balance <- 1 )  // right child tree more high
		{
			if( _key > root->rightChild->key )  // right right case
			{
				return LeftRotate( root );
			}
			else if( _key < root->rightChild->key ) // right left case
			{
				root->rightChild = RightRotate( root->rightChild );
				LeftRotate( root );
			}
		}

		return root;
	}

	/*
	* Delete node for given key
	*
	*/
	pAVLNode Delete( pAVLNode root, const T& _key )
	{
		if( 0 == root )
			return 0;


		if( root->key < _key )
		{
			root->rightChild = Delete( root->rightChild, _key );
		}
		else if( root->key > _key )
		{
			root->leftChild = Delete( root->leftChild, _key );
		}
		else
		{
			if( root->leftChild )
			{
				if( root->rightChild ) // left right child exist case 1
				{
					pAVLNode minNode = FindMin( root->rightChild );
					root->key = minNode->key;
					root->data = http://www.mamicode.com/minNode->data;>
compile and run in visual studio 2005


联系
我们