【数据结构】AVL树

右单旋：

template<class?K,?V>::_RotateR(Node*&?parent)
{
?Node*?subL?=?parent->_left;
?Node*?subLR?=?subL->_right;
?//不能变换顺序
?parent->_left?=?subL->_right;//1
?subL->_parent?=?parent->_parent;//1
?subL->_right?=?parent;//2
?parent->_parent?=?subL;//2
?if?(subLR)//注意不为空，进行链接
??subLR->_parent?=?parent;
?parent->_bf?=?subL->_bf?=?0;
?//进行subL的父亲结点和subL的链接
?if?(subL->_parent?==?NULL)//为空时，parent为根结点，更改根结点
??_root?=?subL;
?else//不为空，进行链接
?{
??if?(subL->_parent->_key?>?subL->_key)
???subL->_parent->_left?=?subL;
??else
???subL->_parent->_right?=?subL;
?}
?parent?=?subL;
}

左右旋转：

template<class?K,?V>::_RotateLR(Node*&?parent)
{
?Node*?pNode?=?parent;//需重新定义parent，在进行左右旋转后，parent指向发生了变化
?Node*?subLNode?=?pNode->_left;
?Node*?subLRNode?=?subLNode->_right;
?_RotateL(parent->_left);
?_RotateR(parent);
?//在单旋时，parent和subL的平衡因子都为0，在进行左右旋转和右左旋转会出错,故重新设置平衡因子
?//subLRNode的平衡因子存在三种情况：为0，为-1，为1。subLRNode的平衡因子影响parent和subL的平衡因子
?if?(subLRNode->_bf?==?1)
?{
??pNode->_bf?=?1;
??subLNode->_bf?=?0;
?}
?else?if?(subLRNode->_bf?==?-1)
?{
??pNode->_bf?=?0;
??subLNode->_bf?=?-1;
?}
?else
?{
??parent->_bf?=?0;
??subLNode->_bf?=?0;
?}
}

右左旋转：

template<class?K,?V>::_RotateRL(Node*&?parent)
{
?Node*?pNode?=?parent;
?Node*?subRNode?=?pNode->_right;
?Node*?subRLNode?=?subRNode->_left;
?_RotateR(parent->_right);
?_RotateL(parent);
?if?(subRLNode->_bf?==?1)
?{
??pNode->_bf?=?-1;
??subRNode->_bf?=?0;
?}
?else?if?(subRLNode->_bf?==?-1)
?{
??pNode->_bf?=?0;
??subRNode->_bf?=?1;
?}
?else
?{
??pNode->_bf?=?0;
??subRNode->_bf?=?0;
?}
}

测试用例如下：

void?AVLTreeTest()
{
?AVLTree<int,?int>?avlt;
?//int?arr[10]?=?{?16,?3,?7,?11,?9,?26,?18,?14,?15,?23?};
?int?arr[10]?=?{?4,?2,?6,?1,?5,?16,?14?};
?for?(int?i?=?0;?i?<?10;?++i)
?{
??avlt.Insert(arr[i],?i);
??avlt.PrintAVLTree();
?}
?cout?<<?avlt.IsBalance()?<<?endl;
}

（编辑：辽源站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!