AVL树

AVL 树

前言

AVL 树是二叉搜索&平衡树的一种，能够担任快速地插入，查找，等操作的数据结构。二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 \(n\) 个结点的二叉搜索树中，这些操作的最优时间复杂度为 \(O(\log n)\)，最坏为 \(O(n)\)。

二叉搜索树的定义

  • 空树为二叉搜索树
  • 如果二叉搜索树的左子树不为空，那么它的左子树上所有点的附加权值均小于其根节点的值。
  • 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  • 二叉搜索树的左右子树均为二叉搜索树。

简单来说，就是一棵树满足全部左子树的值小于其根节点，全部右子树的值大于其根节点。

节点的定义

与正常的树相同，有左右子节点。还有需要维护的总体大小，高度。全部用指针实现。在保存时只需保存根节点的指针就行。

1
2
3
4
5
6
7
8
9
10
class AVLTreeNote{
	public:
		int key;
		AVLTreeNote *Left;
		AVLTreeNote *Right;
		int height;
		int size;
		int count;
		AVLTreeNote(int value): key(value), size(1), count(1), Left(nullptr), Right(nullptr),height(1) {}
};

基本操作

遍历

对于一个符合要求的二叉平衡树，它的中序遍历为非降的序列。那么可以利用这个性质来debug。(在小范围数据特别好用)，时间复杂度为 \(O(n)\)。

1
2
3
4
5
6
7
8
9
// 树的中序遍历，并且按顺序输出节点
void Traversal(AVLTreeNote* root){
	if(root == nullptr){
		return;
	}
	Traversal(root->Left);
	cout<<"root->key: "<<root->key<<" height: "<<root->height<<" size: "<<root->size<<" count : "<<root->count<<" Left(if have): "<<(root->Left ? root->Left->key : -1)<<" Right(if have): "<<(root->Right ? root->Right->key : -1)<<endl;
	Traversal(root->Right);
}

寻找最大最小值

一个二叉搜索树上的最小值为二叉搜索树左链的顶点，最大值为二叉搜索树右链的顶点。时间复杂度为 \(O(h)\)。