C++ 二叉搜索树（二）AVL树的实现

本片基于上一篇实现的普通二叉搜索树BST实现更进一步的AVL树，AVL树在普通二叉搜索树的基础上添加了树的平衡操作。

节点的平衡因子：节点的左子树高度与右子树高度之差。

失衡：节点的平衡因子绝对值大于1。

平衡操作：通过左旋或右旋将失衡的节点的平衡因子绝对值恢复至小于等于1。

左旋：对节点进行左旋，就是进行如下操作：

• 节点的右子改为其右子的左子
• 节点成为其右子的左子

如下图所示，对A进行左旋操作：

右旋：对节点进行右旋，就是进行如下操作：

• 节点的左子改为其左子的右子
• 节点成为其左子的右子

如下图所示，对A进行右旋操作：

上面的左旋和右旋已经涵盖了失衡中的2种情况，即A、B、C是在一个方向上的，下面说明不在一个方向时的旋转方法。

右左旋：如下图左所示，A、B、C不在同一个方向，此时，只需进行两次旋转：

• 对B进行右旋操作
• 对A使用左旋操作

左右旋：与上面的右左旋同理，不再赘述。

注意：本节的实现基于上一篇实现的二叉搜索树BST。

AVL树继承了普通了二叉搜索树BST，与BST唯一不同的仅仅是在插入和删除后添加了平衡操作。

#define balancefactor(node) (getHeight(node->left) - getHeight(node->right))
#define isBlanced(node) (balancefactor(node) < 2 && balancefactor(node) > -2)

class AVL: public BST 
{
protected:
	Node* rotateAt(Node* node);
	Node* connect34(Node* a, Node* b, Node* c, 
				   Node* T0, Node* T1, Node* T2, Node* T3);
public:
	Node*& insert(int data);
	bool remove(int data);
};

由于旋转操作比较复杂且情况也比较多，具体实现中我们不使用旋转操作使二叉树复衡，而使用更加简单的、通用的3+4重构方法。

• balancefactor()与isBalanced()为计算平衡因子与判断节点是否平衡的宏。
• insert和remove即AVL树的插入和删除操作，与BST唯一不同的是添加了平衡操作。
• rotateAt与connect34即3+4重构，实现平衡操作。

首先介绍3+4重构使AVL树恢复平衡的方法。

当失衡发生时，记参与旋转操作的3个节点为A、B、C，大小关系为A

你可以画一个失衡的树进行上面的操作，具体地查看一下。

代码实现：
传入参数：3个节点和4棵子树。

返回值：新树的根节点，供调用者将重构完成的子树与整棵树进行链接，拿上面的图来说，返回的就是B。

Node* AVL::connect34(Node* a, Node* b, Node* c,
					 Node* T0, Node* T1, Node* T2, Node* T3)
{
	a->left = T0; if (T0) T0->parent = a;
	a->right = T1; if (T1) T1->parent = a;
	updateHeight(a);

	c->left = T2; if (T2) T2->parent = c;
	c->right = T3; if (T3) T3->parent = c;
	updateHeight(c);

	b->left = a; a->parent = b;
	b->right = c; c->parent = b;
	updateHeight(b);

	return b;
}

该方法调用上面的connect34并指定重构子树的父节点
返回值：重构子树的根节点。

代码实现：

代码中g为失衡节点，p为g的子，v为p的子。

Node* AVL::rotateAt(Node* v)
{
	Node* p = v->parent, * g = p->parent;
    // 视4种不同情况调用connect
	if (p->isLeft()) {
		if (v->isLeft()) {
			p->parent = g->parent; // 指定重构子树父节点
            // 重构并返回根节点
			return connect34(v, p, g, v->left, v->right, p->right, g->right);
		}
		else {
			v->parent = g->parent;
			return connect34(p, v, g, p->left, v->left, v->right, g->right);
		}
	}
	else {
		if (v->isRight()) {
			p->parent = g->parent;
			return connect34(g, p, v, g->left, p->left, v->left, v->right);
		}
		else {
			v->parent = g->parent;
			return connect34(g, v, p, g->left, v->left, v->right, p->right);
		}
	}
}

这个insert相比于BST中的insert添加了插入后的平衡操作（调用上面的3+4重构）。

要注意的是，在平衡过后，子树的高度与未插入节点前是一样的，因此只需进行至多一次平衡操作。

Node*& AVL::insert(int data)
{
	Node*& node = search(data);
	if (node) return node;
	++size_;
	node = new Node(data, hot_);  // 插入新节点
	if (!hot_) root_ = node; // 此时插入的节点为根节点，更新root_
	// 重平衡
	for (Node* p = node->parent; p; p = p->parent) {
		if (!isBlanced(p)) { // 如果发现失衡
			// 先记录要被重构的子树的父亲
			Node* temp = p->parent;
			// 重构
			Node* newp = rotateAt((p->getTallerChild())->getTallerChild());
			// 更新重构子树在其父亲的子节点中的位置
			if (temp) {
				if (p == temp->left) temp->left = newp;
				else temp->right = newp;
			}
			// 如果重构子树根为整树的根，那么更新root_
			if (p == root_) root_ = newp;
			// 重构后子树高度与未插入前相同，因此不用更新高度
			break;
		}
		else {
			updateHeight(p);
		}
	}
	return node;
}

同样在删除后添加了平衡操作，与插入不同的是，子树平衡后高度与未删除前不一定相同，因此更高的祖先可能失衡，需要进行O(logn)次的平衡操作。

bool AVL::remove(int data)
{
	Node*& target = search(data);
	if (!target) return false;
	removeAt(target);
	--size_;
	// 重平衡
	for (Node* p = target->parent; p; p = p->parent) {
		if (!isBlanced(p)) { // 如果发现失衡
			// 先记录要被旋转的子树的父亲
			Node* temp = p->parent;
			// 旋转并返回该子树的新树根
			Node* newp = rotateAt((p->getTallerChild())->getTallerChild());
			// 更新子树在其父亲的子节点中的位置
			if (temp) {
				if (p == temp->left) temp->left = newp;
				else temp->right = newp;
			}
			// 如果旋转子树根为整树的根，那么更新root_
			if (p == root_) root_ = newp;
			updateHeight(p); // 高度更新
		}
	}
	return true;
}