012 C++ AVL

前言

本文将会向你介绍AVL平衡二叉搜索树的实现

引入AVL树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序普通的二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法(AVL树是以这两位的名字命名的)：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1，超过了1需要对树中的结点进行调整(旋转)，即可降低树的高度，从而减少平均搜索长度。

平衡因子

AVL树的平衡因子是指一个节点的左子树的高度减去右子树的高度的值。在AVL树中，每个节点的平衡因子必须为-1、0或1，如果不满足这个条件，就需要通过旋转操作来重新平衡树。AVL树的平衡因子可以帮助我们判断树的平衡状态，并且在插入进行相应的调整，以保持树的平衡性。

节点的创建

除了需要增加一个_bf平衡因子，这里还多加了一个pParent的结构体指针便于我们向上遍历对平衡因子进行调整

struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 节点的平衡因子
};

插入节点

先按照二叉搜索树的规则将节点插入到AVL树中
新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性
cur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

如果cur插入到pParent的左侧，只需给pParent的平衡因子-1即可
如果cur插入到pParent的右侧，只需给pParent的平衡因子+1即可

此时：pParent的平衡因子可能有三种情况：0，正负1，正负2

1. 如果pParent的平衡因子为0，说明插入之前pParent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功
2. 如果pParent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新
3. 如果pParent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理

	// 在AVL树中插入值为data的节点bool Insert(const T& data){Node* cur = _pRoot;Node* parent = nullptr;if (_pRoot == nullptr){//直接插入_pRoot = new Node(data);//插入成功return true;}//寻找插入位置else{Node* parent = cur;while (cur){parent = cur;if (cur->_data > data){cur = cur->_pLeft;}else if (cur->_data < data){cur = cur->_pRight;}//已有else return false;}cur = new Node(data);//插入+链接if (parent->_data > data){parent->_pLeft = cur;}else{parent->_pRight = cur;}//链接cur->_pParent = parent;}//更新平衡因子while (parent){if (cur == parent->_pRight){parent->_bf++;}else if (cur == parent->_pLeft){parent->_bf--;}if (parent->_bf == 0){//插入后子树稳定，不用向上更新平衡因子return true;}else if (parent->_bf == 1 || parent->_bf == -1){return true;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){//左旋 (右高左低，往左边压)RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){//右旋（左高右低，往右边压）RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋（不是单独的左右有一方低，有一方高）RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右双旋（不是单独的左右有一方低，有一方高）RotateR(parent);}parent = parent->_pParent;cur = cur->_pParent; }else{return false;}return true;}}

右单旋

左高右低，往右边旋（根据平衡因子判断（右子树的高度减去左子树的高度））
细节分析+代码
在这里插入图片描述

