当前位置：首页 > news >正文

C++AVL树

news 2025/8/9 13:13:36

1.AVL树简单介绍

AVL 树是一种自平衡二叉搜索树（Self-Balanced Binary Search Tree），由 Adelson-Velsky 和 Landis 在 1962 年提出，因此得名。它在二叉搜索树的基础上增加了自平衡机制，确保树的高度始终保持在 O (log n) 级别，从而保证高效的查找、插入和删除操作。

特性：

二叉搜索树的特性
平衡条件：树中每个节点都添加了平衡因子，平衡因子为该节点右子树 - 左子树的值，平衡因子取值范围为1，0，-1.
自平衡机制：当插入或删除操作导致平衡被破坏（某节点平衡因子绝对值 > 1）时，通过旋转操作恢复平衡，旋转不会破坏二叉搜索树的特性。

2.AVL树实现

2.1AVL树节点结构

	template<class K,class V>struct AVLTreeNode{pair<K, V> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){ }};

和二叉搜索树相比，AVL树多一个平衡因子，用来在树出现某一子树过高时，及时发现并作出调整。
在节点内部多添加了指向父节点的指针，方便后续会对树的结构进行调整。

2.2AVL树的插入

元素插入的基本过程：

按二叉搜索树的规则找到要插入元素的位置
插入节点后会影响元素所在子树的高度，影响祖先节点的平衡因子。
更新新增节点所在路径的节点的平衡因子
向上更新过程中判断节点的平衡因子是否处于正确范围。
如果出现节点平衡因子更新后变为2/-2情况，对所在子树进行调整（旋转）
更新过程没出现问题，如果途中存在节点平衡因子更新后变为0，则提前停止更新，否则一直更新，直到根节点。

2.2.1平衡因子更新

平衡因子=右子树高度 - 左子树高度
插入节点会影响子树的高度，新插入节点在父节点的左子树，父节点平衡因子--，新插入节点在父节点的右子树，父节点平衡因子++。

平衡因子向上更新条件：

插入前parent->_bf==0，插入节点后 parent->_bf 变为1/-1，说明parent节点所在子树的高度发生变化，会影响祖先节点的平衡因子，需要继续向上更新。
插入前parent->_bf==1/-1，插入节点后parent->_bf变为0，说明新节点插入在父节点子树低一侧，填补了空缺，parent所在子树高度不变，不影响parent以上节点，停止更新。
插入前parent->_bf==1/-1，插入节点后parent->_bf变为2/-2，说明parent所在子树出现问题，新增节点插入在高的子树上，导致parent左右子树高度差>1,需要对parent所在子树进行旋转。
旋转：把parent节点和两个子树中低的那个，向下旋转，高的子树向上旋转，使parent所在子树平衡。

需要旋转：

中途停止：

更新到根节点：

2.2.2插入节点和更新平衡因子代码：

if (_root == nullptr)
{_root = new Node(kv);return true;
}Node* parent = _root;
Node* cur = _root;
while (cur)
{if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}
}
cur = new Node(kv);
if (kv.first < parent->_kv.first)
{parent->_left = cur;
}
else
{parent->_right = cur;
}cur->_parent = parent;//调整平衡因子
while (parent)
{if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if(parent->_bf==1 || parent->_bf==-1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{return false;}
}

2.2.3旋转

右旋：

左子树高时，使用右旋，将低的右子树向下压
在旋转前，如果parent节点有前置节点，把该前置节点保存，用于与cur节点连接。
如果parent节点为根节点，则在旋转后把_root指向cur节点，把cur的_parent指针置空。
当parent节点为-2时，说明相当于稳定结构（1/-1），左子树比右子树高2个节点的大小，所以把parent节点向下压，使其成为该树的一个子节点，让cur节点成为该树的根节点。
这样高的一边向上挪，高度差-1，低的一边向下挪，高度差-1，旋转后从高度差为2，变为平衡。
cur节点的右子树中的节点值的范围都处于 “大于cur节点，小于parent节点” 可以把该子树看作一个整体，都小于parent节点，在旋转时，可以无脑把该子树连接到parent->left.
新增节点所在子树（cur->left）被向上移动，（cur->right）子树成为parent->left，被向下移动
（parent->right）子树一次性向下移动了两个节点位置，时高度差从2变为0.
由图中可以看出在旋转后cur和parent节点的平衡因子都变为了0,在写代码时在旋转函数的最后，直接把cur和parent的平衡因子无脑改为0即可。

右旋代码实现：

void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;Node* pparent = parent->_parent;cur->_right = parent;parent->_parent = cur;parent->_left = curright;if (curright){curright->_parent = parent;}if (_root == parent){_root = cur;cur->_parent = nullptr;}else{cur->_parent = pparent;if (parent == pparent->_left){pparent->_left = cur;}else{pparent->_right = cur;}}cur->_bf = parent->_bf = 0;
}

