企业网站排名提升软件智能优化,响应式网站 翻译,合肥网站建设方案,2020ppt模板免费下载01. 初始AVL树
AVL树是最早发明的自平衡二叉搜索树。在AVL树中#xff0c;任何节点的两个子树的高度差#xff08;平衡因子#xff09;最多为1#xff0c;这使得AVL树能够保持较好的平衡性#xff0c;从而保证查找、插入和删除操作的时间复杂度都是O(log n)。包含n个节点…01. 初始AVL树
AVL树是最早发明的自平衡二叉搜索树。在AVL树中任何节点的两个子树的高度差平衡因子最多为1这使得AVL树能够保持较好的平衡性从而保证查找、插入和删除操作的时间复杂度都是O(log n)。包含n个节点的AVL树的高度始终保持在O(log n)02. AVL树的结构
AVL 树在原 二叉搜索树 的基础上添加了 平衡因子 bf 以及用于快速向上调整的 父亲指针 parent所以 AVL 树是一个三叉链结构。2.1 AVL树节点定义
template class K, class V
struct AVLTreeNode // 定义借点类型
{AVLTreeNode(const std::pairK, V kv): _parent(nullptr), _left(nullptr), _right(nullptr), _kv(kv), _bf(0){}AVLTreeNodeK, V *_parent;AVLTreeNodeK, V *_left;AVLTreeNodeK, V *_right;//这里并没有直接存储数据K和V而是像map那样将其封装成一个pairK,V类型。std::pairK, V _kv; // 存储键值对int _bf; // 平衡因子
};那么在AVLTree类方法实现只需创建一个AVLTreeNodeK,V*类型的_root根节点。
规定 当前实现的平衡因子规定差值为 右 - 左因此如果右子树增高_bf左子树增高 _bf–具体操作将在后面体现。2.2 AVL树的方法
templateclass K,class V
class AVLTree{typedef TreeNodeK, V Node;
public://插入bool insert(const pairK, V kv) {}//查找bool find(const K kev) {}//中序遍历void order() {}void RotateR(Node* parent) {} //右单旋void RotateL(Node* parent) {} //左单旋void RRotateRL(Node* parent) {} //右左双选void RotateLR(Node* parent) {} //左右双选void order(Node* root) {} //中序遍历private:Node* _root;
};03. AVL树的插入
3.1插入过程
对于avl树的插入实际是在二叉搜索树基础之上增加了更新平衡因子和在这个过程中进行旋转调整的过程。
空树检查
若树为空 (_root nullptr)直接创建新节点作为根节点返回 true
搜索插入位置
从根节点开始比较 key
key 当前节点向左子树搜索key 当前节点向右子树搜索key 当前节点键已存在返回 false插入新节点
创建新节点并链接到父节点
key 父节点作为左孩子插入key 父节点作为右孩子插入平衡因子更新与调整下面完成
更新平衡因子然后判断是否需要进行旋转调整高度bool Insert(const std::pairK, V kv){if (_root nullptr){ // 树中没有任何节点直接new_root new Node(kv); // 未使用Node(key, value)而是采用简直对的形式return true;}// 不为空树时的操作,找到插入点Node *parent nullptr;Node *cur _root;while (cur){if (kv.first cur-_kv.first){ // 左走parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}elsereturn false;} // 退出的时候找到,即找到叶节点仍需要判断往那边走插入数据(curnull)// 创建新节点插入cur new Node(kv);if (kv.first parent-_kv.first0){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}//控制平衡//1、更新平衡因子----更新新增节点到根节点的祖先路径//2、出现异常平衡因子那么需要旋转平衡处理while (parent) {if (cur parent-_right)parent-_bf;elseparent-_bf--;if (parent-_bf 0) {break;}else if (abs(parent-_bf) 1) {//继续往上更新cur parent;parent parent-_parent;}else if (abs(parent-_bf) 2) {//旋转处理if (parent-_bf -2 cur-_bf -1) {RotateR(parent);//右单旋}else if (parent-_bf 2 cur-_bf 1) {RotateL(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;}3.1 左单旋
左单旋适用场景P (_bf2)\ C (_bf0)C (_bf1) 调整为 / \\ P RR (_bf0)当插入10的时候出现不平衡。
左单旋
确定parentsubRsubRL使subRL成为parent右孩子subR左孩子变为parent注意pparent的更新和paarent为根节点情况void RotateL(Node *parent){ // parent在_bf2处Node *subR parent-_right;Node *subRL subR-_left;// 先将subR的左孩子交给parentparent-_right subRL;if (subRL ! nullptr){subRL-_parent parent;}Node *pparent parent-_parent;//保存parent的父节点确保更新平衡因子subR-_left parent;parent-_parent subR;if (_root parent){//是否是根节点subR-_parent nullptr;_root subR;}else{if (pparent-_right parent){pparent-_right parent;}else{pparent-_left subR;}subR-_parent pparent;}parent-_bf subR-_bf 0;}注意事项
空指针检查
subRL 可能为 nullptr需判断后再操作其父指针
根节点更新
若 parent 是根节点旋转后需更新 _root 指向 subR
平衡因子重置
左单旋后parent 和 subR 的平衡因子必为 03.2 右单旋P (_bf-2)/ C (_bf0)C (_bf-1) / \/ L PL (_bf0) (_bf-0)当插入10的时候出现不平衡。
右单旋
确定parentsubLsubLR使subLR成为parent左孩子subR右孩子变为parent注意pparent的更新和paarent为根节点情况
//右单旋
void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;//先将 subL 的右孩子移交给父亲parent-_left subLR;if (subLR ! nullptr)subLR-_parent parent;Node* pparent parent-_parent;subL-_right parent;parent-_parent subL;//再将父亲移交给 subLsubL 成为新父亲if (parent _root){//如果原父亲为根那么此时需要更新 根subL-_parent nullptr;_root subL;}else{//单纯改变链接关系if (pparent-_right parent)pparent-_right subL;elsepparent-_left subL;subL-_parent pparent;}//更新平衡因子parent-_bf subL-_bf 0;
}
注意事项
空指针检查
subLR 可能为 nullptr需判断后再操作其父指针。
根节点更新
若 parent 是根节点旋转后需更新 _root 指向 subL。
平衡因子重置
右单旋后parent 和 subL 的平衡因子必为 0。3.3 右左单旋//右左双旋
void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int BF subRL-_bf;//先右单旋RotateR(subR);//再左单旋RotateL(parent);//根据不同的情况更新平衡因子if(BF 0){parent-_bf subR-_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{//非法情况std::cerr 此处的平衡因子出现异常! std::endl;assert(false); //直接断言报错}
}
右左单旋
右单旋
确定 parent、subR、subRL将subRL的右子树变为 subR左子树parent右子树为subRL左子树subRL向上提平衡因子调整分三类情况subRL-_bf调整后平衡因子触发条件情况10parent subR subRL 0新节点是 subRL 自身情况2-1parent 0, subR 1, subRL 0新节点在 subRL 左子树情况31parent -1, subR 0, subRL 0新节点在 subRL 右子树
3.4 左右双旋
右左双旋和左右双旋逻辑非常像这里就不演示了直接看代码实现
//左右双旋
void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int BF subLR-_bf;//先左单旋RotateL(subL);//再右单旋RotateR(parent);//根据不同的情况更新平衡因子if (BF 0){parent-_bf subL-_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{//非法情况std::cerr 此处的平衡因子出现异常! std::endl;assert(false); //直接断言报错}
}3.5 AVL查找//查找bool find(const K kv) {Node* ptail _root;while (ptail){if (kv.first ptail-_kv-first){ptail ptail-_right;}else if (kv.first ptail-_kv-first){ptail ptail-_left;}else{return true;}}return false;}
