最新上线的手游,seo价格查询公司,近五年关于网站建设的参考文献,中小型电子商务网站AVL树 AVL是两名俄罗斯数学家的名字#xff0c;以此纪念 与二叉搜索树的区别
AVL树在二叉搜索树的基础上增加了新的限制#xff1a;需要时刻保证每个树中每个结点的左右子树高度之差的绝对值不超过1 因此#xff0c;当向树中插入新结点后#xff0c;即可降低树的高度…AVL树 AVL是两名俄罗斯数学家的名字以此纪念 与二叉搜索树的区别
AVL树在二叉搜索树的基础上增加了新的限制需要时刻保证每个树中每个结点的左右子树高度之差的绝对值不超过1 因此当向树中插入新结点后即可降低树的高度从而减少平均搜索长度 平衡因子
为了能方便处理平衡二叉搜索树的限制条件通常会引入平衡因子的概念
某一节点的平衡因子其右子树高度-其左子树高度 在AVL树中并不是一定需要平衡因子的有些代码的AVL树就没有平衡因子。 这里引入平衡因子只是更方便的去判断树是否平衡了 AVL树的效率推算 我们知道树的增删查改的效率是与树的高度有关的
假如AVL树是满二叉树此时2h-1N
假如AVL树不是满二叉树设最底层的节点个数为X此时2h-XN。X的范围为[1最后一层结点树-1]
此时上述两种情况都可以得出树的高度的数量级为logN因此增删查改的时间复杂度为O(logN)
AVL树的节点设计
首先与二叉搜索树相比每个节点多了一个平衡因子balance factor
其次为了满足一定需求还多了个_parent指针指向节点的父亲
templateclass K,class V
struct AVLTreeNode
{pairK, V _kv;AVLTreeNodeK,V* _left;AVLTreeNodeK,V* _right;AVLTreeNodeK,V* _parent;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;
public://……
private:Node* _rootnullptr;
};AVL树的插入 在面试时几乎不会让你手撕AVL树的插入。重要的是了解思想。 但让你手撕一个旋转是有可能的 插入的逻辑
AVL树是在二叉搜索树的基础上引入了平衡因子因此AVL树的插入分为两个步骤
按照二叉搜索树的方式插入新节点多了个链接_parent插入后更新节点的平衡因子
首先注意新插入的节点只会对其父亲和其祖先的平衡因子造成影响
插入节点的_parent的平衡因子是一定需要调整的在插入之前其_parent的平衡因子有三个可能值1、-1、0插入节点后
如果插入到_parent的左侧则_parent的平衡因子–即可如果插入到_parent的右侧则_parent的平衡因子即可
此时_parent的平衡因子可能有三大种情况
如果_parent的平衡因子为0说明插入之前的平衡因子为正负1插入后被调整成0满足AVL树的性质插入成功插入结束如果_parent的平衡因子为±1说明插入之前的平衡因子为0此时树的高度增加那么就需要继续向上更新祖先的平衡因子直至某一祖先的平衡因子为0或者更新到根节点才算插入成功停止更新插入结束。如果_parent的平衡因子为±2此时违反了AVL树的性质需要进行旋转处理。处理完成则算插入成功插入结束
更新平衡因子
最坏的情况是一直更新到根如下图
因此在更新平衡因子时我们的循环条件为while(parent) 因为只有根节点的_parent为空。所以当更新完根节点的平衡因子后循环结束 while (parent)
{if (cur parent-_left)//节点插入在父亲左边{parent-_bf--;}else if (cur parent-_right)//节点插入在父亲右边{parent-_bf;}//进一步判断祖先节点的平衡因子if (parent-_bf 0)//父亲的平衡因子为0循环结束{break;}else if (parent-_bf 1 || parent-_bf -1)//父亲的平衡因子为1或-1则需要继续向上调整{cur parent;parent cur-_parent;}else if (parent-_bf 2 || parent-_bf -2)//父亲的平衡因子为2或-2则需要旋转且选择完后树一定平衡故结束循环{//左单旋if (parent-_bf 2 cur-_bf 1){RotateL(parent);}//右单旋if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//右左双旋if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}//左右双旋if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else//其他情况此时说明在插入之前树就已经不是平衡树了{assert(false);}
}最后一个else中的assert(false)看似是无用的因为parent不可能是绝对值大于2的。但是代码都是人写的不可排除一开始的树就是有问题的。因此这句代码很重要 AVL树的旋转
根据节点插入位置的不同AVL树的旋转分为四种
新节点插入较高左子树的左侧–左左右单旋新节点插入较高右子树的右侧–右右左单旋新节点插入较高左子树的右侧—左右先左单旋再右单旋左右双旋新节点插入较高右子树的左侧—右左先右单旋再左单旋右左双旋
何时使用何种旋转
假如以pParent为根的子树不平衡即pParent的平衡因子为2或者-2分以下情况考虑: pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pSubR 当pSubR的平衡因子为1时执行左单旋 当pSubR的平衡因子为-1时执行右左双旋 pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pSubL 当pSubL的平衡因子为-1是执行右单旋 当pSubL的平衡因子为1时执行左右双旋
旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新
右单旋 上图在插入前AVL树是平衡的。新节点插入到30的左子树(注意此处不是左孩子)中30左子树增加了一层导致以60为根的二叉树不平衡要让60平衡只能将60左子树的高度减少一层右子树增加一层即将左子树往上提这样60转下来因为60比30大只能将其放在30的右子树而如果30有右子树右子树根的值一定大于30小于60只能将其放在60的左子树旋转完成后更新节点的平衡因子即可
在旋转过程中有以下几种情况需要考虑 cur节点的右孩子可能存在也可能不存在 parent可能是根节点也可能是子树 如果是根节点旋转完成后要更新根节点 如果是子树可能是某个节点的左子树也可能是右子树 这两点是所有旋转情况都需要考虑的 右单旋的核心操作把cur的右孩子给到parent的左再把parent给到cur的右
代码
void RotateR(Node* parent)//parent的平衡因子绝对值为2
{Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;//把cur的右孩子给到parent的左if (curright)//如果cur的右孩子存在则更新其父亲为parent{curright-_parent parent;}cur-_right parent;//再把parent给到cur的右Node* ppnode parent-_parent;//记录parent的原父亲节点用于对cur的父亲进行更新parent-_parent cur;//更新parent的父亲//对cur的父亲进行更新if (parent _root)//parent即为根节点{_root cur;cur-_parent nullptr;//那么cur作为新的根其父亲为空}else//parent是子树{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}cur-_bf parent-_bf 0;//更新完后平衡因子一定为0
}左单旋 左单旋的核心操作与右单旋的核心操作正好是镜像的
左单旋的核心操作把cur的左给parent的右再把parent给到cur的左
代码
void RotateL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;//把cur的左给parent的右if (curleft)//如果cur的左存在则更新其父亲{curleft-_parent parent;} cur-_left parent;//再把parent给到cur的左Node* ppnode parent-_parent;//记录parent的原父亲节点用于对cur的父亲进行更新parent-_parent cur;//对cur的父亲进行更新if (parent _root){_root cur;cur-_parent nullptr;}else//说明左旋的部分只是某棵树的局部{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}cur-_bf parent-_bf 0;
}右左双旋 先对90进行右单旋再对30进行左单旋 两次旋转。第一次旋转使其变成单纯的右边高第二次旋转对应的左单旋 双旋代码难的不是旋转而是平衡因子的更新 从图中可以看到最终60成了根60的左孩子给了parent的右边60的右孩子给了cur的左边
因此平衡因子的更新分为两种情况
h 0那么60则作为新插入的节点此时60的bf 0那么parent和cur的bf也一定为0h0 假如新结点插入在60的左边即60的bf -1。那么最终parent的bf 0cur的bf 1假如新结点插入在60的右边即60的bf 1。那么最终parent的bf -1cur的bf 0而60作为根节点最终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;}else{assert(false);}
}左右双旋 与右左双旋是镜像的不再赘述
代码
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;}else{assert(false);}
}AVL树插入的完整代码
bool Insert(const pairK, V kv)
{//先帮助插入节点找到正确位置if (_root nullptr)//树为空{_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;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 (cur-_kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//控制平衡因子while (parent)//{if (cur parent-_left)//节点插入在父亲左边{parent-_bf--;}else if (cur parent-_right)//节点插入在父亲右边{parent-_bf;}//进一步判断祖先节点的平衡因子if (parent-_bf 0)//父亲的平衡因子为0循环结束{break;}else if (parent-_bf 1 || parent-_bf -1)//父亲的平衡因子为1或-1则需要继续向上调整{cur parent;parent cur-_parent;}else if (parent-_bf 2 || parent-_bf -2)//父亲的平衡因子为2或-2则需要旋转且选择完后树一定平衡故结束循环{//左单旋if (parent-_bf 2 cur-_bf 1){RotateL(parent);}//右单旋if (parent-_bf -2 cur-_bf -1){RotateR(parent);}//右左双旋if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}//左右双旋if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else//其他情况此时说明在插入之前树就已经不是平衡树了{assert(false);}}}//左单旋
void RotateL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;} cur-_left parent;Node* ppnode parent-_parent;//记录parent的原父亲节点parent-_parent cur;//对cur的父亲进行更新if (parent _root){_root cur;cur-_parent nullptr;}else//说明左旋的部分只是某棵树的局部{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}cur-_bf parent-_bf 0;
}//右单旋
void RotateR(Node* parent)
{Node* cur parent-_left;Node* curright cur-_right;//让右节点接到parent的左边再将parent接到cur的右边parent-_left curright;if (curright){curright-_parent parent;}cur-_right parent;Node* ppnode parent-_parent;//记录parent的原父亲节点parent-_parent cur;//对cur的父亲进行更新if (parent _root){_root cur;cur-_parent nullptr;}else//说明右旋的部分只是某棵树的局部{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}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;}else{assert(false);}
}//左右双旋
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 1;cur-_bf -1;curright-_bf 0;}else if (bf -1){parent-_bf 1;cur-_bf 0;curright-_bf 0;}else{assert(false);}
}AVL树的验证
验证AVL树分为两步 验证其为二叉搜索树如果中序遍历历可得到一个有序的序列就说明为二叉搜索树这里就不详细介绍了详情可以看二叉搜索树那里 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确 int TreeHeight(Node* root)
{if (root nullptr)return 0;int leftHeight TreeHeight(root-_left);int rightHeight TreeHeight(root-_right);return rightHeight leftHeight ? rightHeight 1: leftHeight 1;
}bool IsBalance()//两个IsBalance构成重载
{return IsBalance(_root);
}bool IsBalance(Node* root)
{if (root nullptr)return true;int leftHeight TreeHeight(root-_left);int rightHeight TreeHeight(root-_right);if (rightHeight - leftHeight ! root-_bf){cout 平衡因子异常: root-_kv.first - root-_bf endl;return false;}return abs(rightHeight - leftHeight) 2 IsBalance(root-_left) IsBalance(root-_right);
}这里给出一个调试技巧 假如我运行出现了下面的情况 我们现在知道在插入11的时候出了问题那么就可以针对e11时进行调试 但如果现在有100个值我在第99个值才出现问题那是不是需要按F10按99次呢 两种方法 一个是利用条件断点 还一个是我们自己写代码让它停到想停的地方 这里的int x0;是随便写的目的是能让断点在这里停下来。因为断点打在空行上是停不住的 当然我停在断点处不是为了调int x0;而是为了调下面
AVL树的删除 了解即可 总结
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。
但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。
因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
