无为教育网站,四川建设厅网站登录不上咋办,网站制作及排名优化,网站建设公司方案目录
一.AVL树的概念
二、AVL树节点的定义
三、AVL树的插入
3.1插入方法
四、AVL树的旋转
1. 新节点插入较高左子树的左侧---左左#xff1a;右单旋
2. 新节点插入较高右子树的右侧---右右#xff1a;左单旋
3.新节点插入较高左子树的右侧---左右#xff1a;先左单旋…
目录
一.AVL树的概念
二、AVL树节点的定义
三、AVL树的插入
3.1插入方法
四、AVL树的旋转
1. 新节点插入较高左子树的左侧---左左右单旋
2. 新节点插入较高右子树的右侧---右右左单旋
3.新节点插入较高左子树的右侧---左右先左单旋再右单旋
4.新节点插入较高右子树的左侧---右左先右单旋再左单旋
5.AVL树的插入代码
五、AVL树的验证
六、AVL树的性能 一.AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 平衡因子 右子树高度 - 左子树高度 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 搜索时 间复杂度O( )。
二、AVL树节点的定义 AVL树每个节点都会记录他的左右孩子和父节点 并且每个节点记录一下自己的平衡因子 用模板T存储他的数据 templateclass T
struct AVLTreeNode
{AVLTreeNode(const T data): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _pLeft; // 该节点的左孩子AVLTreeNodeT* _pRight; // 该节点的右孩子AVLTreeNodeT* _pParent; // 该节点的双亲T _data;int _bf; // 该节点的平衡因子
};
三、AVL树的插入 对于AVL树的插入因为它是要结合AVL树的旋转的所以在本文中AVL树的插入和AVL树的旋转合起来才是完整的插入过程所以这里我们主要讲一下插入的大体的一个过程具体插入的细节及代码实现后面实现 AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步1. 按照二叉搜索树的方式插入新节点 2. 调整节点的平衡因子 3.1插入方法
1. 先按照二叉搜索树的规则将节点插入到AVL树中 2. 新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子并检测是否破坏了AVL树的平衡性新节点插入后他的父节点的平衡因子一定需要调整在插入之前父节点 的平衡因子分为三种情况-10, 1分以下两种情况 1. 如果新节点插入到父节点的左侧只需给父节点的平衡因子-1即可 2. 如果新节点插入到父节点的右侧只需给父节点的平衡因子1即可 此时父节点的平衡因子可能有三种情况0正负1 正负2 1. 如果父节点的平衡因子为0说明插入之前父节点的平衡因子为正负1插入后被调整成0此 时满足AVL树的性质插入成功 2. 如果父节点的平衡因子为正负1说明插入前父节点的平衡因子一定为0插入后被更新成正负1此时以父节点为根的树的高度增加需要继续向上更新 3. 如果父节点的平衡因子为正负2则父节点的平衡因子违反平衡树的性质需要对其进行旋转 处理 四、AVL树的旋转 如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种 1. 新节点插入较高左子树的左侧---左左右单旋 最终根据我们图上所画的这种右单选的情况我们可以按照上图写出右旋转的代码 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;// 更新节点之间的连接关系parent-_left subLR;if (subLR){subLR-_parent parent;}subL-_right parent;Node* pparent parent-_parent;parent-_parent subL;if (!pparent){_root subL;subL-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subL;}else if (pparent-_right parent){pparent-_right subL;}subL-_parent pparent;}// 更新平衡因子parent-_bf subL-_bf 0;} 根据上图判断 我们定义了父亲的左subL和父亲左的右subLR 首先根据上图第一步把父亲左的右节点给父亲的左如果subLR不为空更新一下subLR的父节点 然后把parent链接在subL的右边记录一下父亲的父亲pparent一会需要subL更新父节点 更改父亲的父节点为subL 下面就开始更新subL的父节点了 第一步判断旋转前的person是不是根节点如果是根节点的父亲pparent为空然后把根节点更新为subL把subL的父节点置为空 如果不是根节点判断以前pparent的左边还是右边是父亲parent让pparent指向父亲改为指向subL再把subL的父节点更新为pparent 最后更新平衡因子把parent和subL的平衡因子置为0 2. 新节点插入较高右子树的右侧---右右左单旋 最终根据我们图上所画的这种右单选的情况我们可以按照上图写出左旋转的代码 // 左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;// 更新节点之间的连接关系parent-_right subRL;if (subRL)// subRL不为空才需要更新它的父亲{subRL-_parent parent;}subR-_left parent;Node* pparent parent-_parent;parent-_parent subR;if (!pparent)// parent为根时的处理{_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}// 更新平衡因子parent-_bf subR-_bf 0;}
对于左单旋解释左单旋跟右单旋 两者非常类似所以这里不再花费篇幅去讲解.
3.新节点插入较高左子树的右侧---左右先左单旋再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。
// 左右双旋void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int flag subLR-_bf;// 记录subLR的平衡因子最后要依据它来更新其他节点的平衡因子// 依次旋转RotateL(subL);RotateR(parent);// 根据subLR平衡因子的值更新不同插入情况下的平衡因子if (flag 1)// 说明是在subLR的右子树插入的那么subLR的左子树变为subL的右子树subL平衡因子变为-1subLR和parent的为0{subL-_bf -1;}else if (flag -1)// 说明是在subLR的左子树插入的subLR的右子树最后会被分给parent作为左子树parent的平衡因子变为-1subL和subLR的平衡因子变为0{parent-_bf 1;}}
4.新节点插入较高右子树的左侧---右左先右单旋再左单旋 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int flag subRL-_bf;// 依次旋转RotateR(subR);RotateL(parent);// 更新平衡因子if (flag 1){parent-_bf -1;}else if (flag -1){subR-_bf 1;}}
5.AVL树的插入代码
bool Insert(const pairk, v kv){// 空树的话就让插入的那个节点作为根if (!_root){_root new Node(kv);return true;}// 不是空树就按照搜索树的性质找到插入的位置和它的父亲Node* cur _root;Node* parent nullptr;while (cur){parent cur;if (cur-_kv.first kv.first){return false;}else if (cur-_kv.first kv.first){cur cur-_left;}else{cur cur-_right;}}// 创建要插入的节点Node* newNode new Node(kv);// 更新关系插入节点newNode-_parent parent;if (parent-_kv.first newNode-_kv.first){parent-_right newNode;}else{parent-_left newNode;}cur newNode;parent cur-_parent;while (parent){// 向上更新平衡因子if (cur parent-_left){--(parent-_bf);}else{(parent-_bf);}// 检查是否需要调整// 0的话就平衡了// -1或1的话还要向上更新// -2或2的话需要旋转处理if (parent-_bf 0)// 平衡因子为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){if (cur-_bf 1)// 右子树的右子树也高 -- 左单旋{RotateL(parent);}else if (cur-_bf -1)// 右子树的左子树也高 -- 右左双旋{RotateRL(parent);}}else if (parent-_bf -2)// 左子树高{if (cur-_bf -1)// 左子树的左子树也高 -- 右单旋{RotateR(parent);}else if (cur-_bf 1)// 左子树的右子树也高 -- 左右双旋{RotateLR(parent);}}break;}}return true;}
五、AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确 int Height(Node* root){if (root nullptr)return 0;int RightHeight Height(root-_left);int LeftHeight Height(root-_right);return RightHeight LeftHeight ? RightHeight 1 : LeftHeight 1;}bool _IsBalance(Node* root){if (root nullptr)return true;//空的话应该返回true因为不影响平衡int LeftHeight Height(root-_left);//迭代计算高度int RightHeight Height(root-_right);if (RightHeight - LeftHeight ! root-_bf)//仅仅判断高度是不够的有可能平衡因子还是错了所以要对每个平衡因子做检查{cout 平衡因子现在是: root-_bf endl;cout 平衡因子应该是 (RightHeight - LeftHeight) endl;return false;//平衡因子错了直接返回}return RightHeight - LeftHeight 2 _IsBalance(root-_left) _IsBalance(root-_right);}六、AVL树的性能 AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合
