数据结构——AVL树

一、AVL树

1.概念

        二叉搜索树虽然可以缩短查找效率，单如果数据有序或解决有序，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1，即可降低树的高度，从而减少平均搜索长度。

AVL树的定义：

        一棵AVL树或是空树，或是具有以下性质的二叉搜索树：

（1）它的左右子树都是AVL树；

（2）左右子树的高度差（平衡因子）的绝对值不超过1。

        如果一棵二叉搜索树是高度平衡的，它就是AVL树。若它有n个节点，其高度可保持在O()，搜索时时间复杂度为O()。

2. AVL树的定义

 AVL树的节点定义：

template<class T>
struct AVLTreenode {
	AVLTreenode(const T& value = T()) 
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _value(value)
		,_bf(0)
	{}
	AVLTreenode<T>* _left;
	AVLTreenode<T>* _right;
	AVLTreenode<T>* _parent;
	T _value;
	int _bf;//本节点的平衡因子
};

二、AVL树的操作

1.AVL树的插入

        AVL树是在二叉搜索树的基础上引入了平衡因子，因此AVL树也是二叉搜索树，那么其插入过程可以分为两步：

（1）按照二叉搜索树的方式插入新节点；

（2）调整节点的平衡因子，使其重新回归平衡。

2.AVL树的旋转

        如果在一棵平衡的AVL树中插入一个新节点后，可能造成其不平衡，那么此时就需要调整树的结构，使其重新平衡。根据节点插入的位置不同，AVL树的旋转分为四种：

2.1新节点插入较高左子树的左侧(左左):右单旋

如图：新节点插入到较高的左子树的左侧，执行LL旋转（右单旋）后，节点B成为了新的根节点，即节点A及其子树进行了旋转，称为左单旋。

注意：

（1）较高左子树：子树B

（2）较高左子树的左侧：B节点之后都算其左侧，即插入到B节点的左右孩子都算左侧。

（3）若节点A非根，即A之上还有节点，则旋转后需修改A的双亲节点的指向为B，然后继续向上调整，直至调整到根节点，使整棵树达到平衡。

2.2新节点插入较高右子树的右侧(右右):左单旋

如图：新节点插入到较高的右子树的右侧，执行RR旋转（左单旋）后，节点B成为了新的根节点，即节点A及其子树进行了旋转，称为左单旋。

注意：

（1）较高右子树：子树B

（2）较高右子树的右侧：B节点之后都算其右侧，即插入到B节点的左右孩子都算右侧。

（3）若节点A非根，即A之上还有节点，则旋转后需修改A的双亲节点的指向为B，然后继续向上调整，直至调整到根节点，使整棵树达到平衡。

2.3新节点插入较高左子树的右侧(左右):先左单旋再右单旋

如图：先对B进行左单旋，再对A进行右单旋。

注意：双旋后，parentA和subLB的平衡因子可能需要更新。

2.4新节点插入较高右子树的左侧(右左):先右单旋再左单旋

如图：先对B进行右单旋，再对A进行左单旋

注意：双旋后parentA和subRB的平衡因子可能需要更新。

3.AVL树的验证

AVL树是再二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分为两步：

（1）验证其为二叉搜索树：中序遍历为有序序列。

（2）验证其为平衡树：①每个节点的左右子树高度差的绝对值不超过1②节点的平衡因子是否计算正确。

4.AVL树的删除

        因为AVL树也是二叉搜索树，所以可以按照二叉搜索树的方式将节点删除，然后再更新平衡因子，但是删除节点后的平衡因子更新，最差情况下需要一直调整到根节点位置。

三、AVL树的实现

1.代码实现

template<class T>
struct AVLTreenode {
	AVLTreenode(const T& value = T()) 
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _value(value)
		,_bf(0)
	{}
	AVLTreenode<T>* _left;
	AVLTreenode<T>* _right;
	AVLTreenode<T>* _parent;
	T _value;
	int _bf;//本节点的平衡因子 0，1，-1
	//约定平衡因子为右子树高度减去左子树高度
};

//约定value唯一
template<class T>
class AVLTree {
	typedef AVLTreenode<T> Node;
public:
	AVLTree()
		:_root(nullptr)
	{}
	~AVLTree() {
		Destroy(_root);
	}
	
	//插入
	bool Insert(const T& value) {
		//1.先按二叉搜索树的方式进行插入
		if (_root == nullptr) {
			_root = new Node(value);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur) {
			parent = cur;
			if (value < cur->_value) {
				cur = cur->_left;
			}
			else if (value > cur->_value) {
				cur = cur->_right;
			}
			else {//元素已经存在
				return false;
			}
		}
		//2.插入新节点
		cur = new Node(value);
		cur->_parent = parent;
		if (value < parent->_value) parent->_left = cur;
		else parent->_right = cur;
		//3.调整平衡因子
		while (parent) {
			//2.1修改双亲节点的平衡因子
			if (cur == parent->_right) parent->_bf++;
			else parent->_bf--;
			//2.2判断是否需要调整
			if (parent->_bf == 0) {
				//没有影响树的高度，直接退出
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1) {
				//说明parent是叶子节点，插入后改变了树的高度，需要向上更新平衡因子
				cur = parent;
				parent = cur->_parent;
			}
			else {
				//说明平衡因子为2或-2，不符合AVL树性质，需要通过旋转调整
				if (parent->_bf == 2) {
					//说明右子树高，是左单旋或右左双旋
					//cur与parent平衡因子同号->单旋，异号->双旋
					if (cur->_bf == 1) {
						RotateLeft(parent);
					}
					else {
						RotateRL(parent);
					}

				}
				else {
					//说明左子树高，是右单旋或左右双旋
					//cur与parent平衡因子同号->单旋，异号->双旋
					if (cur->_bf == -1) {
						RotateRight(parent);
					}
					else {
						RotateLR(parent);
					}
				}
				break;
			}
		}
		return true;
	}

