四川网站建设哪家专业,用vue框架做的pc端网站,营销策略有哪些方法,四川建设质量安全网站#x1f4d8;北尘_#xff1a;个人主页 #x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上#xff0c;不忘来时的初心 文章目录 一、AVL树的概念二、AVL树的旋转1、左单旋2、右单旋3、左右双旋4、右左双旋 三、AVL树的基本实… 北尘_个人主页 个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上不忘来时的初心 文章目录 一、AVL树的概念二、AVL树的旋转1、左单旋2、右单旋3、左右双旋4、右左双旋 三、AVL树的基本实现四、AVL树的性能 一、AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。 因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法 当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。 一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 二、AVL树的旋转
由于插入节点后平衡因子会发生变化从而使绝对值大于1所以就需要去旋转而旋转就有4中情况。
1、左单旋 代码实现 void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}parent-_bf subR-_bf 0;}2、右单旋 代码实现 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;Node* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}subL-_bf parent-_bf 0;}3、左右双旋
右左双旋可以直接调用右单旋然后再左单旋但需要注意的是调用后并没有完成因为平衡因子还不是正确的值。 平衡因子也分为三种情况以下图为例 当60的平衡因子为0时平衡因子皆为0 当60的平衡因子为1时60的平衡因子为030的平衡因子为-190的平衡因子为0 当60的平衡因子为-1时60的平衡因子为030的平衡因子为090的平衡因子为1 代码实现 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else{assert(false);}}4、右左双旋
右左双旋可以直接调用右单旋然后再左单旋但需要注意的是调用后并没有完成因为平衡因子还不是正确的值。 平衡因子也分为三种情况以下图为例 当60的平衡因子为0时平衡因子皆为0 当60的平衡因子为1时60的平衡因子为030的平衡因子为-190的平衡因子为0 当60的平衡因子为-1时60的平衡因子为030的平衡因子为090的平衡因子为1 代码实现 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);if (bf 0){// subRL自己就是新增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);}}三、AVL树的基本实现 AVL树的节点实现 templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; // balance factorAVLTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};AVL树的插入实现 class 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-_right cur;cur-_parent parent;}else{parent-_left 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){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){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}// 1、旋转让这颗子树平衡了// 2、旋转降低了这颗子树的高度恢复到跟插入前一样的高度所以对上一层没有影响不用继续更新break;}else{assert(false);}}return true;}void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_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 0){// subRL自己就是新增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);}}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;if (subRL)subRL-_parent parent;if (_root parent){_root subR;subR-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}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* parentParent parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}subL-_bf parent-_bf 0;}private:Node* _rootnullptr;
}; 四、AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
