本文共 4906 字，大约阅读时间需要 16 分钟。

/* * ===================================================================================== * *       Filename:  avl_tree.h * *    Description:   * *        Version:  1.0 *        Created:  2012年02月05日 10时38分59秒 *       Revision:  none *       Compiler:  gcc * *         Author:  SphinX(),  *   Organization:   * * ===================================================================================== */#ifndef AVLTREE_H#define AVLTREE_H#include 
   
    #include 
    
     using namespace std;template 
     
      class AvlTree{	private:	struct AvlNode	{		T element;		AvlNode * left;		AvlNode * right;		int height;		AvlNode(const T & _element, AvlNode * lt, AvlNode * rt, int h = 0)			: element(_element), left(lt), right(rt), height(h) {}	};	public:	AvlTree()	{		root = NULL;		the_size = 0;	}	AvlTree(const AvlTree & rhs)	{		if (this != &rhs)		{			clear();			root = clone(rhs->root);		}	}	~AvlTree()	{		clear();	}		const AvlTree & operator = (const AvlTree & rhs)	{		if (this != &rhs)		{			clear();			root = clone(rhs->root);			the_size = rhs.the_size;		}		return *this;	}		int size() const	{		return the_size;	}	bool empty() const	{		return size() == 0;	}	bool contains(const T & x) const	{		return contains(x, root);	}	const T & findMin() const	{		return findMin(root)->element;	}	const T & findMax() const	{		return findMax(root)->element;	}	void clear()	{		clear(root);		the_size = 0;		return ;	}	void insert(const T & x)	{		insert(x, root);		the_size++;		return ;	}	void remove(const T & x)	{		remove(x, root);		the_size--;		return ;	}	private:	int height(AvlNode * t)	{		return NULL == t ? -1 : t->height;	}		bool contains(const T & x, AvlNode * t) const	{		while (t != NULL)		{			if (x < t->element)			{				t = t->left;			}			else if (t->element < x)			{				t = t->right;			}			else			{				return true;			}		}		return false;	}	AvlNode * findMin(AvlNode * t) const	{		if (t != NULL)		{			while (t->left != NULL)			{				t = t->left;			}		}		return t;	}	AvlNode * findMax(AvlNode * t) const	{		if (t != NULL)		{			while (t->right != NULL)			{				t = t->right;			}		}		return t;	}		AvlNode * clone(AvlNode * t)	{		if (NULL == t)		{			return NULL;		}		return new AvlNode(t->element, clone(t->left), clone(t->right));	}	void clear(AvlNode * & t)	{		if (t != NULL)		{			clear(t->left);			clear(t->right);			delete t;		}		t = NULL;		return ;	}	void rotateWithLeftChild(AvlNode * & k2)	{		AvlNode * k1 = k2->left;		k2->left = k1->right;		k1->right = k2;		k2->height = max(height(k2->left), height(k2->right)) + 1;		k1->height = max(height(k1->left), k2->height) + 1;		k2 = k1;		return ;	}	void rotateWithRightChild(AvlNode * & k2)	{		AvlNode * k1 = k2->right;		k2->right = k1->left;		k1->left = k2;		k2->height = max(height(k2->left), height(k2->right)) + 1;		k1->height = max(height(k1->right), k2->height) + 1;		k2 = k1;		return ;	}	void doubleWithLeftChild(AvlNode * & k3)	{		rotateWithRightChild(k3->left);		rotateWithLeftChild(k3);		return ;	}	void doubleWithRightChild(AvlNode * & k3)	{		rotateWithLeftChild(k3->right);		rotateWithRightChild(k3);		return ;	}	void insert(const T & x, AvlNode * & t)	{		if (NULL == t)		{			t = new AvlNode(x, NULL, NULL);			return ;		}		else if (x < t->element)		{			insert(x, t->left);			if (height(t->left) - height(t->right) == 2)			{				if (x < t->left->element)				{					rotateWithLeftChild(t);				}				else				{					doubleWithLeftChild(t);				}			}		}		else if (t->element < x)		{			insert(x, t->right);			if (height(t->right) - height(t->left) == 2)			{				if (t->right->element < x)				{					rotateWithRightChild(t);				}				else 				{					doubleWithRightChild(t);				}			}		}		t->height = max(height(t->left), height(t->right)) + 1;		return ;	}	void remove(const T & x, AvlNode * & t)	{		if (NULL == t)		{			return ;		}		if (x < t->element)		{			remove(x, t->left);			if (height(t->right) - height(t->left) == 2)			{				AvlNode * rt = t->right;				if (height(rt->right) > height(rt->left))				{					rotateWithRightChild(t);				}				else				{					doubleWithRightChild(t);				}			}			else			{				t->height = max(height(t->left), height(t->right)) + 1;			}		}		else if (t->element < x)		{			remove(x, t->right);			if (height(t->left) - height(t->right) == 2)			{				AvlNode * lt = t->left;				if (height(lt->left) > height(lt->right))				{					rotateWithLeftChild(t);				}				else				{					doubleWithLeftChild(t);				}			}			else			{				t->height = max(height(t->left), height(t->right)) + 1;			}		}		else		{			if (t->left != NULL && t->right != NULL)			{				if (height(t->left) < height(t->right))				{					t->element = findMin(t->right)->element;					remove(t->element, t->right);				}				else				{					t->element = findMax(t->left)->element;					remove(t->element, t->left);				}			}			else			{				AvlNode * oldNode = t;				t = ((NULL == t->left) ? t->right : t->left);				delete oldNode;				oldNode = NULL;			}		}		return ;	}	AvlNode * root;	int the_size;};#endif
     
    
   

转载地址：http://ribqb.baihongyu.com/