东莞网站优化效果如何,做类似电影天堂的网站违法吗,wordpress 整站,建设工程合同的分类文章目录 一.AVL树的定义二.AVL树的插入三.插入后更新平衡因子四.AVL树的旋转1.左单旋2.右单旋3.先左单旋再右单旋4.先右单旋再左单旋 五.AVL树的性能分析六.检查是否满足AVL树七.源码 一.AVL树的定义
二叉搜索树虽可以缩短查找的效率#xff0c;但如果数据有序或接近有序二叉… 文章目录 一.AVL树的定义二.AVL树的插入三.插入后更新平衡因子四.AVL树的旋转1.左单旋2.右单旋3.先左单旋再右单旋4.先右单旋再左单旋 五.AVL树的性能分析六.检查是否满足AVL树七.源码 一.AVL树的定义
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
具有以上性质的树被称为AVL树。 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)搜索时间复杂度O( l o g 2 n log_2 n log2n)。 AVL树节点的定义
templateclass K,class V
struct AVLTreeNode
{ALVTreeNodeK,V* _left;AVLTreeNodeK,V* _right;AVLTreeNodeK,V* _parent;//父亲节点pairK, V _kv;//构造函数AVLTreeNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}int _bf;//平衡因子
};AVL树的定义
templateclass K,class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:private:Node* _rootnullptr;
};二.AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步
按照二叉搜索树的方式插入新节点调整节点的平衡因子
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.second){//当前值小于要插入的值往右边走parent cur;cur cur-_right;}else if (cur-_kv.first kv.second){//当前值大于要插入的值往左边走parent cur;cur cur-_left;}else{//有相同的值了退出插入return false;}}//当cur走到了nullptr就是找到了要插入的点了cur new Node(kv);//判断插入在左边还是右边if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//确定父子关系//…………//更新插入后的平衡因子//…………
}三.插入后更新平衡因子
新节点插入后AVL树的平衡性可能会遭到破坏此时就需要更新平衡因子并检测是否破坏了AVL树的平衡性
更新平衡因子的规则
新增在右边则会让父平衡因子新增在左边父平衡因子--更新后如果 parent-bf 0说明 parent 插入前的平衡因子是 1 or -1插入填上了矮的一边parent 的子树高度不变不需要继续往上更新。更新后如果parent-bf为 1 或 -1 说明parent插入前的平衡因子是0说明左右子树高度相等插入后有一边高parnet 高度变了需要继续往上更新。更新后如果 parent-bf 2 或-2说明parent插入前的平衡因子是 1 or -1已经到达平衡临界值parent 子树进行旋转处理将树保持平衡。更新后如果 parent-bf 2 或 -2 则说明插入前树已经失去的平衡要进行代码的检查。
while (parent)
{//更新平衡因子if (cur parent-_left){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){//没有新增高度break;}else if(abs(parent-_bf)1){//平衡因子为1往上面继续找parent parent-_parent;cur cur-_parent;}else if (abs(parent-_bf) 2){//需要旋转了}
}四.AVL树的旋转
1.左单旋 新节点插入较高右子树的右侧—右右左单旋 将subR作为一个根节点将subRL作为parent的右节点(如果subRL存在的话)parent作为subR的左节点。
左旋的条件是
parent-_bf2cur-_bf1旋转之后parent的平衡因子为0subL的平衡因子也是0。
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;if (subRL){subRL-_parent subR;}subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;;}subR-_parent pparent;}subR-_bf parent-_bf 0;
}2.右单旋 新节点插入较高左子树的左侧—左左右单旋 将subL作为一个根节点将subLR作为parent的左节点(如果subLR存在的话)parent作为subL的右子节点。
右旋的条件是
parent-_bf-2cur-_bf-1旋转之后parent的平衡因子为0subL的平衡因子也是0。
3.先左单旋再右单旋 新节点插入较高左子树的右侧—左右先左单旋再右单旋 如果将节点插入到c当中平衡因子就会发生改变所以这里的平衡因子需要分情况讨论。 这里通过subLR的平衡因子来确定是在左边插入还是在右边插入。 两种情况下subLR都是0。 void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL- _right;int bf subLR-_bf;//提前存好旋转后会subLR会发生改变RotateL(parent-_left);RotateR(parent);subLR-_bf 0;if (bf 1){//在右边插入parent-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subL-_bf 0;}else if (bf 0){//已经平衡了parent-_bf 0;subL-_bf 0;}else{//插入存在问题assert(false);}
}4.先右单旋再左单旋 新节点插入较高右子树的左侧—右左先右单旋再左单旋 C增加节点之后高度和d一样都是h将其全部旋转到右边去然后再通过左旋把30压下去将60作为根节点。 与左右单旋一样插入的b还是c需要分别更新平衡因子
void RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);subRL-_bf 0;if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;parent-_bf 0;}else if (bf 0){parent-_bf 0;subR-_bf 0;}else{assert(false);}
}五.AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这 样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。
但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
六.检查是否满足AVL树
通过计算左右子树的高度差来确定是否满足AVL树因为平衡因子是自己设置的如果还通过平衡因子来确定的话会不太准。
bool _IsBalance(Node* root)
{if (root nullptr){return true;}int leftHT Height(root-_left);int rightHT Height(root-_right);int diff rightHT - leftHT;if (diff ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}return abs(diff) 2 _IsBalance(root-_left)//递归左子树 _IsBalance(root-_right);//递归右子树
}int Height(Node* root)
{if (root nullptr)return 0;int left Height(root-_left);int right Height(root-_right);return max(left, right) 1;
}七.源码
namespace dianxia
{//树的节点templateclass K, class Vstruct AVLTreeNode{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // 平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}};templateclass K, class Vclass AVLTree{typedef AVLTreeNodeK, V Node;public:bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;// 更新平衡因子while (parent){if (cur parent-_right){parent-_bf;}else{parent-_bf--;}if (parent-_bf 1 || parent-_bf -1){// 继续更新祖先parent parent-_parent;cur cur-_parent;}else if (parent-_bf 0){break;}else if (parent-_bf 2 || parent-_bf -2){// 需要旋转处理 -- 1、让这颗子树平衡 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;}else{assert(false);}}return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}private:int _Height(Node* root){if (root NULL)return 0;int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}bool _IsBalance(Node* root){if (root NULL){return true;}int leftH _Height(root-_left);int rightH _Height(root-_right);if (rightH - leftH ! root-_bf){cout root-_kv.first 节点平衡因子异常 endl;return false;}return abs(leftH - rightH) 2 _IsBalance(root-_left) _IsBalance(root-_right);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppnode parent-_parent;subR-_left parent;parent-_parent subR;if (ppnode nullptr){_root subR;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subR;}else{ppnode-_right subR;}subR-_parent ppnode;}parent-_bf subR-_bf 0;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* ppnode parent-_parent;subL-_right parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subL;}else{ppnode-_right subL;}subL-_parent ppnode;}subL-_bf parent-_bf 0;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 0){parent-_bf 0;subLR-_bf 0;subL-_bf 0;}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 1){subR-_bf 0;parent-_bf -1;subRL-_bf 0;}else if (bf -1){subR-_bf 1;parent-_bf 0;subRL-_bf 0;}else if (bf 0){subR-_bf 0;parent-_bf 0;subRL-_bf 0;}else{assert(false);}}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}private:Node* _root nullptr;};
}本文到此结束码文不易还请多多支持哦
