定义

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。
带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

AVL和二叉搜索树区别

当初始化的数组为有序时，二叉搜索树会退化为链表,其时间复杂度为O(n),违背了树这个结构本身设计的初衷.

AVL树在每次添加节点的时候都会平衡因子检查当前节点是否平衡(左右子树的高度差是否小于1),如果平衡被打破则进行旋转操作进行调整。

和并查集类似,当插入数据增大时候，我们不能保证每次插入的数据都能尽可能的铺满树的最后一层而不是不断的增加高度,保证树的高度尽可能低。并查集通过rank保证树的高度,而AVL则通过平衡因子保证树的高度尽可能小。

自平衡操作

旋转之后一定要保证AVL的性质还在!就是中序遍历后的结果是有序的!

右旋

就个人理解而言，右旋就是需要旋转的节点顺时针旋转90°,这时候左孩子则顶替被旋节点的位置了,被旋节点成为了自己左孩子的右孩子!说起来有点绕，可以网上看看其他人做的动画,一抓一大把.

参考图
AVL2.jpg

代码

template<class K, class V>
Node<K, V>* AVL<K, V>::rightRotate(Node<K, V>* y)
{
Node<K, V>* x = y->left;
Node<K, V>* T3 = x->right;
x->right = y;
y->left = T3;
//更新height
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}

左旋

和右旋相反

代码

template<class K, class V>
Node<K, V>* AVL<K, V>::leftRotate(Node<K, V>* y)
{
Node<K, V>* x = y->right;
Node<K, V>* T3 = x->left;
x->left = y;
y->right = T3;
//更新height
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;

}

潦草的笔记

AVL1.jpg

示例代码

AVL.hpp:
# pragma once
# ifndef _AVL_HPP_
# define _AVL_HPP_
# include <iostream>
# include <string>
# include <stack>
# include <queue>
# include<list>
# include <vector>
using namespace std;
template<class K, class V> class AVL;

template <class K, class V>
class AVL
{
private:
	template <class K, class V>
	class Node {
	public:
		Node(K key, V value)
		{
			this->key = key;
			this->value = value;
			height = 1;  //初始为叶子节点
			left = NULL;
			right = NULL;
		}
	public:
		K key;
		V value;
		Node<K, V>* left;
		Node<K, V>* right;
		int height;

	};
public:
	AVL();
	inline int Size() { return size; }
	inline V get(K key) { return getNode(root, key)->value; }
	inline bool empty() { return size == 0; }
	inline void add(K key, V value) {root = add(root, key, value);}
	inline bool contains(K key) { return contains(root, key); }
	inline void preOrder() { preOrder(root); }
	void preOrderNR();
	inline void inOrder() { inOrder(root); }
	//应用:内存释放方面,先将孩子节点的内存都释放干净，再释放根节点
	inline void postOrder() { postOrder(root); }
	//层次遍历(广度优先遍历) 
	void levelOrder();
	inline V minElement()
	{
		if (!size)
			throw "BST is empty";
		return minElement(root)->value;

	}
	inline V maxElement()
	{
		if (!size)
			throw "BST is empty";
		maxElement(root)->value;
	}
	inline string toString()
	{
		string val;
		generateBSTString(root, 0, val);
		return val;
	}

	inline V removeMin()
	{
		V val = minElement();
		root = removeMin(root);
		return val;
	}
	inline V removeMax()
	{
		V val = maxElement();
		root = removeMax(root);
		return val;
	}
	void remove(K key);
	bool isBST();
	//是否为一棵平衡二叉树
	inline bool isBalanced() { return isBalanced(root); }



private:
	

	Node<K, V>* add(Node <K, V>* node, K key, V value);
	bool contains(Node <K, V>* node, K e);
	void preOrder(Node <K, V>* node);
	void inOrder(Node<K, V>* node);
	void inOrder(Node<K, V>* node, vector<K>& keys);
	void postOrder(Node<K, V>* node);
	//打印输出函数
	void  generateBSTString(Node<K, V>* node, int depth, string& str);
	string generateDepthString(int depth);
	Node<K, V>* minElement(Node<K, V>* node);
	Node<K, V>* maxElement(Node<K, V>* node);
	//任意删除节点
	Node<K, V>* remove(Node<K, V>* node, K e);
	Node<K, V>* getNode(Node<K, V>* node, K key);
	int getHeight(Node<K, V>* node);
	int getBalanceFctor(Node<K, V>* node);
	bool isBalanced(Node<K, V>* node);
	Node<K, V>* rightRotate(Node<K, V>* y);
	Node<K, V>* leftRotate(Node<K, V>* y);
private:
	Node<K, V>* root;
	int size;
};