整体思路
在这里插入图片描述

	void RotateR(Node* pParent){Node* pPnode = pParent->_pParent;Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;if (subLR){pParent->_pLeft = subL->_pRight;subL->pParent = pParent;}subL->_pRight = pParent;pParent->_pParent = subL;//旋转部分子树if (pPnode){//是左子树if (pPnode->_pLeft == pParent){pPnode->_pLeft = subL;subL->pParent = pPnode;}//是右子树else{pPnode->_pLeft = subL;subL->pParent = pPnode;}}//旋转整棵子树else{_pRoot = subL;subL->pParent = nullptr;}//调节平衡因子pParent->_bf = subL->_bf = 0;}

左单旋

这里作统一说明：h表示子树的高度，绿色标记的数字为节点的平衡因子，长方形表示的是一棵抽象的子树
右高左低，往左边旋（根据平衡因子判断（右子树的高度减去左子树的高度））
左单旋和右单旋的思路很像，这里就不再进行细节分析。

整体思路
在这里插入图片描述

void RotateL(Node* pParent){Node* pPnode = pParent->_pParent;Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;//可能为空if (subRL){pParent->_pRight = subRL;subRL->_pParent = pParent;}subR->_pLeft = pParent;pParent->_pParent = subR;//链接：旋转整棵树if (pPnode == nullptr){_pRoot = subR;subR->_pParent = nullptr;}//链接：旋转子树else{if (pPnode->_pLeft == pParent){pPnode->_pLeft = subR;subR->_pParent = pPnode;}else if (pPnode->_pRight == pParent){pPnode->_pRight = subR;subR->_pParent = pPnode;}}//更新平衡因子pParent->_bf = subR->_bf = 0;}

左右双旋

右左双旋（不是单独的左右有一方低，有一方高）

(1)第一种情况，也是最特殊的情况，即parent的右子树只有两个节点

在这里插入图片描述

（2）第二种情况，parent的左右子树是高度为h的抽象子树，新增节点插入到b子树上

在这里插入图片描述

（2）第三种情况，parent的左右子树是高度为h的抽象子树，新增节点插入到c子树上实际上第二三种情况的分析是一致的

在这里插入图片描述

void RotateLR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;//复用RotateL(subL);RotateR(pParent);//更新平衡因子//插入右边if (bf == 1){subLR->_bf = 0;subL->_bf = -1;pParent->_bf = 0;}//插入左边else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;pParent->_bf = 1;}else if (bf == 0){subLR->_bf = 0, subL->_bf = 0, pParent->_bf = 0;}else{assert(false);}}

右左双旋

左右双旋（不是单独的左右有一方低，有一方高）

(1)第一种情况，也是最特殊的情况，即parent的左子树只有两个节点

在这里插入图片描述

（2）第二种情况，parent的左右子树是高度为h的抽象子树，新增节点插入到c子树上

在这里插入图片描述

（3
）第三种情况，parent的左右子树是高度为h的抽象子树，新增节点插入到b子树上实际上第二三种情况的分析是一致的

在这里插入图片描述

void RotateRL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(subR);RotateL(pParent);//更新平衡因子//插入在右边if (bf == 1){subRL->_bf = 0;subR->_bf = 0;pParent->_bf = -1;}//插入在左边else if (bf == -1){subRL = 0;pParent->_bf = 0;subR->_bf = 1;}else if (bf == 0){subRL =pParent->_bf = subR->_bf = 0;}else{assert(false);}}

测试

	size_t _Height(Node* pRoot){if (pRoot == nullptr){return 0;}int leftHeight = _Height(pRoot->_pLeft);int rightHeight = _Height(pRoot->_pRight);return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;}bool _IsBalance(Node* pRoot){if (pRoot == nullptr){return true;}int leftHeight = _Height(pRoot->_pLeft);int rightHeight = _Height(pRoot->_pRight);//平衡因子异常的情况if (rightHeight - leftHeight != pRoot->_bf){cout << pRoot->_data << "平衡因子异常" << endl;return false;}//检查是否平衡return abs(rightHeight - leftHeight) < 2//检查、遍历左右子树&& _IsBalance(pRoot->_pLeft)&& _IsBalance(pRoot->_pRight);}bool IsBalance(){return _IsBalance(_pRoot);}int main()
{const int N = 30000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());cout << v.back() << endl;}AVLTree<int> t;for (auto e : v){if (e == 41){t.Insert(e);}cout << "Insert:" << e << "->" << t.IsBalance() << endl;}cout << t.IsBalance() << endl;return 0;
}

全部代码

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf;   // 节点的平衡因子
};// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public:AVLTree(): _pRoot(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T& data){Node* cur = _pRoot;Node* parent = nullptr;//判断是否为空树if (_pRoot == nullptr){//直接插入_pRoot = new Node(data);//插入成功return true;}//寻找插入位置else{Node* parent = cur;while (cur){//记录父节点的位置，便于后续的链接操作parent = cur;//向左遍历if (cur->_data > data){cur = cur->_pLeft;}//向右遍历else if (cur->_data < data){cur = cur->_pRight;}//已有else return false;}cur = new Node(data);//插入+链接if (parent->_data > data){parent->_pLeft = cur;}else{parent->_pRight = cur;}//链接cur->_pParent = parent;}//更新平衡因子while (parent){if (cur == parent->_pRight){parent->_bf++;}else if (cur == parent->_pLeft){parent->_bf--;}if (parent->_bf == 0){//插入后子树稳定，不用向上更新平衡因子return true;}else if (parent->_bf == 1 || parent->_bf == -1){return true;}else if (parent->_bf == 2 || parent->_bf == -2){if (parent->_bf == 2 && cur->_bf == 1){//左旋 (右高左低，往左边压)RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){//右旋（左高右低，往右边压）RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){//右左双旋（不是单独的左右有一方低，有一方高）RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){//左右双旋（不是单独的左右有一方低，有一方高）RotateR(parent);}parent = parent->_pParent;cur = cur->_pParent; return true;}else{return false;}	}return true;}// AVL树的验证bool IsAVLTree(){return _IsAVLTree(_pRoot);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_pLeft);cout << root->_data << " ";_InOrder(root->_pRight);}void InOrder(){_InOrder(_pRoot);cout << endl;}// 根据AVL树的概念验证pRoot是否为有效的AVL树size_t _Height(Node* pRoot){if (pRoot == nullptr){return 0;}int leftHeight = _Height(pRoot->_pLeft);int rightHeight = _Height(pRoot->_pRight);return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;}bool _IsBalance(Node* pRoot){if (pRoot == nullptr){return true;}int leftHeight = _Height(pRoot->_pLeft);int rightHeight = _Height(pRoot->_pRight);//平衡因子异常的情况if (rightHeight - leftHeight != pRoot->_bf){cout << pRoot->_data << "平衡因子异常" << endl;return false;}//检查是否平衡return abs(rightHeight - leftHeight) < 2//检查、遍历左右子树&& _IsBalance(pRoot->_pLeft)&& _IsBalance(pRoot->_pRight);}bool IsBalance(){return _IsBalance(_pRoot);}// 右单旋void RotateR(Node* pParent){Node* pPnode = pParent->_pParent;Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;if (subLR){pParent->_pLeft = subL->_pRight;subL->_pParent = pParent;}subL->_pRight = pParent;pParent->_pParent = subL;//旋转部分子树if (pPnode){if (pPnode->_pLeft == pParent){pPnode->_pLeft = subL;subL->_pParent = pPnode;}else{pPnode->_pLeft = subL;subL->_pParent = pPnode;}}//旋转整棵子树else{_pRoot = subL;subL->_pParent = nullptr;}//调节平衡因子pParent->_bf = subL->_bf = 0;}// 左单旋void RotateL(Node* pParent){Node* pPnode = pParent->_pParent;Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;if (subRL){pParent->_pRight = subRL;subRL->_pParent = pParent;}subR->_pLeft = pParent;pParent->_pParent = subR;//链接：旋转整棵树if (pPnode == nullptr){_pRoot = subR;subR->_pParent = nullptr;}//链接：旋转子树else{if (pPnode->_pLeft == pParent){pPnode->_pLeft = subR;subR->_pParent = pPnode;}else if (pPnode->_pRight == pParent){pPnode->_pRight = subR;subR->_pParent = pPnode;}}//更新平衡因子pParent->_bf = subR->_bf = 0;}// 右左双旋void RotateRL(Node* pParent){Node* subR = pParent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(subR);RotateL(pParent);//更新平衡因子//插入在右边if (bf == 1){subRL->_bf = 0;subR->_bf = 0;pParent->_bf = -1;}//插入在左边else if (bf == -1){subRL = 0;pParent->_bf = 0;subR->_bf = 1;}else if (bf == 0){subRL =pParent->_bf = subR->_bf = 0;}else{assert(false);}}// 左右双旋void RotateLR(Node* pParent){Node* subL = pParent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(subL);RotateR(pParent);//更新平衡因子//插入右边if (bf == 1){subLR->_bf = 0;subL->_bf = -1;pParent->_bf = 0;}//插入左边else if (bf == -1){subLR->_bf = 0;subL->_bf = 0;pParent->_bf = 1;}else if (bf == 0){subLR->_bf = 0, subL->_bf = 0, pParent->_bf = 0;}else{assert(false);}}
private:Node* _pRoot;
};//int main()
//{
//	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15};
//	int a[] = { 4,2,6,13,5,15,7,16,14 };
//	AVLTree<int> t;
//	for (auto e : a)
//	{
//		t.Insert(e);
//	}
//	t.InOrder();
//	return 0;
//}
int main()
{const int N = 30000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand());cout << v.back() << endl;}AVLTree<int> t;for (auto e : v){if (e == 41){t.Insert(e);}cout << "Insert:" << e << "->" << t.IsBalance() << endl;}cout << t.IsBalance() << endl;return 0;
}