左旋：

左旋和右旋类似
这里把旋转前平衡因子为2的节点被称为parent（上图值为10的节点），值为15的节点被称为cur。
过程：cur的左子树成为parent的右子树，parent成为cur新的左子树
注意：parent是否有前置节点，是否为根节点

代码实现：

void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;Node* pparent = parent->_parent;cur->_left = parent;parent->_parent = cur;parent->_right = curleft;if (curleft){curleft->_parent = parent;}if (_root == parent){_root = cur;cur->_parent = nullptr;}else{cur->_parent = pparent;if (parent == pparent->_left){pparent->_left = cur;}else{pparent->_right = cur;}}cur->_bf = parent->_bf = 0;
}

右左双旋：

右左双旋：当parent平衡因子为2，cur平衡因子为-1，插入节点后并非形似一条直线。
第一步要先把该（新增节点后只有3个节点）折线变为直线：以cur节点为中心右旋（把12--15这个类似杠铃的图形顺时针旋转120度），此处的右旋原理就是右单旋，可以直接复用。
右旋结束后形成一条“直线”此时为左单旋的场景，直接复用左单旋即可。

代码实现：

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

左右双旋：

左右双旋：当parent平衡因子为2，cur平衡因子为-1，插入节点后并非形似一条直线。
第一步要先把该（新增节点后只有3个节点）折线变为直线：以cur节点为中心左旋（把8--9这个类似杠铃的图形逆时针旋转120度），此处的左旋原理就是左单旋，可以直接复用。
左旋结束后形成一条“直线”此时为右单旋的场景，直接复用右单旋即可。

代码实现：

void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}else if(bf==-1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}}

2.2.4AVL树查找

复用二叉搜索树的查找即可

Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}

3.AVL树节点，插入，查找衔接

	template<class K,class V>struct AVLTreeNode{pair<K, V> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){ }};template<class K, class V>class AVLTree{typedef AVLTreeNode<K,V> Node;public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = _root;Node* cur = _root;while (cur){if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else if(kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (kv.first < parent->_kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//调整平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 0){break;}else if(parent->_bf==1 || parent->_bf==-1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{return false;}}return true;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalanceTree(){return _IsBalanceTree(_root);}int Height(){return _Height(_root);}int Size(){return _Size(_root);}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";//cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}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 _IsBalanceTree(Node* root){if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int bf = rightHeight - leftHeight;if (abs(bf) >= 2 || bf != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return _IsBalanceTree(root->_left)&& _IsBalanceTree(root->_right);}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* pparent = parent->_parent;cur->_right = parent;parent->_parent = cur;parent->_left = curright;if (curright){curright->_parent = parent;}if (_root == parent){_root = cur;cur->_parent = nullptr;}else{cur->_parent = pparent;if (parent == pparent->_left){pparent->_left = cur;}else{pparent->_right = cur;}}cur->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* pparent = parent->_parent;cur->_left = parent;parent->_parent = cur;parent->_right = curleft;if (curleft){curleft->_parent = parent;}if (_root == parent){_root = cur;cur->_parent = nullptr;}else{cur->_parent = pparent;if (parent == pparent->_left){pparent->_left = cur;}else{pparent->_right = cur;}}cur->_bf = parent->_bf = 0;}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(cur);RotateL(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curleft->_bf = 0;}else if(bf == 1){parent->_bf = -1;cur->_bf = 0;curleft->_bf = 0;}else if (bf == -1){parent->_bf = 0;cur->_bf = 1;curleft->_bf = 0;}}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}else if(bf==-1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}}Node* _root = nullptr;};

查看全文

http://www.lryc.cn/news/614569.html