电商网站设计工作内容,gta 买房网站建设中,微信营销案例ppt,国家公示系统官网一、AVL树的概念
二叉搜索树的缺点 二叉搜索树虽可以缩短查找效率 但如果数据有序或接近有序 二叉搜索树将退化为单支树 查找元素相当于在顺序表中搜索元素#xff0c;效率低下
AVL树便是解决此问题 向二叉搜索树中插入新结点 并保证每个结点的左右子树 高度之差的绝对值不超…
一、AVL树的概念
二叉搜索树的缺点 二叉搜索树虽可以缩短查找效率 但如果数据有序或接近有序 二叉搜索树将退化为单支树 查找元素相当于在顺序表中搜索元素效率低下
AVL树便是解决此问题 向二叉搜索树中插入新结点 并保证每个结点的左右子树 高度之差的绝对值不超过1 (需要对树中的结点进行调整) 即可降低树的高度从而减少 平均搜索长度 AVL树或空树 或是具有以下性质的二叉搜索树
它的左右子树都是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树实现的基本框架
2.1 AVL树节点的定义
template class K, class V
struct AVLTreeNode
{// 三叉链AVLTreeNodeK, V* _left; AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;//存储的键值对 pairK, V _KV;// balance factor 平衡因子int _bf; // 构造函数AVLTreeNode(const pairK, V kv), left(nullptr), right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};2.2 AVL树的基本结构
template class K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
private:Node* _root nullptr; // 根节点
};2.3 AVL树的插入
AVL树插入步骤
按二叉搜索树的方式插入新节点更新平衡因子若平衡因子失衡需要旋转处理
平衡因子失衡后的旋转处理 更新完, 平衡因子没问题(|bf| 1) 平衡因子结构未受影响, 不需要处理 更新完平衡因子有问题(|bf| 1) 平衡结构受影响需要处理(旋转)
原因 插入新增节点 会影响祖先的平衡因子(全部或部分) 当前节点平衡因子等于 右树节点个数减左树节点个数 cur parent-right 则parent-bfcur parent-left 则parent-bf– parent所在子树高度发生变化 则需要继续往上更新爷爷节点 否则就不更新
parent-bf 1 || parent-bf -1
// 则说明parent所在子树变了, 继续更新插入节点更新平衡因子后分为三种情况
插入前parent-bf 0 说明插入前左右两边高度相等 插入后有一边高1 说明parent一边高一边低高度变了 2.
parent-bf 2 || parent-bf -2则说明parent所在子树不平衡 需要处理这颗子树(旋转处理)
parent-bf 0 parent所在子树高度不变 不用继续往上更新这一次插入结束 说明插入前parent-bf 1 or -1 插入前一边高一边低 插入节点填上矮的那边高度不变 三、AVL树的旋转
旋转的原则 保持它是搜索树
旋转的目的
让这棵子树平衡降低这棵子树的高度
左旋过程
30的左子树25变成20的右子树20变成30的左子树 30变成整棵树的根
实际旋转中的节点值可能不是这些值 但也是按这些点位去旋转的 根据节点插入位置的不同 AVL树的旋转分为四种 1. 新节点插入较高左子树的左侧—左左 右单旋 图中h为子树的高度
2. 新节点插入较高右子树的右侧—右右 左单旋 3. 新节点插入较高左子树的右侧—左右 先左单旋再右单旋 将双旋变成单旋后再旋转即 先对30进行左单旋 然后再对90进行右单旋 图中只展示了b插入引发双旋的场景 本质有三种引发双旋的场景
在b插入b的高度变化1在c插入c的高度变化160本身就是新增节点 旋转完成后再考虑平衡因子的更新 不同场景的插入60的平衡因子也不同 分别为-110 且每种场景的插入旋转完后90和30的 平衡因子都不一样 代码的实现通过记录60这个点位的平衡因子 旋转完后 根据不同场景的插入更新90和30的平衡因子 4. 新节点插入较高右子树的左侧—右左 先右单旋再左单旋 参考先左单旋再右单旋
四、插入代码的实现
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;}// new的节点的parent还指向空cur-_parent parent;// 1. 更新平衡因子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) // parent-right是cur{RotateL(parent);}else if (parent-_bf -2 cur-_bf -1) // parent-{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; // 处理完break否则会一直循环}else{// 如果插入之前就有问题assert(false);}}return true;
}五、AVL树旋转代码实现
void RotateL(Node* parent) // 左单旋
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL) // subRL可能为空subRL-_parent parent;// 旋转的不一定是整棵树Node* pparent parent-_parent;subR-_left parent;parent-_parent subR;if (pparent nullptr){_root subR;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}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* pparent parent-_parent;subL-_right parent;parent-_parent subL;if (pparent nullptr){_root subL;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}parent-_bf subL-_bf 0;
}void RotateLR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);subLR-_bf 0; // subLR的左一定等于0if (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);}
}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){parent-_bf -1;subR-_bf 0;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else if (bf 0){parent-_bf 0;subR-_bf 0;}else{assert(false);}
}六、全部代码实现
AVL树模拟实现全部代码gitee链接