template<class K, class V>
AVL<K, V>::AVL()
{
	root = NULL;
	size = 0;
}
template<class K, class V>
void AVL<K, V>::preOrderNR()
{
	stack<Node<K, V>*> stack;
	stack.push(root);
	while (!stack.empty())
	{
		Node<K, V>* cur = stack.top();;
		stack.pop();
		cout << cur->e << " ";
		if (cur->left != NULL)
			stack.push(cur->left);
		if (cur->right != NULL)
			stack.push(cur->right);
	}
}
//层次遍历(广度优先遍历) 
template<class K, class V>
void AVL<K, V>::levelOrder()
{
	queue<Node<K, V>*> q;
	q.push(root);
	while (!q.empty())
	{
		Node<K, V>* cur = q.front();
		q.pop();
		cout << cur->e << " ";
		if (cur->left != NULL)
		{
			q.push(cur->left);
		}
		if (cur->right != NULL)
			q.push(cur->right);
	}



}
template<class K, class V>
void AVL<K, V>::remove(K key)
{
	root = remove(root, key);
}
template<class K, class V>
bool AVL<K, V>::isBST()
{
	vector<K> keys;
	inOrder(root, keys);
	for (int i = 1; i < keys.size(); i++)
	{
		if (keys[i] < keys[i - 1])
			return false;
	}
	return true;
}
template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::add(Node <K, V>* node, K key, V value)
{
	if (node == NULL)
	{
		size++;
		return new Node<K, V>(key, value);
	}
	if (key < node->key)
		node->left = add(node->left, key, value);
	else if (key > node->key)
		node->right = add(node->right, key, value);
	else
		node->value = value;


	node->height = 1 + max(getHeight(node->left), getHeight(node->right));
	int banlanceFactor = getBalanceFctor(node);
	if (banlanceFactor > 1 && getBalanceFctor(node->left) >= 0)
	{
		//进行平衡调整右旋转LL
		return rightRotate(node);

	}
	if (banlanceFactor < -1 && getBalanceFctor(node->right) <= 0)
		return leftRotate(node);  //RR

	//LR
	if (banlanceFactor > 1 && getBalanceFctor(node->left) < 0)
	{
		node->left = leftRotate(node->left);
		return rightRotate(node);
	}
	//RL
	if (banlanceFactor < -1 && getBalanceFctor(node->right) > 0)
	{
		node->right = rightRotate(node->right);
		return leftRotate(node);
	}

	return node;
}
template<class K, class V>
bool AVL<K, V>::contains(Node <K, V>* node, K e)
{
	if (node == NULL)
		return false;
	if (node->key == e)
		return true;
	else if ( e< node->key )
		return contains(node->left, e);
	else
		return contains(node->right, e);
}
template<class K, class V>
void AVL<K, V>::preOrder(Node <K, V>* node)
{
	if (node == NULL)
		return;
	cout << node->value << " ";
	preOrder(node->left);
	preOrder(node->right);
}
template<class K, class V>
void AVL<K, V>::inOrder(Node<K, V>* node)
{
	if (node == NULL)
		return;

	inOrder(node->left);
	cout << node->value << " ";
	inOrder(node->right);
}
template<class K, class V>
void AVL<K, V>::inOrder(Node<K, V>* node, vector<K>& keys)
{
	if (node == NULL)
		return;
	inOrder(node->left, keys);
	keys.push_back(node->key);
	inOrder(node->right, keys);
}
template<class K, class V>
void AVL<K, V>::postOrder(Node<K, V>* node)
{
	if (node == NULL)
		return;

	postOrder(node->left);
	postOrder(node->right);
	cout << node->value << " ";

}
//打印输出函数
template<class K, class V>
void  AVL<K, V>::generateBSTString(Node<K, V>* node, int depth, string& str)
{
	if (node == NULL)
	{
		str += generateDepthString(depth) + "null\n";
		return;


	}

	str = str + generateDepthString(depth) + to_string(node->value) + "\n";
	generateBSTString(node->left, depth + 1, str);
	generateBSTString(node->right, depth + 1, str);
}
template<class K, class V>
string AVL<K, V>::generateDepthString(int depth)
{
	string str;
	for (int i = 0; i < depth; i++)
		str += "--";
	return str;

}
template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::minElement(Node<K, V>* node)
{
	if (node->left == NULL)
		return node;
	return minElement(node->left);
}
template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::maxElement(Node<K, V>* node)
{
	if (node->right == NULL)
		return node;
	return minElement(node->right);
}

