C++ AVLTree

1. AVLTree的定义

2. 平衡因子

平衡因子不是必须的，只是选择实现AVLTree的一种方式。

平衡因子的优势是可以直接观察，但是需要付出维护的代价。

在每一个节点中都加入其平衡因子的数值，一般习惯用右子树高度-左子树高度

template<typename k,typename v>
struct AVLTreeNode {
	typedef AVLTreeNode<k, v> Node;
	Node* _left;
	Node* _right;
	Node* _parent;
	int _bf;//balance factor
	pair<k, v> _kv;

	AVLTreeNode( const pair<k,v>& kv = make_pair(k(),v()) )
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

以下树为例进行分析。 

将平衡因子当作一个风向标。

标出每一个节点现在的平衡因子：

新插入的节点会影响从根到该节点路径上所有节点的平衡因子，每插入一个平衡因子就需要调整其祖先的平衡因子（这也是为什么每个节点的成员需要设计一个parent）。

对于叶子结点，每插入一个节点，对于其双亲（原来的叶子）的变化：

插入在parent右边, 平衡因子++

插入在parent左边，平衡因子--

下面来讨论在普遍情况下插入节点后平衡因子的变化。

首先，任意树的平衡因子只会是-1 0 1

(否则不满足AVL树的条件)

1. 如果在插入节点之后，parent的平衡因子是0（就像上图的节点8），说明原本是-1或者1，然后新节点加入到了矮的那一边。

2. 如果插入后parentr的平衡因子是1或则-1，说明原本parent的平衡因子本来是0，在右或左插入一个。那此时parent的子树的高度就变化了，需要继续向上更新。

3. 如果插入后parent的平衡因子是2或者-2，说明原本parent的平衡因子本来是-1或者1，然后新节点加入到了长的那一边。此时parent的子树的高度也变化了，需要继续向上更新。

并且已经违反了AVL树的规则，需要进行旋转。

3. AVLTree的基础接口 

基本结构都和二叉搜索树类似。

先实现结点：

template<typename k,typename v>
struct AVLTreeNode {
	typedef AVLTreeNode<k, v> Node;
	Node* _left;
	Node* _right;
	Node* _parent;
	int _bf;//balance factor
	pair<k, v> _kv;

	AVLTreeNode(const pair<k,v>& kv = make_pair(k(),v())
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}
};

再写树：

构造我们现在只强调一下拷贝构造。

不能直接将根_root拷贝过来，这样是两颗重复的树，我们需要自己实现深拷贝。

而树的拷贝需要递归，构造函数里直接递归当然不合适，所以需要再封装一层。

插入 

插入的大逻辑如下：

            

bool insert(const pair<k, v>& kv) {
	Node* parent = nullptr;
	Node* cur = _root;

	if (cur == nullptr) {
		_root = new Node(kv);
		return true;
	}

	while (cur) {
		if (cur->_kv.first > kv.first) {
			parent = cur;
			cur = cur->_left;
		}
		else if (cur->_kv.first < kv.first) {
			parent = cur;
			cur = cur->_right;
		}
		else {
			return false;
		}
	}
	cur = new Node(kv);
	if (parent->_kv.first > kv.first) parent->_left = cur;
	if (parent->_kv.first < kv.first) parent->_right = cur;
	cur->_parent = parent;

	//开始调整parent的balance factor,因为是三叉链，所以可以通过parent一路遍历向上
	while (parent) {
		//先计算平衡因子
		if (parent->_left == cur) {
			parent->_bf--;
		}
		else if (parent->_right == cur) {
			parent->_bf++;
		}
		//再决定是否向上调整
		if (parent->_bf == 0) {
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1) {
			//adjust up
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2) {
			//旋转
		}
		else {
			//如果还有其他情况，说明原节点的bf有问题，不满足avl树的规范，直接断掉
			assert(0);
		}
	}
	return true;
}

在搜索二叉树的基础上，插入变的更加复杂。 

首先比较的都是pair中的first，也就是key值

并且依然需要使用双指针，否则不好接入

最后就是需要插入完成之后调整_bf

