汉中建网站,美橙互联 wordpress,北京网站建设加q.479185700,十款免费软件app下载文章目录 AVL树AVL树的概念AVL树节点的定义AVL树的插入AVL树的旋转右单旋左单旋左右双旋右左双旋 代码实现 总结 AVL树
AVL树的概念
二叉搜索树在顺序有序或接近有序的情况下#xff0c;而插入搜索树将退化为单叉树#xff0c;此时查找的时间复杂度为O(n)#xff0c;效率低… 文章目录 AVL树AVL树的概念AVL树节点的定义AVL树的插入AVL树的旋转右单旋左单旋左右双旋右左双旋 代码实现 总结 AVL树
AVL树的概念
二叉搜索树在顺序有序或接近有序的情况下而插入搜索树将退化为单叉树此时查找的时间复杂度为O(n)效率低下。 两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新节点后保证每个节点的左右子树高度差的绝对值不超过1即可降低树的高度减少平均搜索长度。因此AVL树也被叫做高度平衡二叉搜索树插入查找删除在平均和最坏情况下的时间复杂度都是O( l o g 2 n log_2 n log2n)。
AVL树节点的定义 templateclass K, class Vstruct AVLTreeNode{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; //balance factor 平衡因子AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}};注意实现AVL树平衡因子不是必须的只不过有了平衡因子帮助我们更便捷地控制整棵树。
AVL树的插入
根据二叉搜索树的规则插入新节点
bool Insert(const pairK, V kv){root为空特殊处理if (_root nullptr){_root new Node(kv);return true;}Node* curr _root;Node* parent nullptr;while (curr){if (curr-_kv.first kv.first){parent curr;curr curr-_right;}else if (curr-_kv.first kv.first){parent curr;curr curr-_left;}else{return false;}}将新节点和其父亲节点链接起来Node* newnode new Node(kv);if (parent-_kv.first kv.first)parent-_right newnode;elseparent-_left newnode;newnode-_parent parent;......}不断向上更新平衡因子 当前平衡因子为0说明插入之前平衡因子为1 / -1插入之后不改变树的高度不会影响其他祖先节点此时更新结束。当前平衡因子为1 / -1说明插入之前平衡因子为0插入之后当前节点地高度发生变化会影响其他祖先节点但是不违反规则需要向上对祖先节点进行更新直至当前节点为root。当前平衡因子为 2 / -2此时当前节点所在地子树违反了平衡规则需要进行处理–旋转。
while (parent)
{if (parent-_left newnode){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0)break;else if (parent-_bf -1 || parent-_bf 1){newnode parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2){旋转处理}else{assert(false);}
}AVL树的旋转
右单旋 void RotatoR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent)ppnode-_left subL;elseppnode-_right subL;subL-_parent ppnode;}parent-_bf 0;subL-_bf 0;
}左单旋 void RotatoL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent)ppnode-_left subR;elseppnode-_right subR;subR-_parent ppnode;}parent-_bf 0;subR-_bf 0;
}左右双旋 旋转之前45的平衡因子可能是-1/0/1旋转完成之后根据情况对其他节点的平衡因子进行调整
void RotatoLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotatoL(subL);RotatoR(parent);subLR-_bf 0;if (bf 0){subL-_bf 0;parent-_bf 0;}else if (bf 1){subL-_bf -1;parent-_bf 0;}else if (bf -1){subL-_bf 0;parent-_bf 1;}
}右左双旋 void RotatoRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;subRL-_bf 0;RotatoR(subR);RotatoL(parent);if (bf 0){subR-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;parent-_bf 0;}
}代码实现
namespace xxx
{templateclass K, class Vstruct AVLTreeNode{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf; //balance factor 平衡因子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* curr _root;Node* parent nullptr;while (curr){if (curr-_kv.first kv.first){parent curr;curr curr-_right;}else if (curr-_kv.first kv.first){parent curr;curr curr-_left;}else{return false;}}Node* newnode new Node(kv);if (parent-_kv.first kv.first)parent-_right newnode;elseparent-_left newnode;newnode-_parent parent;while (parent){if (parent-_left newnode){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0)break;else if (parent-_bf -1 || parent-_bf 1){newnode parent;parent parent-_parent;}else if (parent-_bf -2 || parent-_bf 2){if (parent-_bf 2 newnode-_bf 1){RotatoL(parent);}else if (parent-_bf -2 newnode-_bf -1){RotatoR(parent);}else if (parent-_bf -2 newnode-_bf 1){RotatoLR(parent);}else if (parent-_bf 2 newnode-_bf -1){RotatoRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;}void RotatoL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppnode parent-_parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (ppnode-_left parent)ppnode-_left subR;elseppnode-_right subR;subR-_parent ppnode;}parent-_bf 0;subR-_bf 0;}void RotatoR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppnode parent-_parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (ppnode-_left parent)ppnode-_left subL;elseppnode-_right subL;subL-_parent ppnode;}parent-_bf 0;subL-_bf 0;}void RotatoLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotatoL(subL);RotatoR(parent);subLR-_bf 0;if (bf 0){subL-_bf 0;parent-_bf 0;}else if (bf 1){subL-_bf -1;parent-_bf 0;}else if (bf -1){subL-_bf 0;parent-_bf 1;}}void RotatoRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;subRL-_bf 0;RotatoR(subR);RotatoL(parent);if (bf 0){subR-_bf 0;parent-_bf 0;}else if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){subR-_bf 1;parent-_bf 0;}}void InOrder(){_InOrder(_root);cout endl;}bool IsAVLTree(){return _IsAVLTree(_root);}private:bool _IsAVLTree(Node* root){if (root nullptr)return true;int leftH Height(root-_left);int rightH Height(root-_right);return abs(leftH - rightH) 1 _IsAVLTree(root-_left) _IsAVLTree(root-_right);}int Height(Node* node){if (node nullptr)return 0;int leftH Height(node-_left);int rightH Height(node-_right);return 1 max(leftH, rightH);}void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.second ;_InOrder(root-_right);}Node* _root nullptr;};
}总结
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。