//任意删除节点
template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::remove(Node<K, V>* node, K e)
{
	Node<K, V>* retNode;
	if (node == NULL)
		return NULL;
	if (e < node->key)
	{
		node->left = remove(node->left, e);
		retNode = node;
	}
	else if (e > node->key)
	{
		node->right = remove(node->right, e);
		retNode = node;
	}
	else
	{
		if (node->left == NULL)
		{
			Node<K, V>* rightNode = node->right;
			node->right = NULL;
			size--;
			delete node;
			node = NULL;
			retNode = rightNode;
		}
		else if (node->right == NULL)
		{
			Node<K, V>* leftNode = node->left;
			node->left = NULL;
			size--;
			delete node;
			node = NULL;
			retNode = leftNode;
		}
		else {
			//待删除节点左右节点都不为空的情况
			retNode = new Node<K,V>(*minElement(node->right));//这里很重要!! 因为后面会删除最小元素这里先保存下来


			retNode->right = remove(node->right, retNode->key);
			retNode->left = node->left;
			node->left = NULL;
			node->right = NULL;
			delete node;
			node = NULL;
			//现在retNode可能是一棵新的不平衡AVL树  
			//接下来进行自平衡调整后返回retNode
		}
	}

	if (retNode == NULL)
		return NULL;
	
		retNode->height = 1 + max(getHeight(retNode->left), getHeight(retNode->right));
		int banlanceFactor = getBalanceFctor(retNode);
		if (banlanceFactor > 1 && getBalanceFctor(retNode->left) >= 0)
		{
			//进行平衡调整右旋转LL
			return rightRotate(retNode);

		}
		if (banlanceFactor < -1 && getBalanceFctor(retNode->right) <= 0)
			return leftRotate(retNode);  //RR

		//LR
		if (banlanceFactor > 1 && getBalanceFctor(retNode->left) < 0)
		{
			retNode->left = leftRotate(retNode->left);
			return rightRotate(retNode);
		}
		//RL
		if (banlanceFactor < -1 && getBalanceFctor(retNode->right) > 0)
		{
			retNode->right = rightRotate(retNode->right);
			return leftRotate(retNode);
		}
		return retNode;

	
}
template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::getNode(Node<K, V>* node, K key)
{
	if (node == NULL)
		return NULL;
	if (key < node->key)
		return getNode(node->left, key);
	else if (key > node->key)
		return getNode(node->right, key);
	else
		return node;
}
template<class K, class V>
int AVL<K, V>::getHeight(Node<K, V>* node)
{
	if (!node)
		return 0;
	return node->height;
}
template<class K, class V>
int AVL<K, V>::getBalanceFctor(Node<K, V>* node)
{
	if (node == NULL)
		return 0;
	return getHeight(node->left) - getHeight(node->right);
}
template<class K, class V>
bool AVL<K, V>::isBalanced(Node<K, V>* node)
{
	if (node == NULL)
		return true;
	int balanceFactor = getBalanceFctor(node);
	if (abs(balanceFactor) > 1)
		return false;
	return isBalanced(node->left) && isBalanced(node->right);


}
template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::rightRotate(Node<K, V>* y)
{
	Node<K, V>* x = y->left;
	Node<K, V>* T3 = x->right;
	x->right = y;
	y->left = T3;
	//更新height 
	y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
	x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
	return x;
}

template<class K, class V>
AVL<K, V>::Node<K, V>* AVL<K, V>::leftRotate(Node<K, V>* y)
{
	Node<K, V>* x = y->right;
	Node<K, V>* T3 = x->left;
	x->left = y;
	y->right = T3;
	//更新height 
	y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
	x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
	return x;


}



# endif

写代码时的坑点：

  1. 删除节点时候的内存释放,树大小自减的时机
  2. 旋转操作时候的节点高度需要+1!
  3. 模板函数的头文件和源文件分离链接时出错:C++ 中的模板类声明头文件和实现文件分离后，如何能实现正常编译?https://www.zhihu.com/question/20630104
  4. 嵌套类的使用https://blog.csdn.net/Poo_Chai/article/details/91596538 这篇我觉得讲的很清楚了
  5. 相关博文 ：C++ 单独编译（separate compilation）与 模板的编译
    https://www.cnblogs.com/deepllz/p/9044231.html