 旋转

如果在一棵原本是平衡的 AVL 树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。

直接通过上文中的例子来进入“旋转”的主题 

左单旋：

新节点插入较高右子树的右侧，开始向上遍历调整平衡因子，调整到8的时候发现平衡因子是2，需要旋转，然后就将8这个节点传进我们的调节函数RotateL

旋转方法：9的左子树变成8的右子树，8变成9的左子树 

这样旋转之后高度和加入节点之前没有变化。

抽象图：

所有的分析中都要注意，节点之间的高度差距不能超过1

假设30为传入函数的需要调整的节点（命名为parent）

60命名为subR a/b/c是三个等高的树

（如果a/b/c不等高就不能构成我们想调整的情况。）

总结一下就是：

左单旋需要将subRL连接到parent的右边，因为60的左子树一定是大于30的，然后将30连接到60的左边。

可以先通过列举h==0 h==1 h==2 h==3等情况观察：

 h==0时最简单。也是上文引例中的情况。

h==1时的情况

h==2时，情况的种类就很多了。

a/b可能是xyz中的任意一种情况。c只能是x，否则直接在该子树中就可以调节了。

注意为什么是3*3*4 

因为左单旋对应的模型是在60的右树（C）下进行增加节点，所以只有4个可以选择的位置。

 h==3时，先分析高度为3的子树的情况，可能为x（全满）或者y（非全满）

其中y共有14种情况。所以不讨论加节点的C树，a/b树就已经有(14+1)*(14+1)种可能性

因此，解决这个问题还需要从抽象图入手，将a、b、c当作高度为h的抽象树。

代码实现：

旋转点：平衡因子出现问题的点。

左单旋其实只需要改变subR suRL parent三者的链接关系。

parent可以是整棵树的根，也可以是任意一个子树的根 

依然有逻辑bug，subRL和parent的_parent都还要修改。

先只修改subRL的_parent（parent是需要调整的节点的变量名，_parent是节点内的成员变量）

subRL可能是空（h==0的时候就是空）。但是parent和subR是一定存在的（否则怎么会出现一个_bf是2一个_bf是1呢）

那如果这棵树本来自身只是一颗子树呢？

所以在改动parent->_parent的值之前，要记录一下原来的parent->_parent

对于parent->_parent的分析：

如果是空，表明30（原来的parent）本来就是整棵树的根，现在整棵树的根调整了，

我们需要调整下_root

如果不是空，就像之前的insert一样，得从parentParent再去找我们左旋的这棵树是在左边还是右边。但是不用调整_root

至此，单旋的大逻辑就已经完成。

节点链接好了，但是我们现在还没有处理平衡因子。

经过观察不难发现，parent和subR的平衡因子都变成0了

再加一句：parent->_bf = subR->_bf = 0;

void RotateL(Node* parent) {
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

    parent->_right = subRL;
	if (subRL) {
		subRL->_parent = parent;
	}

	Node* parentParent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	if (parentParent) {
		if (parentParent->_left == parent) {
			parentParent->_left = subR;
		}
		else {
			parentParent->_right = subR;
		}
	}
	else {
		subR->_parent = nullptr;
		this->_root = subR;
	}
	subR->_parent = parentParent;

	//调整平衡因子
    parent->_bf = subR->_bf = 0;
}

为了便于记忆：取名字的三个节点呈现一个“ > ”形状，要将凹陷的部分拉出来，所以出现这种形状叫左旋。

右单旋：

逻辑几乎和左旋是一样的，只是交换了right和left

读者可以自行尝试先写一写这个代码。

void RotateR(Node* parent) {
	assert(parent);

	Node* subL = parent->_left;
	Node* subLR = subL->right;

	parent->_left = subLR;
	if (subLR) {
		subLR->_parent = parent;
	}

	//解决subL和parent的父节点问题
	Node* parentParent = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	if (parentParent == nullptr) {
		_root = subL;
	}
	else {
		if (parentParent->_left == parent) {
			parentParent->_left = subL;
		}
		else {
			parentParent->_right = subL;
		}
	}
	subL->_parent = parentParent;

	//调整平衡因子
    parent->_bf = subL->_bf = 0;
}

实现好了左单旋和右单旋的代码

回到原来的插入代码，进行联系：

左旋的时候，parent的bf==2 cur的bf == 1

右旋的时候，parent的bf==-2 cur 的bf==-1

根据上述的两个条件，要讨论哪些旋转方案也逐渐明朗

cur->_bf==1&& parent->bf==2（左单旋）

cur->_bf==-1&& parent->bf==-2(右单旋)

cur->_bf==-1&& parent->bf==2

cur->_bf==1&& parent->bf==-2

来看后面两种情况：

双旋：

上面为单旋能解决的情况（parent和subR的bf符号相同），下面为符号相反

