【数据结构】AVL树
发布时间：2021-03-31 11:36:55 所属栏目：安全 来源：网络整理
导读：1、AVL树简介 ????? AVL树本质上还是一棵二叉搜索树，又称高度平衡的二叉搜索树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。对于二叉搜索树的介绍和实现，可查看本人上一篇博客。 2、AVL树的特点 1）本身首先是一棵二叉搜索树
|
左单旋： template<class?K,?class?V>
void?AVLTree<K,?V>::_RotateL(Node*&?parent)
{
?Node*?subR?=?parent->_right;
?Node*?subRL?=?subR->_left;
?parent->_right?=?subRL;//1
?subR->_parent?=?parent->_parent;//1
?subR->_left?=?parent;//2
?parent->_parent?=?subR;//2
?if?(subRL)//注意不为空，进行链接
??subRL->_parent?=?parent;
?parent->_bf?=?subR->_bf?=?0;
?//进行subR的父亲结点和subR的链接
?if?(subR->_parent?==?NULL)//为空时，parent为根结点，更改根结点
??_root?=?subR;
?else//不为空，进行链接
?{
??if?(subR->_parent->_key?>?subR->_key)
???subR->_parent->_left?=?subR;
??else
???subR->_parent->_right?=?subR;
?}
?parent?=?subR;
}
（编辑：辽源站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |