平衡二叉树（AVL树）复习

不是教学博客。。只为自己复习做笔记了。

直接上代码，不多bb

1.平衡二叉树的定义

①AVL是一颗二叉查找树，在其基础上增加了“平衡”的要求

②平衡：左子树于右子树的高度之差绝对值不超过1，这个高度差成为平衡因子

 

③只要随时保证每个结点平衡因子绝对值不超过1，AVL的高度就始终能保持O(logn)级别。由于需要对每个结点都得到平衡因子，因此需要在树的结构中加入一个变量height，用来记录当前结点为根结点的子树高度：

struct node {
	int v, height;
	node* lchild, * rchild;
};

这种定义下，如果需要新建一个结点，就这样写：

node* newNode(int v) {
	node* Node = new node;
	Node->v = v;
	Node->height = 1;
	Node->lchild = Node->rchild = nullptr;
	return Node;
}

显然，可以通过下面的函数获取当前节点root所在子树的当前高度：

int getHeight(node* root) {
	if (root == nullptr)
		return 0;
	return root->height;
}

同时也就可以计算平衡因子：

int getBalanceFactor(node* root) {
	return getHeight(root->lchild) - getHeight(root->rchild);
}

为什么不直接记录结点的平衡因子，而是记录高度？因为没有办法通过当前结点的子树的平衡因子计算得到该节点的平衡因子，而需要借助子树的高度间接求得。显然，结点root所在子树的height等于左子树height与右子树的height的较大值+1：

void updateHeight(node* root) {
	root->height = max(getHeight(root->lchild) - getHeight(root->rchild));
}

2.平衡二叉树的基本操作

2.1 查找

与二叉查找树相同。AVL树的高度为O(logn)，因此AVL树的查找操作时间复杂度为O(logn)

void search(node* root, int x) {
	if (root == nullptr) {
		return;
	}
	if (x == root->v) {
		cout << root->v;
	}
	else if (x < root->v) {
		search(root->lchild, x);
	}
	else if (x > root->v) {
		search(root->right, x);
	}
}

2.2 插入

2.2.1 左旋

①让B的左子树成为A的右子树

②让A成为B的左子树

③将根节点设定为结点B

void L(node* root) {
	node* temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
}

2.2.2 右旋

右旋和左旋同理，先移动A的右子树，再改变A和B父子关系 ：

void R(node* root) {
	node* temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
}

 

 现有一个AVL树，往其中插入一个结点时，一定会有结点的平衡因子发生变化，会导致失衡。显然，只有在从根结点到该插入节点的路径上的结点才可能发生平衡因子变化，因此只需对这条路径上失衡的结点进行调整。可以证明，只要把最靠近插入节点的失衡节点调整到正常，路径上的所有结点就会都平衡。

举个例子，以结点A为根节点的子树一定是LL型或LR型之一，当结点A的左孩子的平衡因子是1时为LL型，是-1时为LR型。

 

 2.2.3 LL型

把C为根节点的树看作一个整体，然后以结点A作为root进行右旋，便可达到平衡：

 

2.2.4 LR型

可以先忽略结点A，然后以结点C为root进行左旋，就可以把情况转化为LL型，然后按照上面LL型进行一次右旋即可：

2.2.5 RR型

对于RR型来说，可以把以C为根结点的子树看作一个整体，然后以结点A作为root左旋，便可达到平衡：

 

2.2.6 RL型

 

对于RL型来说，可以忽略结点A，以结点C为root进行右旋，就可以把情况转化为RR型，然后按上面RR型的做法进行一次左旋即可：

2.2.7 AVL树插入情况汇总及代码（BF表示平衡因子）

首先回顾一下二叉查找树的insert基础代码（不考虑平衡）：

void insert(node*& root, int v) {
	if (root == nullptr) {
		root = newNode(v);
		return;
	}
	if (v < root->left) {
		insert(root->left, v);
	}
	else if (v > root->right) {
		insert(root->right, v);
	}
}

在这个基础上，由于需要从插入的结点从下往上判断结点是否失衡，因此需要在每个insert函数之后更新当前字数的高度，并在之后根据树形是LL型，LR型，RR型，RL型之一来进行平衡操作：

void insert(node*& root, int v) {
	if (root == nullptr) {
		root = newNode(v);
		return;
	}
	if (v < root->v) {
		insert(root->lchild, v);
		updateHeight(root->lchild);
		if (getBalanceFactor(root) == 2) {
			//LL
			if (getBalanceFactor(root->lchild == 1)) {
				R(root);
			}
			//LR
			else if (getBalanceFactor(root->lchild == -1)) {
				L(root->lchild);
				R(root);
			}
		}
	}
	else if (v > root->v) {
		insert(root->rchild);
		updateHeight(root);
		if (getBalanceFactor(root) == -2) {
			//RR
			if (getBalanceFactor(root->rchild == -1)) {
				L(root);
			}
			//RL
			else if (getBalanceFactor(root->rchild == 1)) {
				R(root->rchild);
				L(root);
			}
		}
	}
}

3.AVL树的建立

只需依次插入n个结点即可：

node* CreateAVL(int data[], int n) {
	node* root = nullptr;
	for (int i = 0; i < n; i++) {
		insert(root, data[i]);
	}
	return root;
}