	//删除
	void Erase(const T& value) {

	}

	//查找
	Node* Find(const T& value) {
		if (_root == nullptr) return nullptr;
		Node* cur = _root;
		while (cur) {
			if (value < cur->_value) {
				cur = cur->_left;
			}
			else if (value > cur->_value) {
				cur = cur->_right;
			}
			else {
				return cur;
			}
		}
		return nullptr;
	}

	//中序遍历
	void InOrder() {
		_InOrder(_root);
		std::cout << std::endl;
	}

	//判断是否是AVL树
	bool IsAVLTree() {
		return _IsAVLTree(_root);
	}
	//中序打印各节点的平衡因子
	void PrintBf() {
		_PrintBf(_root);
		std::cout << std::endl;
	}

private:
	//左单旋
	//新节点插入较高右子树的右侧
	void RotateLeft(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL) {//注意subrl可能为空
			subRL->_parent = parent;
		}
		subR->_left = parent;
		//跟新parent和subR的双亲节点
		//先保存好parent原先的双亲节点
		Node* pparent = parent->_parent;
		parent->_parent = subR;
		subR->_parent = pparent;
		//处理上层节点
		if (pparent == nullptr) {//已经更新到根节点
			_root = subR;
		}
		else {
			if (parent == pparent->_left) {
				pparent->_left = subR;
			}
			else {
				pparent->_right = subR;
			}
		}
		parent->_bf = 0;
		subR->_bf = 0;
	}
	//右单旋
	//新节点插入较高左子树的左侧
	void RotateRight(Node* parent) {
		//其思想与左单旋相同
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR) {
			subLR->_parent = parent;
		}
		subL->_right = parent;
		Node* pparent = parent->_parent;
		parent->_parent = subL;
		subL->_parent = pparent;
		if (pparent == nullptr) {
			_root = subL;
		}
		else {
			if (parent == pparent->_left) {
				pparent->_left = subL;
			}
			else {
				pparent->_right = subL;
			}
		}
		parent->_bf = 0;
		subL->_bf = 0;
	}
	//左右双旋
	//parent的左子树高
	//新节点插入较高左子树的右侧
	void RotateLR(Node* parent) {
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		int bf = subLR->_bf;
		//先对较高左子树进行左旋
		RotateLeft(parent->_left);
		//再对子树parent整体进行右旋
		RotateRight(parent);
		//更新调整后，需要更新的平衡因子
		if (bf == -1) {
			parent->_bf = 1;
		}
		else if (bf == 1) {
			subL->_bf = -1;
		}
	}
	//右左双旋
	//parent的右子树高
	//新节点插入较高右子树的左侧
	void RotateRL(Node* parent) {
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
		//先对较高右子树进行右旋
		RotateRight(parent->_right);
		//再对子树parent整体进行左旋
		RotateLeft(parent);
		//更新调整后，需要更新的平衡因子
		if (bf == -1) {
			subR->_bf = 1;
		}
		else if (bf == 1) {
			parent->_bf = -1;
		}
	}
	//中序遍历
	void _InOrder(Node* root) {
		if (root == nullptr) return;
		_InOrder(root->_left);
		std::cout << root->_value << " ";
		_InOrder(root->_right);
	}

	//AVL树判断
	bool _IsAVLTree(Node* root) {
		if (root == nullptr) return true;
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int ret = rightHeight - leftHeight;
		if (ret > 1 || ret < -1 || ret != root->_bf) {
			return false;
		}
		return _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
	}
	//求树的高度
	int _Height(Node* root) {
		if (root == nullptr) return 0;
		int leftHeight = _Height(root->_left) + 1;
		int rightHeight = _Height(root->_right) + 1;
		return std::max(leftHeight, rightHeight);
	}
	//中序打印各节点的平衡因子
	void _PrintBf(Node* root) {
		if (root == nullptr) return;
		_PrintBf(root->_left);
		std::cout << root->_bf << " ";
		_PrintBf(root->_right);
	}

	//销毁
	void Destroy(Node*& root) {
		if (root == nullptr) return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
private:
	Node* _root;
};

2.性能分析

        AVL树是一棵绝对平衡的二叉树，其每个节点的左右子树高度差的绝对值不超过1，这样能够保证查询时的高效时间复杂度为。但是如果要对AVL树做一些结构修改操作，性能则会非常低下，比如：插入时，需要维护其平衡性，旋转次数较多；删除时，有可能要一直持续旋转和调整到根的位置。

        因此，若需要一直查询效率高且有序的数据结构，而且数据的个数为静态的，可以考虑使用AVL树，但是一个结构经常修改，就不太适合了。