【树】AVL树专题

定义：AVL树是一棵平衡的二叉排序（查找）树。在这里“平衡”的意思是任意一个结点下的左右子树的高度不超过1（空结点高度为0，叶子结点高度为1）

图中左边非平衡二叉树中，标黄结点45的左右子树的高度差不为1。左子树高度为2（44、43），而右子树的高度为0

效率：AVL树的查找、删除、插入操作在平均和最坏的情况下都为O(logn)，因为它时刻维持着二叉树平衡

相关概念

1. 平衡因子(Balance Factor)：将二叉树上左子树结点高度减去右子树结点高度的绝对值

2. 最小不平衡子树：距离插入结点最近的，且平衡因子绝对值大于1的结点为根的子树

   

   图中在插入43后，黄色45结点的平衡因子大于2。因此，以结点45为根的结点为最小不平衡子树

AVL树的C语言代码实现

AVL树结点定义：

#define ElemType int

/*
*val：结点存储的值
*height：结点高度，用来运算父亲结点的BF值。取左右子树高度较大值
*lchild、rchild：左孩子、右孩子指针
*/

typedef struct AVLTreeNode {
	ElemType val;
	int height;
	struct AVLTreeNode* lchild;
	struct AVLTreeNode* rchild;
}AVLTreeNode, AVLTree*;

一些实现中也会把AVL树的BF值存起来，但这里我们也可以用height值求出BF。因此没有花费多余空间存储

AVL树的高度：

int AVLHeight(AVLTreeNode* pnode) {
	return pnode->height;
}

AVL树失衡调整：

在AVL树中，对一个结点的插入或删除操作都可能导致AVL树失衡。因此失衡调整是插入与删除的基本操作

AVL树的失衡可分为四种情况，这里我们逐一分析

假设我们要对数组a[] = { 4, 5, 6, 3, 2, 8, 7, 0, 1 }构建一棵AVL树