                                                                  （h==0）

按照之前的旋转思路，此时进行左单旋，能保证搜索树的特征，但是没有完成旋转的初衷：使高度差消失。

这样旋只是让原来的右边高变成现在的左边高

                                                                         (h==1)

如果此时再右旋，又会旋回去。

也就是说，左右旋面对这种情况只会原地打转。

解决方法：双旋

先看h==1或h==0

再看抽象图：

左双旋分为：右单旋+左单旋

右双旋分为：左单旋+右单旋

需要左双旋时，第一次右单旋就将本来需要左双旋的变成上文最基本的模型：

                                                  

因为此时涉及到对subR进行一次单旋，需要使用到subRL的右子树，所以需要单独再拆开一层树来分析。单旋的时候subRL不一定存在，但这次都是在subRL的位置上加的数据，所以subRL一定不为空

还可以直接观察双旋结果： 

直接看起始和终点状态，将subRL这个节点变成根，parent在左、subR在右

然后subRL的左右子树分别分配给parent的右和subR的左

总结：subRL或者subLR会成为新的根，他左边的子树分配给在两个节点中更左边的节点的右边，他右边的子树分配给在两个节点中更右边的节点（subR或subL / parent中的任意一个）的左边

双旋的代码实现的大逻辑：

当然是不正确的，

虽然每一次单旋都能保证父节点和子节点的转接，但是没有考虑平衡因子的维护。

问题整理：

双旋并不像单旋，单纯的全部更新为0

并且新节点加到b和c，最后的结果还不一样。

h为0的时候还是一种单独的情况，更新完之后是全0

以左双旋为例： 

如果subRL的平衡因子是1 就是在C插入

如果subRL的平衡因子是-1 就是在B插入

如果是0，则subRL本身是新加入的节点，也就是上文所说的h是0的时候的特殊情况。  

RotateRL的意思就是先右单旋再左单旋 

左双旋和右双旋实现：

void RotateRL(Node* parent) {
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;//采用直接观察法，记录最初的subRL的_bf

	RotateR(subR);
	RotateR(parent);

	if (bf == 0) {
		//说明subRL就是新加入的元素
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else if (bf == -1) {
		parent->_bf = 0;
		subRL->_bf = 0;
		subR = 1;
	}
	else if (bf == 1) {
		parent->_bf = 1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else {
		assert(0);
	}
}

void RotateLR(Node* parent) {
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf;

	RotateL(subL);
	Rotate(parent);

	if (bf == 0) {
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1) {
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == -1) {
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else {
		assert(0);
	}
}

这个时候就能根据parent和cur的_bf值判断怎么旋了。

旋完之后可以直接break跳出平衡因子的调节。

4. AVLTree的测试 

完成了以上代码后，使用{16, 3, 7, 11, 9, 26, 18, 14, 15} {4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

两组测试用例来测试代码。

先实现中序走一遍。

但是中序只能保证是一个二叉搜索树。

还要判断其是不是平衡搜索树。

再实现一个找高度的函数

或者

均可，但是切忌写成：

 递归里套了递归，时间复杂度会大很多。这一点在之前的博客中有过详细讲解。

利用_Height函数实现IsBalanceTree函数

bool _IsBalanceTree(Node* root) {
	if (root == nullptr) return true;//空树也算AVLTree

	//计算节点高度差
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;

	if (abs(diff) >= 2) {
		cout << "结构错误，有高度差大于1的节点" << endl;
		return false;
	}
	if (diff != root->_bf) {
		cout << "平衡因子调节错误" << endl;
		return false;
	}

	//并且保证所有的子树都满足这个条件。
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

调试技巧：

如果发现有错，用编译器cout来找报出错

打断点不一定要用编译器的条件断点，可以自己直接写。

第一组：

通过了。

第二组：

利用上述调试技巧打断点。 

 发现是6的平衡因子有问题

那么就在插入6时打下断点，开始观察是如何出错的。

（空语句不能打断点，所以我们定义一个变量语句来方便打断点） 

然后顺利找到是RotateRL时调节平衡因子的问题。（bf==1时parent的值应该是-1） 

AVLTree test2:

由于C语言库函数的设计，只能有32468个随机数。

所以希望产生N个随机数时最好加一个其他数字。

5. 小结

      AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$log_2 (N)$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

 比如：插入时最多旋转两次（双旋），但是erase时可能需要旋转很多次。