深圳龙岗建设网站,怎么运行网站,wordpress图片shuiyin,网站产品介绍模板AVL树实现 1. AVL的概念AVL树的实现2.1 AVL树的结点结构2.2 AVL树的插入2.2.1 AVL树的插入的一个大概操作#xff1a;2.2.2 AVL树的平衡因子更新2.2.3 平衡因子的停止条件2.2.4 再不考虑旋转的角度上实现AVL树的插入 2.3 旋转2.3.1 旋转的原则2.3.2 右单旋2.2.3 右单旋代码实现… AVL树实现 1. AVL的概念AVL树的实现2.1 AVL树的结点结构2.2 AVL树的插入2.2.1 AVL树的插入的一个大概操作2.2.2 AVL树的平衡因子更新2.2.3 平衡因子的停止条件2.2.4 再不考虑旋转的角度上实现AVL树的插入 2.3 旋转2.3.1 旋转的原则2.3.2 右单旋2.2.3 右单旋代码实现2.3.4 左单旋2.3.5 左单旋代码实现2.3.6 左右双旋2.3.7 左右双旋代码实现 2.4 AVL树平衡检测 结束!!! 1. AVL的概念
• AVL树是最先发明的⾃平衡⼆叉查找树AVL是⼀颗空树或者具备下列性质的⼆叉搜索树它的 左右⼦树都是AV树且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树 通过控制⾼度差去控制平衡。
• AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家他们在1962 年的论⽂《An algorithm for the organization of information》中发表了它。
• AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念每个结点都有⼀个平衡因⼦任何 结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度也就是说任何结点的平衡因⼦等于0/1/-1 AVL树并不是必须要平衡因⼦但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡 就像⼀个⻛向标⼀样。
• 思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树要求⾼度差不超过1⽽不是⾼度差是0呢0不是更 好的平衡吗画画图分析我们发现不是不想这样设计⽽是有些情况是做不到⾼度差是0的。⽐ 如⼀棵树是2个结点4个结点等情况下⾼度差最好就是1⽆法作为⾼度差是0
• AVL树整体结点数量和分布和完全⼆叉树类似⾼度可以控制在logN 那么增删查改的效率也可 以控制在 O(logN)相⽐⼆叉搜索树有了本质的提升
列如 当树的平衡因子达到2时就要旋转 插入到14的左节点使得10的平衡因子变成2。 因为AVL树的左右高度相差不超过2那么我们就要旋转来改变树的结构
AVL树的实现
2.1 AVL树的结点结构 结点的结构templateclass K,class V
struct AVLTreeNode
{
public:
pairK,L _kv;
AVLTreeNodeK,V* _left;
AVLTreeNodeK,V* _right;
AVLTreeNodeK,V* _parent;
int _bf0;平衡因子
AVLTreeNode(const pairK,V kv):_kv(kv),_left(nullptr),_rigth(nullptr),_parent(nullptr),_bf(0)
{}
};结点需要以下几个元素组成:
1数据Key,Valuepair类型的数据2节点指针(为方便指向结点进行更新)3平衡因子(时刻保持着树的高度之差2)2.2 AVL树的插入
2.2.1 AVL树的插入的一个大概操作 1、插入时如果树结点为空那么就直接构造节点直接插入 2、插入时要按照搜索二叉树规则来进行插入 3、插入后平衡因子只会影响租先结点的高度也就是说祖先结点的平衡因子会改变 那么平衡因子更新规律从新增结点开始往上传这就体现了父亲节点指针的用处了直到特殊条件停止或更新到根结点了 特殊条件下面会讲~ 4、更新平衡因⼦过程中没有出现问题则插⼊结束 5、如果更新时出现平衡因子为二的情况时就要旋转了 2.2.2 AVL树的平衡因子更新
更新规则 1 平衡因子右高度-左高度 ------------------------ (同时也可以 平衡因子 左高度-右高度,那么以下更新平衡因子的规则就要改变) 2 只有当前结点的高度改变时才会导致结点的平衡因子改变 当插入13时高度改变使得10的平衡因子的改变 3 插⼊结点会增加⾼度所以新增结点在parent的右⼦树parent的平衡因⼦新增结点在parent的左⼦树parent平衡因子
4 parent所在⼦树的⾼度是否变化决定了是否会继续往上更新
2.2.3 平衡因子的停止条件
1 更新后parent的平衡因⼦等于0更新中parent的平衡因⼦变化为-1-0 或者 1-0说明更新前 parent⼦树⼀边⾼⼀边低新增的结点插⼊在低的那边插⼊后parent所在的⼦树⾼度不变不会 影响parent的⽗亲结点的平衡因⼦更新结束。
如图 变化前
变化后 2 更新后parent的平衡因⼦等于1 或 -1更新前更新中parent的平衡因⼦变化为0-1 或者 0--1说 明更新前parent⼦树两边⼀样⾼新增的插⼊结点后parent所在的⼦树⼀边⾼⼀边低parent所 在的⼦树符合平衡要求但是⾼度增加了1会影响arent的⽗亲结点的平衡因⼦所以要继续向上更新。 3 更新后parent的平衡因⼦等于2 或 -2更新前更新中parent的平衡因⼦变化为1-2 或者 -1--2说 明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼ 了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理旋转的⽬标有两个1、把 parent⼦树旋转平衡。2、降低parent⼦树的⾼度恢复到插⼊结点以前的⾼度。所以旋转后也不 需要继续往上更新插⼊结束。
(1) 往高的那边你插入数据导致平衡因子变为2
2.2.4 再不考虑旋转的角度上实现AVL树的插入
typedef AVLTreeNodeK,V Node;
bool insert(const pairK,V kv)
{
1:根节点为空则直接构造赋值
if(_rootnullptr)
{_rootnew Node(kv);return true;插入完成给值
}
找出kv的位置
Node* parentnullptr
Node* cur_root;
while(cur)
{
if(cur-_kv.firstkv.first)
{插入的值大于cur指向结点的值,那么久往右找parentcur;curcur-_right;
}
else if(cur-_kv.firstkv.first)
{插入的值小于当前节点的值,那么就往左走parentcur;curcur-_left;
}
else
{找到与kv.first 的结点的值,那么久返回插入失败return false
}
}
出来这个循环后,就要构建结点来连接了
curnew Node(kv);
if(parent-_kv.firstkv.first)这里用父亲节点来连接
{parent-_rightcur;
}
else
{
parent-_leftcur;
}
cur-_parentparent;别忘了是三叉链这里博主就会经常忘记插入节点后,开始调节平衡因子:
while(parent)因为从parent插入结点那么避免不了要改变parent的平衡因子
{
if(curparent-_left)
parent-_bf--;
else
parent-_bf;
从这里开始就会用到平衡因子的停止条件
if(parent-_bf0)
{
更新结束
break;
}
else if(parent-_bf1||parent-_bf-1)
{
往上更新curparent;parentparent-_parent;
}
else if(parent-_bf2||parent-_bf-2)
{
这里就需要旋转,因为现在不考虑旋转,所以这里空着
break;
}
else
{
其他因素
assert(false);用assert报错
}
}
}
return true; 走到这里返回成功
}2.3 旋转
2.3.1 旋转的原则
1. 保持搜索树的规则 2. 让旋转的树从不满⾜变平衡其次降低旋转树的⾼度 旋转总共分为四种左单旋/右单旋/左右双旋/右左双旋。 说明下⾯的图中有些结点我们给的是具体值如10和5等结点这⾥是为了⽅便讲解实际中是什 么值都可以只要⼤⼩关系符合搜索树的规则即可。
2.3.2 右单旋
• 本图1展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种具体图2/图3/图4/ 图5进⾏了详细描述。
• 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从-1变成-210为根的树左右⾼度差超过1违反平衡规则。10为根的树左边太⾼了需要 往右边旋转控制两棵树的平衡。
• 旋转核⼼步骤因为5 b⼦树的值 10将b变成10的左⼦树10变成5的右⼦树5变成这棵树新 的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转原 则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。 也就是说旋转是哪边高就往那边压数据 1、这里的左节点太高了那么就把结点5往右压10 2、5作为根结点,5的右边结点给了10的左边结点 3、10变成了5的右边结点
按照以上规律 既能保持旋转后还是AVL树还能让平衡因子更新成2
根据不同情况结果也不一样: a、b、c h0
h1
h2 这里a的结构只能是x,因为为y或z时那么旋转的结点就不是5了而是y或z结点* 那么a就只有4处可以插入值导致5的平衡因子为2,而b或c是以上x,y,z三种情况都可以 那么搭配就有3**3*436种搭配结果
2.2.3 右单旋代码实现
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;
// parent有可能是整棵树的根也可能是局部的⼦树
// 如果是整棵树的根要修改_root
// 如果是局部的指针要跟上⼀层链接
if (parentParent nullptr)
{
_root subL;
subL-_parent nullptr;
}
else
{
if (parent parentParent-_left)
{
parentParent-_left subL;
}
else
{
parentParent-_right subL;
}
subL-_parent parentParent;
}
parent-_bf subL-_bf 0;
}2.3.4 左单旋
• 本图6展⽰的是10为根的树有a/b/c抽象为三棵⾼度为h的⼦树(h0)a/b/c均符合AVL树的要 求。10可能是整棵树的根也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树 是⼀种概括抽象表⽰他代表了所有右单旋的场景实际右单旋形态有很多种具体跟上⾯左旋类 似。
• 在a⼦树中插⼊⼀个新结点导致a⼦树的⾼度从h变成h1不断向上更新平衡因⼦导致10的平 衡因⼦从1变成210为根的树左右⾼度差超过1违反平衡规则。10为根的树右边太⾼了需要往 左边旋转控制两棵树的平衡。
• 旋转核⼼步骤因为10 b⼦树的值 15将b变成10的右⼦树10变成15的左⼦树15变成这棵 树新的根符合搜索树的规则控制了平衡同时这棵的⾼度恢复到了插⼊之前的h2符合旋转 原则。如果插⼊之前10整棵树的⼀个局部⼦树旋转后不会再影响上⼀层插⼊结束了。 这里与右单旋大差不差
2.3.5 左单旋代码实现
void RotateL(Node* parent)
{
Node* subR parent-_right;
Node* subRL subR-_left;
parent-_right subRL;
if(subRL)
subRL-_parent parent;
Node* parentParent parent-_parent;
subR-_left parent;
parent-_parent subR;
if (parentParent nullptr)
{
_root subR;
subR-_parent nullptr;
}
else
{
if (parent parentParent-_left)
{
parentParent-_left subR;
}
else
{
parentParent-_right subR;
}
subR-_parent parentParent;
}
parent-_bf subR-_bf 0;
}2.3.6 左右双旋
通过图7和图8可以看到左边⾼时如果插⼊位置不是在a⼦树⽽是插⼊在b⼦树b⼦树⾼度从h变 成h1引发旋转右单旋⽆法解决问题右单旋后我们的树依旧不平衡。右单旋解决的纯粹的左边 ⾼但是插⼊在b⼦树中10为跟的⼦树不再是单纯的左边⾼对于10是左边⾼但是对于5是右边 ⾼需要⽤两次旋转才能解决以5为旋转点进⾏⼀个左单旋以10为旋转点进⾏⼀个右单旋这棵树 这棵树就平衡了。 • 图7和图8分别为左右双旋中h 0和h1具体场景分析下⾯我们将a/b/c⼦树抽象为⾼度h的AVL ⼦树进⾏分析另外我们需要把b⼦树的细节进⼀步展开为8和左⼦树⾼度为h-1的e和f⼦树因为 我们要对b的⽗亲5为旋转点进⾏左单旋左单旋需要动b树中的左⼦树。b⼦树中新增结点的位置 不同平衡因⼦更新的细节也不同通过观察8的平衡因⼦不同这⾥我们要分三个场景讨论。
• 场景1h 1时新增结点插⼊在e⼦树e⼦树⾼度从h-1并为h并不断更新8-5-10平衡因⼦ 引发旋转其中8的平衡因⼦为-1旋转后8和5平衡因⼦为010平衡因⼦为1。
• 场景2h 1时新增结点插⼊在f⼦树f⼦树⾼度从h-1变为h并不断更新8-5-10平衡因⼦引 发旋转其中8的平衡因⼦为1旋转后8和10平衡因⼦为05平衡因⼦为-1。
• 场景3h 0时a/b/c都是空树b⾃⼰就是⼀个新增结点不断更新5-10平衡因⼦引发旋 转其中8的平衡因⼦为0旋转后8和10和5平衡因⼦均为0。 这里可以看出来8左旋后把左节点连接到5的右结点上来。 再来一个右旋使得8为根了而8的右结点给了10的左节点了
如果是左边结点高且不是插入到a的子树上的先左旋在右旋 ------------右边结点高且不是插入到a的子树上的那么就先右旋在左旋
2.3.7 左右双旋代码实现
void RotateLR(Node* parent)
{
Node* subL parent-_left;
Node* subLR subL-_right;
int bf subLR-_bf;
RotateL(parent-_left);
RotateR(parent);
if (bf 0)
{
subL-_bf 0;
subLR-_bf 0;
parent-_bf 0;
}
else if (bf -1)
{
subL-_bf 0;
subLR-_bf 0;
parent-_bf 1;
}
else if(bf 1)
{
subL-_bf -1;
subLR-_bf 0;
parent-_bf 0;
}
else
{
assert(false);
}
}2.4 AVL树平衡检测
我们实现的AVL树是否合格我们通过检查左右⼦树⾼度差的的程序进⾏反向验证同时检查—下结点 的平衡因⼦更新是否出现了问题。
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;
}
bool _IsBalanceTree(Node* root)
{
// 空树也是AVL树
if (nullptr root)
return true;
// 计算pRoot结点的平衡因⼦即pRoot左右⼦树的⾼度差
int leftHeight _Height(root-_left);
int rightHeight _Height(root-_right);
int diff rightHeight - leftHeight;
// 如果计算出的平衡因⼦与pRoot的平衡因⼦不相等或者
// pRoot平衡因⼦的绝对值超过1则—定不是AVL树
if (abs(diff) 2)
{
cout root-_kv.first ⾼度差异常 endl;
return false;
}
if (root-_bf ! diff)
{
cout root-_kv.first 平衡因⼦异常 endl;
return false;
}
// pRoot的左和右如果都是AVL树则该树—定是AVL树
return _IsBalanceTree(root-_left) _IsBalanceTree(root-_right);
}
// 测试代码
void TestAVLTree1()
{
AVLTreeint, int t;
// 常规的测试⽤例
//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试⽤例
int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
cout t.IsBalanceTree() endl;
}
// 插⼊—堆随机值测试平衡顺便测试—下⾼度和性能等
void TestAVLTree2()
{
const int N 100000;
vectorint v;
v.reserve(N);
srand(time(0));
for (size_t i 0; i N; i)
{
v.push_back(rand()i);
}
size_t begin2 clock();
AVLTreeint, int t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
size_t end2 clock();
cout Insert: end2 - begin2 endl;
cout t.IsBalanceTree() endl;
cout Height: t.Height() endl;
cout Size: t.Size() endl;
size_t begin1 clock();
// 确定在的值
/*for (auto e : v)
{
t.Find(e);
}*/
// 随机值
for (size_t i 0; i N; i)
{
t.Find((rand() i));
}
size_t end1 clock();
cout Find: end1 - begin1 endl;结束!!!
