网站服务公司特点,重庆建筑工程网, 上app下载,小码短链接文章目录 前提一、AVL树的结构定义二、AVL的插入#xff08;重点#xff09;1. 插入的结点在较高左子树的左侧#xff08;右单旋#xff09;2. 新节点插入较高右子树的右侧#xff08;左单旋#xff09;3.新结点插入较高右子树的左侧#xff08;先右单旋再左单旋#x… 文章目录 前提一、AVL树的结构定义二、AVL的插入重点1. 插入的结点在较高左子树的左侧右单旋2. 新节点插入较高右子树的右侧左单旋3.新结点插入较高右子树的左侧先右单旋再左单旋4. 新节点插入较高左子树的右侧先左单旋再右单旋 插入的整体代码 前提
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查 找元素相当于在顺序表中搜索元素效率低下。
因此两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决上述问题的方法 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(-1、0、1)即可降低树的高度从而减少平均搜索长度。 由此该树被称为AVL树即两位科学家名字的第一个字母。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树的高度差(简称平衡因子)的绝对值不超过1 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在O(logN)搜索时间复杂度O(logN)。 提示以下是本篇文章正文内容下面案例可供参考
一、AVL树的结构定义
树节点的结构创建
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv; //键值对来存储 K AND Vint _bf;//平衡因子//AVL树并没有规定必须要选择设计平衡因子只是一个实现的选择方便控制//构造函数AVLTreeNode(const pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};树的框架创建 templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node; //结点typedef
public:
//......
private:Node* _root nullptr;
};二、AVL的插入重点
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子 寻找位置-创建结点-插入节点-更新平衡因子-调整子树-形成AVL树 1. 插入的结点在较高左子树的左侧右单旋
这样会造成parent的平衡因子变成-2 当前节点不是新增节点的平衡因子变成-1
//右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* pParent parent-_parent;subL-_right parent;parent-_parent subL;if (pParent nullptr){_root subL;_root-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else pParent-_right subL;subL-_parent pParent;}// 更新平衡因子parent-_bf subL-_bf 0;}
2. 新节点插入较高右子树的右侧左单旋
这样会造成parent的平衡因子变成2当前节点不是新增节点的平衡因子变成1
//左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}Node* pParent parent-_parent;subR-_left parent;parent-_parent subR;if (pParent nullptr){_root subR;_root-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subR;}else pParent-_right subR;subR-_parent pParent;}//更新平衡因子subR-_bf parent-_bf 0;}3.新结点插入较高右子树的左侧先右单旋再左单旋
会造成parent的平衡因子变成2 当前节点不是新增节点平衡因子变成-1
void RotateRL(Node* parent){Node* subR parent-_right; //左子树60Node* subRL subR-_left;// 右子树的左子树90int bf subRL-_bf;// 记录SubRLd 平衡因子// 先以SubR为轴进行右单旋RotateR(parent-_right);// 再进行左单旋RotateL(parent);if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else if (bf 0){parent-_bf 0;subR-_bf 0;subRL-_bf 0;}else if (bf 1){parent-_bf -1;subR-_bf 0;subRL-_bf 0;}else assert(0);}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else assert(0);}4. 新节点插入较高左子树的右侧先左单旋再右单旋
这样会造成parent的平衡因子变成-2 当前结点的平衡因子变成1 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 0){parent-_bf 0;subL-_bf 0;subLR-_bf 0;}else if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subL-_bf -1;parent-_bf 0;subLR-_bf 0;}else assert(0);}插入的整体代码
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;//parent是cur的父节点Node* cur _root;//cur往下走while (cur){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;//AVL树不允许有重复值}}//走到这里就表示找到我们要插入kv值的正确位置了,准备插入节点..........cur new Node(kv);if (parent-_kv.first kv.first)//如果new的节点比父节点大那么父节点的右指针指向new节点{parent-_right cur;cur-_parent parent;}else//如果new的节点比父节点小那么父节点的左指针指向new节点{parent-_left cur;cur-_parent parent;}//开始更新平衡因子while (parent)//更新到根节点才算更新完平衡因子{//1、如果是右子树新增结点那么父节点的_bf就加一//2、如果是左子树新增结点那么父节点的_bf就减一//1和-1大家可以自己决定只要是对的怎么都行if (cur parent-_right){parent-_bf;}else{parent-_bf--;}// 是否继续更新依据子树的高度是否变化// 1、parent-_bf 0说明之前parent-_bf是 1 或者 -1// 说明之前parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新// 2、parent-_bf 1 或 -1 说明之前是parent-_bf 0两边一样高现在插入一边更高了// parent所在子树高度变了继续往上更新// 3、parent-_bf 2 或 -2说明之前parent-_bf 1 或者 -1现在插入严重不平衡违反规则// 就地处理--旋转// 旋转// 1、让这颗子树左右高度不超过1// 2、旋转过程中继续保持他是搜索树// 3、更新调整孩子节点的平衡因子// 4、让这颗子树的高度跟插入前保持一致//如果新增节点cur使得父节点parent的平衡因子变成了0那么表示该插入节点对整棵树的平衡因子没有影响//不用向上判断可以直接退出if (parent-_bf 0){break;}//如果新增cur使得父节点parent的平衡因子变成了1或者-1那么我们要继续向上判断是否对上面的节点的//说明之前的平衡被打破子树的高度变化了有可能会造成父节点的平衡因子出现问题else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}//当平衡因子出现2 or -2 的时候就需要调整子树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 if (parent-_bf 2 cur-_bf -1)//右左旋{RotateRL(parent);}else{assert(false);}break;//旋转完一次就可以退出了因为旋转的时候我们已经向上判断了除非新插入否则树就是avl树}else{assert(false);//这里直接报错走到这里树就已经不是AVL树了}}return true;
}
