做仿站如何获取网站源码,windows2012做网站,网页设计橙色代码,网站建设公司如何挖掘客户目录 什么是AVL树
AVL树的定义
插入函数的实现
左单旋和右单旋
左右双旋与右左双旋 什么是AVL树 AVL树实际上就是二叉搜索树的一种变体#xff0c;我们都知道二i叉搜索树可以将查找的时间复杂度提升到O(logn)#xff0c;极大提升搜索效率。但是在极端情况下#xff0c;当…目录 什么是AVL树
AVL树的定义
插入函数的实现
左单旋和右单旋
左右双旋与右左双旋 什么是AVL树 AVL树实际上就是二叉搜索树的一种变体我们都知道二i叉搜索树可以将查找的时间复杂度提升到O(logn)极大提升搜索效率。但是在极端情况下当按顺序向树插入节点时二叉树严重不平衡相当于退化成了链表此时查找的时间复杂度就变为了O(n)这并不是我们希望看到的。 那么有没有什么方式可以让二叉搜索树保持一定的平衡性从而不至于导致查找效率严重降低呢AVL树也就是高度平衡二叉树给出的解决方案是 1. 二叉树的每个节点都有一个平衡因子平衡因子等于左子树高度减右子树高度的值 2. 平衡因子的绝对值不能超过1 3. 当插入或删除节点导致平衡因子绝对值超过1时进行旋转 AVL树的定义 让我们来思考一下要实现前面描述的功能AVL树的单个节点应该有哪些成员变量呢 1. 首先肯定要有左右子树的节点 2. 然后为了旋转时能够找到父亲我们还需要存父亲节点 3. 为了确保平衡我们要将左右高度差作为平衡因子保存 4. 最后还有搜索要用到的键值对 AVL树节点类定义
templateclass K, class V
struct AVLTreeNode
{// 由于插入节点时要向上更新所以使用三叉链结构AVLTreeNodeK, V* left;AVLTreeNodeK, V* right;AVLTreeNodeK, V* parent; pairK, V _kv; // 键值int _bf; // 平衡因子AVLTreeNode(const pairK, V kv):_kv(kv), left(nullptr),right(nullptr),parent(nullptr),_bf(0){}
};
那么AVL树的定义就应该是
templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
private:Node* _root nullptr;
};
插入函数的实现 让我们先明确一下AVL树插入一个节点要做的事 1. 按照二叉搜索树的规则找到插入位置进行插入 2. 根据左右高度差得到平衡因子 3. 当平衡因子绝对值大于1时进行旋转处理 首先二叉树搜索规则就是当插入节点的键小于当前节点的键时和当前节点的左子树进行比较当插入节点的键大于当前节点的键时和当前节点的右子树进行比较否则说明插入节点的键已经存在这不符合二叉搜索树的规则直接报错。我们按照这个规则找到可以插入的位置然后将新节点插入。 插入完成之后我们开始更新平衡因子当新节点位于父亲的左边时bf减1当位于父亲的右边时bf加1。修改完父亲的平衡因子后进行判断 1. 如果当前父亲平衡因子值为0说明高度差没有改变不需要进行处理直接break即可。 2. 如果当前父亲平衡因子值为1/-1说明插入导致高度差改变了这可能会导致祖先节点的平衡因子绝对值超过1所以需要继续往上更新祖先的平衡因子 3. 如果更新后的祖先的平衡因子绝对值超过1就需要进行旋转处理 为了更直观地理解这个过程让我们来看一个简单的例子
插入新节点导致祖先失去平衡 通过旋转使AVL树恢复平衡 我们可以看到这棵树的根节点平衡因子在插入新节点后由1变为2而进行一次左旋之后平衡因子更新为0恢复了平衡。
由于旋转涉及到的情况比较多且有一些细节操作而这只是其中最简单的一种情况所以我们先写出AVL树插入的基本框架之后再对各个需要旋转的情况分别进行处理。 bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr; // 用于记录插入位置的父亲节点Node* cur _root; // 用于比较查找到插入位置while (cur){parent cur;if (kv.first cur-_kv.first){cur cur-left;}else if (kv.first cur-_kv.first){cur cur-right;}// 搜索二叉树不支持重复key值的情况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){// 旋转处理……}// 说明旋转有问题,不能在|bf|2时恢复平衡else{assert(false);}}return true;}
左单旋和右单旋 先来看左单旋如下图所示是左单旋最简单的情况 但显然需要左单旋的情况通常会更复杂些所以我们实现左单旋时需要考虑具有通用性的情况 可以发现我们的左单旋操作似乎只需要让parent的右指向subRL然后让subR的左指向parent。但大家可别忘了我们定义AVL树节点时为了方便向上更新设计的是三叉链结构所以还需要更新subRL和parent的父亲节点。除此之外还需要考虑到parent可能是祖先节点的孩子所以如果parent是AVL树的根节点将根节点更新为subR并将subR的父亲更新为nullptr如果parent是祖先节点的孩子则将祖先节点的孩子更新为subR并将subR的父亲更新为父亲节点。 指针朝向修改完后我们还需要修改发生高度变化的节点的平衡因子如上图所示parent的平衡因子由2变为0subR的平衡因子由1变为0。 void RotateL(Node* parent)
{// 在修改之前先保存祖父节点Node* grandpa parent-parent;// 事实上对于左旋这一情况我们要修改的只有parent,subR,subRL最多再加个grandpa的指针朝向Node* subR parent-right;Node* subRL subR-left;// 进行左旋操作parent-right subRL;subR-left parent;// 之后还得把父指针也一起修改了parent-parent subR;if(subRL)subRL-parent parent;// 这棵树不是子树if (parent _root){_root subR;_root-parent nullptr;}// 这棵树是子树else{// 是祖父节点的左子树if (grandpa-left parent){grandpa-left subR;}// 是祖父节点的右子树else{grandpa-right subR;}subR-parent grandpa;}parent-_bf subR-_bf 0;} 接下来是右单旋在局部子树左偏时我们通过右旋来进行处理 由于在左单旋部分我们已经详细讲解过了右单旋其实就相当于反过来所以就不再讲解一遍了。 void RotateR(Node* parent){// 在修改之前先保存祖父节点Node* grandpa parent-parent;// 事实上对于右旋这一情况我们要修改的只有parent,subL,subLR最多再加个grandpa的指针朝向Node* subL parent-left;Node* subLR subL-right;// 进行右旋操作parent-left subLR;subL-right parent;// 之后还得把父指针也一起修改了parent-parent subL;if (subLR)subLR-parent parent;// 需要考虑现在调整的这棵树是子树的情况if (parent _root){_root subL;_root-parent nullptr;}else{// 是祖父节点的左子树if (grandpa-left parent){grandpa-left subL;}// 是祖父节点的右子树else{grandpa-right subL;}subL-parent grandpa;}parent-_bf subL-_bf 0;
}
左右双旋与右左双旋 我们还是先来看一个左右双旋的简单例子可以看到我们先通过一次左旋把这棵子树修改为了单纯的左偏而处理左偏我们只需要进行一次右旋即可。 再来看更普遍的情况 事实上由于我们已经有了左旋和右旋的代码所以进行双旋时可以直接复用左旋和右旋函数所以双旋主要考虑的是如何更新平衡因子。
一共有三种情况
第一种60就是新增节点此时平衡因子全部更新为0
第二种新增节点向b插入此时parent的因子为1其余因子为0
第三种新增节点向c插入此时subL的因子为-1其余因子为0
大家可以自己分别画一下这三种情况其实自己动手画一下就很好理解了让我们看代码 void RotateLR(Node* parent){Node* subL parent-left;Node* subLR subL-right;// 啊啊啊原来是这里错了调试了一个晚上。。// int bf parent-_bf;int bf subLR-_bf;RotateL(parent-left);RotateR(parent);if (bf 0){parent-_bf subL-_bf subLR-_bf 0;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}//else//{// assert(false);//}}右左双旋和左右双旋完全类似也是三种情况其实理解了左右双旋右左双旋就很好写了 void RotateRL(Node* parent){Node* subR parent-right;Node* subRL subR-left;// 提前记录修改点的平衡因子int bf subRL-_bf;// 先右旋RotateR(parent-right);// 再左旋RotateL(parent);if (bf 0){// 自己就是新增节点parent-_bf subR-_bf subRL-_bf 0;}else if (bf -1){// 新增节点位于subRL的左子树parent-_bf 0;subRL-_bf 0;subR-_bf 1;}else if (bf 1){// 新增节点位于subRL的右子树parent-_bf -1;subRL-_bf 0;subR-_bf 0;}//else//{// assert(false);//}}
