[C++][数据结构]AVL树插入的模拟实现

前言

紧接着上一篇文章，我们来模拟实现一下set的底层结构

引入

对于BSTree，虽然可以缩短查找的效率，但如果数据有序它将退化为单支树

我们可以用AVL树来解决这个问题。

概念

AVL树：

• 它的每个结点的左右子树高度之差的绝对值不超过1
• 它的左右子树都是AVL树

对于10来说，左右子树高度差为2，所以不满足

实现

基本结构

template<class K, class V>
struct AVLTreeNode
{using Node = AVLTreeNode<K, V>;Node* _left;	//左节点Node* _right;	//右节点Node* _parent	//父节点int _bf;		//平衡因子//计算方式：右树高度减去左树高度pair<K, V> _kv;	//用pair封起来的键值对AVLTreeNode(const pair<K, V>& kv):_kv(kv),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}
};

插入

和搜索树的插入规则前半部分是相同的，具体细节可以看注释

	bool Insert(const pair<K, V>& kv){//1.按照搜索树规则插入：先找到合适的位置，然后链接if (_root == nullptr){_root = new Node(kv);return true;}//如果树为空，特殊判断Node* parent = nullptr;//父节点//方便记录父节点原来的子树Node* cur = _root;while (cur != nullptr){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;}}//查找完再判断是父节点的左树还是右数//标记为Acur = new Node(kv);if (parent->kv.first > kv.first){parent->_right = cur;}else{parent->_right = cur;}cur->_parent = parent;//2.更新平衡因子，根据AVL的规则，进行旋转调整//	- 插入因子会影响自己所有的祖先节点//	- 更新原则：//		1.修改_bf//			- cur是_parent左边，_parent->_bf--//			- cur是_parent右边，_parent->_bf++//		2.根据_parent->_bf是否为0来判断是否修改祖先的_bf，//			- _bf == 0 在更新前_bf是-1或1，更新后左右平衡了，所以不会影响祖先//			- _bf == 1/-1 更新前平衡因子为0，更新后左右不平衡了，所以祖先也要更新//		3._bf == 2/-2 插入后出现问题，要进行旋转while(parent){if (parent->_right == cur){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == 1){cur = cur->_parent;parent = parent->_parent;}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){RotateLR(parent);}else{RotateRL(parent);}break;//因为旋转完就是全都平衡了，所以直接结束循环}else{throw("false");}}return true;}

旋转

旋转也是插入的一部分，只是因为比较重要，所以单独拎出来写

变量说明：

• h表示树的高度
• a、b、c是树的名字
• 30，60是_value

左单旋

左单旋适合的情况：
右树插入新的节点，导致祖先节点不平衡

操作：

1. 将右节点的左子树变为祖先节点的右子树
2. 将祖先节点变为父节点的左子树

void RotateL(Node* parent)			//右单旋
{Node* subR = parent->_right;	//subR是parent的右节点Node* subRL = subR->_left;		//subRL是subR的左节点parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parent->_parent->_left == parent){parent->_parent->_left = subR;}else{parent->_parent->_right = subR:}subR->_parent = parent->_parent;}parent->_bf = 0;subR->_bf = 0;
}

右单旋

和上面的逻辑相同，只是新增节点放在了左子树，要向右旋转

	void RotateR(Node* parent)			//右单旋{Node* subL = parent->_left;		//subL是parent的左节点Node* subLR = subL->_right;		//subLR是subL的右节点parent->_left = subLR;if (subLR){subLR->_parent = parent;}subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parent->_parent->_left == parent){parent->_parent->_left = subL;}else{parent->_parent->_right = subL:}subL->_parent = parent->_parent;}parent->_bf = 0;subL->_bf = 0;}

左右双旋

旋转的代码相同，就是对于平衡因子的处理需要注意
分四种情况考虑

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{throw("false");}}

右左双旋

	void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

判断是否平衡

我们再写一个接口来判断给的树是否平衡

	int _Height(Node* root){if (root == nullptr){return 0;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool _IsBlance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (abs(leftHeight - rightHeight) >= 2){throw("不平衡");}if (rightHeight - leftHeight != root->_bf){throw("平衡因子异常");}return _IsBlance(root->_left)&& _IsBlance(root->_right);}

优化：求高度

我们可以发现，这段代码还可以优化，因为每一次的高度都是要重新求的，有很多重复工作。

所以，我们可以增加一个参数，

bool _IsBlance(Node* root, int& height);

这样树的高度就会再函数调用结束后被传出来，并且不用修改返回值

	bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout <<root->_kv.first<<"不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first <<"平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}bool IsBalance(){int height = 0;return _IsBalance(_root, height);}

结语

AVL树比搜索树要更优秀，但具体逻辑（指旋转）要更复杂，希望对你有帮助！！