AVL 树的旋转

本文主要是介绍AVL 树的旋转，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

什么是 AVL 树？

AVL 树是一种自平衡二叉搜索树（Binary Search Tree, BST），以其发明者 G. M. Adelson-Velsky 和 E. M. Landis 的名字命名。它的特点是对于任意一个节点，其左右子树的高度差（平衡因子）不超过 1，这确保了 AVL 树的高度在 O(log n) 的范围内，从而保证了插入、删除和查找操作的时间复杂度都是 O(log n)。

节点结构

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

平衡因子

对于每个节点，平衡因子定义为其左子树高度减去右子树高度的差值，可能的取值为 -1, 0, 1。当平衡因子的绝对值大于 1 时，表示树不平衡，需要进行旋转操作来恢复平衡。

AVL 树的旋转操作

AVL 树中主要通过旋转来保持平衡。旋转分为四种类型（注意看图，再配合代码思考）：

右单旋

新节点插入较高左子树的左侧---左左：右单旋

插入左子树的右侧属于下面的两次旋转的情况，下面左单旋同理

 左子树高度过高导致平衡因子大于 | 1 |

同时这里面我们需要考虑subRL可能不存在的情况，这时候 subRL的父节点不能更新（空指针）

 节点更新需要注意更新顺序，旋转完成后，更新节点的平衡因子

void RotateR(Node * pParent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//防止subLR为nullptr的情况if (subLR)subLR->_parent = parent;subL->_right = parent;Node* Parent = parent->_parent;parent->_parent = subL;subL->_parent = Parent;if (Parent == nullptr){_root = subL;}else{if (Parent->_left == parent){Parent->_left = subL;}else{Parent->_right = subL;}}subL->_bf = parent->_bf = 0;
}

左单旋

新节点插入较高右子树的右侧---右右：左单旋

  右子树高度过高导致平衡因子大于 | 1 |

同时也要考虑 subRL不存在的情况

void RotateL(Node * parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;subR->_left = parent;Node* Parent = parent->_parent;parent->_parent = subR;subR->_parent = Parent;if (Parent == nullptr){_root = subR;}else{if (Parent->_left == parent){Parent->_left = subR;}else{Parent->_right = subR;}}subR->_bf = parent->_bf = 0;
}

左右旋转

新节点插入较高左子树的右侧---左右：先左单旋再右单旋

我们需要记录subRL的平衡因子 是 1 还是 -1 用来判断插入位置是左边还是右边用来更新parent等节点的平衡因子

 

先针对subL左单旋，再针对parent右单旋 

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

 右左旋转

同上旋转

void RotateRL(Node * parent)
{Node* subR = parent->_reft;Node* subRL = subL->_Light;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (1 == bf)subR->_bf = 1;else if (-1 == bf)parent->_bf = -1;
}

ps：注意看图

这篇关于AVL 树的旋转的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---