做简单的网站首页,什么网站可以做音乐伴奏,怎样做网站跳转,网站修改标题1. AVL树的概念 二叉搜索树虽可以缩短查找的效率#xff0c;但如果存数据时接近有序#xff0c;二叉搜索将退化为单支树#xff0c;此时查找元素效率相当于在顺序表中查找#xff0c;效率低下。因此两位俄罗斯数学家 G.M.Adelson-Velskii 和E.M.Landis 在1962年发明了一种解…1. AVL树的概念 二叉搜索树虽可以缩短查找的效率但如果存数据时接近有序二叉搜索将退化为单支树此时查找元素效率相当于在顺序表中查找效率低下。因此两位俄罗斯数学家 G.M.Adelson-Velskii 和E.M.Landis 在1962年发明了一种解决上述问题的方法当二叉搜索树中插入新节点后如果能保证每个节点的左右子树高度差不大于 1 的绝对值即可降低树的高度从而减少平均搜索长度。 一个标准的AVL树任意节点的左右子树高度差的绝对值不大于1我们将记录高度差的数据称为平衡因子。 平衡因子 右子树高度 - 左子树高度 2. AVL树节点的定义 我们根STL库保持一致将key和value合并定义成pair类型再在节点中添加一个平衡因子。 3. AVL树的插入 关于平衡因子我们可以通过其定义得知这样两条条性质 1. 插入节点时只会影响到祖先的平衡因子而不会影响到其他节点的平衡因子。 2. 父节点右侧插入节点其平衡因子 1左侧插入节点其平衡因子 -1 对于插入节点的父节点来说插入后父节点的平衡因子只会出现3种情况第一种情况是平衡因子为0 、第二种情况是平衡因子为1 或 -1 、第三种情况是有祖先平衡因子出现 2 或 -2 插入后父节点平衡因子为0时 说明在左侧或右侧插入一个节点后父节点平衡了但此时并不会影响除父节点外的所有祖先的平衡因子因此平衡因子不需要再向上更新了。 插入后父节点平衡因子为 1 或 -1 时 说明父节点之前的平衡因子一定为0左侧插入能使父节点变-1右侧插入能使父节点变1。为什么父节点平衡因子之前一定为0因为AVL树的平衡因子只可能出现-1、0、1三种情况。 此时平衡因子需要向上更新 插入后有祖先平衡因子出现 2 或 -2 说明这个祖先更新前是1或-1新节点插入在高的那棵树上进一步加剧了高差此时已经违反高差不大于1的规则了此时需要旋转处理 平衡因子调整的逻辑就是这样添加到insert函数中的我会把完整的代码贴到最后的 4. AVL树的旋转
4.1 左单旋 插入节点在较高右子树的右侧时就要进行左单旋。 我这个图中的长方形就代表一颗子树。下面外我们基于这个旋转逻辑编写代码 经过我们前面更新平衡因子之后找到不符合规则的父节点30我们进行旋转代码编写的时候不仅仅要弄节点向下的链接内容还要记得修改节点的parent指针也就是向上链接的内容。 我们要更改的主要就是 30(parent节点) 60(subR节点) tree_b(subRL) 但是我们把代码写成这个还是不对的因为parent的parent没有向下链接。在它向下链接的过程中还有两种情况就是parent本身就是整颗树的根节点旋转后subR成为整棵树的根节点或parent只是树中的一个普通节点那就要考虑parent的parent向下链接的时候链接左子树还是右子树了。 4.2 右单旋 当要在较高左子树的左侧插入新节点就要进行右单旋 右单旋的思路和代码和左单旋是一样的反过来而已先向下更新链接内容再向上更新链接内容然后更新parentParent的向下链接最后调整平衡因子 4.3 右左双旋 当新节点插入在较高右子树的左侧时就要进行右左双旋。 如果我们单纯以30为parent或者说旋转基点进行单左旋结果就是60这棵子树变成30的右子树但是这棵树还是不平衡的c比d高出了2此时再以90为基点右旋结果就是又回去了。 当较高的树在最两侧的时候我们进行单左旋或单右旋是可以让树平衡的但是如果较高的树在中间的时候我们进行单左右旋就会让这个较高树一直在中间来回变动而树一直不会平衡。 所以AVL就用我图中的方案解决了这一问题。 但是如果我们直接把代码写成这样肯定是不行的因为平衡因子的问题还没有得到更新。 如果是我图中画的情况也就是说插入在c树中最后的平衡因子就是 -1、0、0 如果新节点插入在b树中最后平衡因子就应该是 0、0、1 如果 h0也就是说60是新插入的节点最后的平衡因子就应该是 0、0、0 那具体是这三种情况中的哪种我们可以通过观察插入后60节点的平衡因子来判断 4.4 左右双旋 当在较高左子树右侧插入新节点时要进行左右双旋 代码与右左双旋一个思路注意最后要调整平衡因子。 5. AVL树代码 删除的思路和插入是一致的但是删除的更新平衡因子会比较复杂因为删除在旋转了之后平衡因子可能还要继续向上更新。今天先不写删除了如果之后有精力我会把删除更新上的。
#includeassert.h
#includeiostream
using namespace std;templateclass K, class V
struct AVLTNode
{AVLTNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}pairK, V _kv;AVLTNodeK, V* _left;AVLTNodeK, V* _right;AVLTNodeK, V* _parent;int _bf; //balance factor 平衡因子
};templateclass K, class V
class AVLTree
{typedef AVLTNodeK, V Node;public://构造AVLTree() default;//拷贝构造AVLTree(const AVLTreeK, V t){_root Copy(t._root);}//赋值运算符重载void operator(const AVLTreeK, V t){AVLTreeK, V new_t(t);std::swap(new_t._root, _root);}//析构~AVLTree(){Destroy(_root);_root nullptr;}void Destroy(Node* root){if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root;}Node* Copy(const Node* root){if (root nullptr)return nullptr;Node* newnode new Node(root-kv);newnode-_left Copy(root-_left);newnode-_right Copy(root-_right);return newnode;}//插入bool Insert(const pairK, V kv);//搜索Node* Find(const K x);//中序遍历void InOrder(){_InOrder(_root);cout endl;}//树的高度int Height(){return _Height(_root);}//统计节点总个数(插入时可能会有重复数据)int Size(){return _Size(_root);}private://左单旋void RotateL(Node* parent);//右单旋void RotateR(Node* parent);//右左双旋void RotateRL(Node* parent);//左右双旋void RotateLR(Node* parent);//中序遍历(子函数)void _InOrder(Node* root){if (root nullptr)return;_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}//树的高度int _Height(Node* root){if (root nullptr)return 0;int leftHeight _Height(root-_left);int rightHeight _Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}//统计节点总个数(插入时可能会有重复数据)int _Size(Node* root){return root nullptr ? 0 : _Size(root-_left) _Size(root-_right) 1;}private:Node* _root nullptr;
};//插入
templateclass K, class V
bool AVLTreeK, V::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;}elsereturn false;}cur new Node(kv);if (cur-_kv.first parent-_kv.first){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//更新平衡因子while (parent){if (cur parent-_left)parent-_bf--;elseparent-_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);}break;//旋完就退出更新}else{//出现其他奇奇怪怪的情况直接报错assert(false);}}return true;
} //搜索
templateclass K, class V
AVLTNodeK, V* AVLTreeK, V::Find(const K x)
{Node* cur _root;while (cur){if (cur-_kv.first x){cur cur-_right;}else if (cur-_kv.first x){cur cur-_left;}else{return cur;}}return nullptr;
}//左单旋
templateclass K, class V
void AVLTreeK, V::RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL parent-_right-_left;//修改向下链接内容parent-_right subRL;subR-_left parent;//修改向上链接内容subR-_parent parent-_parent;parent-_parent subR;if (subRL)//防止该树点为空{subRL-_parent parent;}//parent的parent向下链接Node* parentParent subR-_parent;if (parentParent nullptr)//整棵树的根{_root subR;}else{if (parent parentParent-_right){parentParent-_right subR;}else{parentParent-_left subR;}}//调整平衡因子parent-_bf 0;subR-_bf 0;
}//右单旋
templateclass K, class V
void AVLTreeK, V::RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;//修改向下链接内容parent-_left subLR;subL-_right parent;//修改向上链接属性subL-_parent parent-_parent;parent-_parent subL;if (subLR){subLR-_parent parent;}//修改parentParentNode* parentParent subL-_parent;if (parentParent nullptr){_root subL;}else{if (parent parentParent-_right){parentParent-_right subL;}else{parentParent-_left subL;}}//更新平衡因子subL-_bf 0;parent-_bf 0;
}//右左双旋
templateclass K, class V
void AVLTreeK, V::RotateRL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);//更新平衡因子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 if (bf -1){parent-_bf 0;subR-_bf 1;subRL-_bf 0;}else{assert(false);}
}//左右双旋
templateclass K, class V
void AVLTreeK, V::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){parent-_bf 0;subL-_bf -1;subLR-_bf 0;}else if (bf -1){parent-_bf 1;subL-_bf 0;subLR-_bf 0;}else{assert(false);}
}
