php网站的部署,广州网站建设 名片制作 网站管理,wordpress 收费版,连连跨境电商网站怎么做我们之前学习了搜索二叉树#xff0c;我们知道普通的搜索二叉树会有特殊情况出现使得二叉树的两枝极其不平衡形成我们通俗说的歪脖子树#xff1a; 这样的树一定会使得我们的增删查的效率变低#xff1b;为了避免这种极端的情况出现#xff0c;在1962年有两位伟大的俄罗斯数…我们之前学习了搜索二叉树我们知道普通的搜索二叉树会有特殊情况出现使得二叉树的两枝极其不平衡形成我们通俗说的歪脖子树 这样的树一定会使得我们的增删查的效率变低为了避免这种极端的情况出现在1962年有两位伟大的俄罗斯数学家Adelson-Velsky和Landis发明的它们通过旋转使得我们的树的任意节点的左右子树高度差不超过2使得搜索二叉树总会是一颗平衡的搜索二叉树
我们怎么知道我们的左右子树的高度差呢
AVL树的节点
我们这个时候就需要在搜索二叉树的基础上对我们的节点进行修改了给我们的节点增加一个平衡因子_balance factor(_bf)
_bf平衡因子
介绍_bf
_bf是如何计算的呢创作者规定 _bf右子树的深度-左子树的深度; 也就是说我们每次我们插入一个新节点到我们当前节点的左边的时候_bf需要减一当新节点插入到我们当前节点的右边的时候_bf加一 templateclass K,class V
struct AVLTreeNode
{typedef AVLTreeNodeK,V node;node* _left;node* _right;node* _parent;pairK,V _data;int _bf;//balance factor平衡因子AVLTreeNode(const pairK, V data):_left(nullptr), _right(nullptr),_parent(nullptr),_data(data),_bf(0){}
};
可以看到我们的AVL树的成员增加了_bf平衡因子和_parent父亲节点的指针
有了描述每个节点的条件要开始组织起来这些节点了我们需要插入一个个节点
插入节点
一开始插入节点是与搜索二叉树相同我们需要先找到节点插入的位置然后再将新增节点连接到我们的原树的叶子节点的末端这个时候插入就完成了
不同的是插入完成后我们需要更新我们父亲节点的_bf平衡因子采用上方所说的插入位置在父亲节点左侧时父亲节点_bf-1插入在父亲节点右侧时当前节点_bf1更新完成父亲节点后向上不断遍历修改父亲的父亲节点而这个遍历我们又需要分情况遍历
插入操作和搜索二叉树中操作相同
if (_root nullptr)
{_root new node(data);return true;
}
node* cur _root;
node* parent _root;
while (cur)
{if (data.first cur-_data.first){parent cur;cur cur-_left;}else if (data.first cur-_data.first){parent cur;cur cur-_right;}else{return false;}
}
cur new node(data);
cur-_parent parent;
if (data.first parent-_data.first)
{parent-_left cur;
}
else
{parent-_right cur;
}
以上是普通的插入操作下面需要进行平衡因子更新
更新_bf
情况1父亲节点的_bf更新为1或-1
如果父节点的_bf为1或者1时就代表我们的父节点的左边或者右边新插入了节点我们我们当前父节点为根的子树高度增加了从而我们又会影响到父亲节点的父亲节点所以我们需要继续所以向上遍历让父亲节点成为新插入的节点更新父亲节点的父亲节点成为parent父亲更新新的父亲的_bf; 情况2父亲节点的_bf更新为0 此时说明我们的父亲节点为根节点的树原本是不平衡的但是由于我们插入的新节点补齐了这颗树使得父亲节点的_bf变为了0这个时候由于父亲节点为根的树高度没有变化所以父亲节点上层的节点自然也不需要更新_bf所以这个时候可以直接退出遍历了 情况3父亲节点的_bf绝对值大于1
这个时候我们需要进行旋转来降低父节点为根的树高度了 循环向上更新_bf
while (parent)
{if (cur parent-_left){parent-_bf--;}else{parent-_bf;}if (parent-_bf 1 || parent-_bf -1)//-1or1时需要继续更新平衡因子{cur parent;parent parent-_parent; }else if (parent-_bf 0)//因子为0是将树补齐了不需要再向上更新了{break;}else if (parent-_bf 2 || parent-_bf -2)//2or-2时需要旋转减小树的高度{if (parent-_bf -2 parent-_left-_bf -1)//左子树的左子树高右旋转{RotateR(parent);}else if (parent-_bf 2 parent-_right-_bf 1)//右子树的右子树高左旋转{RotateL(parent);}else if (parent-_bf -2 parent-_left-_bf 1)//左子树的右子树高先右子树左旋再左子树右旋{RotateLR(parent);}else if (parent-_bf 2 parent-_right-_bf -1)//右子树的左子树高先左子树右旋再右子树左旋{RotateRL(parent);}else{assert(false);}break;}
} 旋转
这个操作就是AVL最精华的部分了我们知道是当树左右两边高度相差超高1的时候就需要旋转了旋转主要是靠画图理解
我们需要注意的是我们旋转的树是一般是子树父节点为根时为整棵树
而旋转又分为四种旋转情况
为了方便描述我们将当前树的根节点同一叫根节点
单旋
情况1根节点_bf为-2根节点左节点_bf为-1时右单旋
当根节点_bf为-2时说明我们这棵树的左子树高度要比右子树高2个节点的高度根左节点的_bf为-1又说明我们左子树的左子树比左子树的右子树高1个节点的高度也就是如下图
我们需要进行单旋因为是左树高所以需要进行右旋转将根节点旋转为左节点的右节点 右单旋
void RotateR(node* parent)
{node* subl parent-_left;node* sublr subl-_right;parent-_left sublr;if (sublr)sublr-_parent parent;node* ppnode parent-_parent;subl-_right parent;parent-_parent subl;if (ppnode nullptr){_root subl;_root-_parent nullptr;}else{subl-_parent ppnode;if (ppnode-_left parent){ppnode-_left subl;}else{ppnode-_right subl;}}parent-_bf subl-_bf 0;return;
} 情况2根节点_bf为2根节点右节点_bf为1时左单旋
这种情况就是情况1的对立边这次是右树的右子树高我们需要进行左单旋 左单旋
void RotateL(node* parent)
{node* subr parent-_right;node* subrl subr-_left;parent-_right subrl;if (subrl)subrl-_parent parent;node* ppnode parent-_parent;subr-_left parent;parent-_parent subr;if (ppnode nullptr){_root subr;_root-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subr;}else{ppnode-_right subr;}subr-_parent ppnode;}parent-_bf subr-_bf 0;
} 单旋之后我们的parent和左节点的_pf都为0
双旋
情况3根节点_pf为-2根节点的左节点_pf为1左右双旋
这种情况就是我们的根节点左树高但左数中的右树高我们需要进行双旋
如何左右双旋如图 值得注意的是双旋我们的_bf是需要更新的我们需要通过sublr的_bf来判断更新值 代码实现
void RotateLR(node* parent)
{node* subl parent-_left;node* sublr subl-_right;int flag sublr-_bf;RotateL(subl);//左旋右子树树中树RotateR(parent);//右旋左子树//更新平衡因子if (flag 1)//插入位置为树中树的右树{parent-_bf 0;subl-_bf -1;sublr-_bf 0;}else if (flag -1){parent-_bf 1;subl-_bf 0;sublr-_bf 0;}else if (flag 0){parent-_bf 0;subl-_bf 0;sublr-_bf 0;}else{assert(false);}
}
情况4根节点_pf为2根节点的右节点_pf为-1右左双旋
此情况就是不同与单旋时的单一枝高而是一枝中的另一枝高 同样的我们旋转之后更新我们的_bf; 代码实现
void RotateRL(node* parent)
{node* subr parent-_right;node* subrl subr-_left;int flag subrl-_bf;RotateR(subr);//右旋左子树树中树RotateL(parent);//左旋右子树//更新平衡因子if (flag 1)//插入位置为树中树的右树{parent-_bf -1;subr-_bf 0;subrl-_bf 0;}else if (flag -1){parent-_bf 0;subr-_bf 1;subrl-_bf 0;}else if (flag 0){parent-_bf 0;subr-_bf 0;subrl-_bf 0;}else{assert(false);}
} 当上面的旋转和更新_bf都完成的时候这棵树我们插入就一定是我们的AVL树了
为了验证我们的树是否真的成为了AVL树我们需要通过检查算法来比较每个节点的_bf是否正确
void _print(node* root)
{if (root nullptr)return;_print(root-_left);cout root-_data.first ;_print(root-_right);
}bool judgeBalance()
{return _judgeBalance(_root);
}bool _judgeBalance(node*root)
{if (root nullptr)return true;int hl getDeep(root-_left);//hightLeftint hr getDeep(root-_right);//hightRightint judge hr - hl;if (judge ! root-_bf){cout root-_data.first 这个节点的_pf没处理好 endl;return false;}return _judgeBalance(root-_left) _judgeBalance(root-_right);
}void testAVLTree1()
{AVLTreeint, intt;srand(time(0));for (int i 0; i 100; i){int x rand();t.insert(make_pair(x, x));}t.print();cout t.judgeBalance() endl;
} 此时我们的树就是一颗完全正确的AVL树
我们只实现了AVL树的插入算法删除算法还没有学习
这是我的完整的AVL树代码
C代码/AVL树 · future/my_road - 码云 - 开源中国 (gitee.com)
