数据结构-AVL树

为什么需要AVL树，以树的结构插入或删除大量随机数据时，有可能会导致树的一边轻一边重， 例如极端情况插入依次123456时，树就与链表无异了，Ologn的查找效率也变成了On;

AVL树的特性：左右子树高度差最大为1，为了维持这个特性，在插入和删除操作时就需要旋转；

旋转规则：当插入位置为对左儿子的左子树进行插入则左单旋，左儿子的右子树时左双旋， 右儿子则镜像；

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
template<typename T>
class AVLTree{
public:
	AVLTree();
	~AVLTree();
	AVLTree(const AVLTree &t);
	AVLTree& operator=(const AVLTree &t);

	void insert(const T &t);
	void remove(const T &t);
	void clear();
	bool contains(const T &t) const;
	bool empty() const;

	void inorder();
	void levelorder();

private:
    struct Node{
        T val;
        int height;
        Node *left;
        Node *right;
        Node(T x, Node *l = NULL, Node *r = NULL, int h = 0)
			: val(x), height(h), left(l), right(r){};
    };
    Node *root;

	Node *&findMax(Node *&k);
	Node *&findMin(Node *&k);

	int height(Node *&k) const;
	void rotateWithLeft(Node *&k1);
	void doubleWithLeft(Node *&k3);
	void rotateWithRight(Node *&k2);
	void doubleWithRight(Node *&k3);

	void insert(const T &t, Node *&k);
	void remove(const T &t, Node *&k);
	void clear(Node *&k);
	bool contains(const T &t, Node *const &k) const;
	void inorder(Node *&k);

	Node* copy_tree(Node *t);
};
/***构造***/
template<typename T>
AVLTree<T>::AVLTree()
 : root(NULL)
 {

 }
/***析构****/
template<typename T>
AVLTree<T>::~AVLTree()
{
	clear();
}
/**拷贝构造****/
template<typename T>
AVLTree<T>::AVLTree(const AVLTree &t)
{
	root = copy_tree(t.root);
}
/***赋值重载****/
template<typename T>
AVLTree<T>& AVLTree<T>::operator=(const AVLTree &t)
{
	if(this != &t)
	{
		AVLTree<T> tmp(t);
		swap(root, tmp.root);
	}
	return *this;
}
/****插入函数用户接口***/
template<typename T>
void AVLTree<T>::insert(const T &t)
{
	insert(t, root);
}
/****删除函数用户接口****/
template<typename T>
void AVLTree<T>::remove(const T &t)
{
	remove(t, root);
}
/***清空树***/
template<typename T>
void AVLTree<T>::clear()
{
	clear(root);
}
/***判断是否包含某元素***/
template<typename T>
bool AVLTree<T>::contains(const T &t) const
{
	return contains(t, root);
}
/***判空****/
template<typename T>
bool AVLTree<T>::empty() const
{
	return root == NULL;
}
/***中序遍历****/
template<typename T>
void AVLTree<T>::inorder()
{
	inorder(root);
}
/***层序遍历****/
template<typename T>
void AVLTree<T>::levelorder()
{
    if(!root)
        return ;
	int curlevel = 0;
	queue<pair<Node *, int> > q;
	q.push(make_pair(root, curlevel));
	while(!q.empty())
	{
		pair<Node*, int> tmp = q.front();
		q.pop();
		if(tmp.second > curlevel)
		{
			cout << endl;
			curlevel = tmp.second;
		}
		cout << tmp.first->val << " ";
		if(tmp.first->left)
			q.push(make_pair(tmp.first->left, curlevel+1));
		if(tmp.first->right)
			q.push(make_pair(tmp.first->right, curlevel+1));
	}
}
/***返回最大值节点即最右节点****/
template<typename T>
typename AVLTree<T>::Node*& AVLTree<T>::findMax(Node *&k)
{
	if(k->right)
		return findMax(k->right);
	else
		return k;
}
/****返回最小值节点即最左节点****/
template<typename T>
typename AVLTree<T>::Node*& AVLTree<T>::findMin(Node *&k)
{
	if(k->left)
		return findMax(k->left);
	else
		return k;
}
/****返回节点高度NULL为-1****/
template<typename T>
int AVLTree<T>::height(Node *&k) const
{
	return k==NULL ? -1 : k->height;
}
/****左单旋即逆时针旋转****/
template<typename T>
void AVLTree<T>::rotateWithLeft(Node *&k1)
{
	Node *k2 = k1->left;
	k1->left = k2->right;
	k2->right = k1;

	k1->height = max(height(k1->left), height(k1->right))+1;
	k2->height = max(height(k2->left), k1->height)+1;

	k1 = k2;
}
/***左双旋*****/
template<typename T>
void AVLTree<T>::doubleWithLeft(Node *&k3)
{
	rotateWithRight(k3->left);
	rotateWithLeft(k3);
}
/***右单旋，顺时针旋转****/
template<typename T>
void AVLTree<T>::rotateWithRight(Node *&k2)
{
	Node *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;
}
/***右双旋*****/
template<typename T>
void AVLTree<T>::doubleWithRight(Node *&k3)
{
	rotateWithLeft(k3->right);
	rotateWithRight(k3);
}
/****递归插入并保持平衡****/
template<typename T>
void AVLTree<T>::insert(const T &t, Node *&k)
{
	if(k == NULL)
		k = new Node(t);
	else if(t < k->val)
	{
		insert(t, k->left);
		if(height(k->left)-height(k->right) == 2)
		{
			if(t < k->left->val)
				rotateWithLeft(k);
			else
				doubleWithLeft(k);
		}
	}
	else if(t > k->val)
	{
		insert(t, k->right);
		if(height(k->right)-height(k->left) == 2)
		{
			if(t > k->right->val)
				rotateWithRight(k);
			else
				doubleWithRight(k);
		}
	}

	k->height = max(height(k->left), height(k->right))+1;
}
/****递归删除保持平衡****/
template<typename T>
void AVLTree<T>::remove(const T &t, Node *&k)
{
	if(k == NULL)
		return ;
	else if(t < k->val)
	{
		remove(t, k->left);
		if(height(k->right)-height(k->left) == 2)
		{
			Node *tmp = k->right;
			if(height(tmp->left) <= height(tmp->right))
				rotateWithRight(k);
			else
				doubleWithRight(k);
		}
	}
	else if(t > k->val)
	{
		remove(t, k->right);
		if(height(k->left)-height(k->right) == 2)
		{
			Node *tmp = k->left;
			if(height(tmp->right) <= height(tmp->left))
				rotateWithLeft(k);
			else
				doubleWithLeft(k);
		}
	}
	else{
		if(k->left && k->right)
		{
			if(height(k->left) > height(k->right))
			{
				Node *&tmp = findMax(k->left);
				k->val = tmp->val;
				remove(tmp->val, tmp);
			}
			else{
				Node *&tmp = findMin(k->right);
				k->val = tmp->val;
				remove(tmp->val, tmp);
			}
		}
		else{
			Node *tmp = k;
			k = k->left ? k->left : k->right;
			delete tmp;
		}
	}
}
/**递归清空树***/
template<typename T>
void AVLTree<T>::clear(Node *&k)
{
	if(k)
	{
		clear(k->left);
		clear(k->right);
		delete k;
	}
	k = NULL;
}
/***递归检测是否包含某元素****/
template<typename T>
bool AVLTree<T>::contains(const T &t, Node *const &k) const
{
	if(k == NULL)
		return false;
	else if(t < k->val)
		return contains(t, k->left);
	else if(t > k->val)
		return contains(t, k->right);
	else
		return true;
}
/***中序****/
template<typename T>
void AVLTree<T>::inorder(Node *&t)
{
	if(t)
	{
		inorder(t->left);
		cout << t->val << " ";
		inorder(t->right);
	}
}
/***递归深拷贝****/
template<typename T>
typename AVLTree<T>::Node* AVLTree<T>::copy_tree(Node *k)
{
	if(k == NULL)
		return NULL;
	return new Node(k->val, copy_tree(k->left), copy_tree(k->right));
}

int main()
{
    int a[16] = {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
    AVLTree<int> mytree;
    for(auto i : a)
        mytree.insert(i);
    mytree.levelorder();
    cout << endl;
    //mytree.remove(4);
    mytree.remove(6);
    mytree.remove(5);
    mytree.levelorder();
    cout << endl;
    mytree.inorder();
    cout << endl;
    cout << mytree.empty() << endl;
    cout << mytree.contains(8) << endl;
    return 0;
}