📄 avlindex.h
字号:
}
c_root->setparent(it2);
it1->setparent(it2);
if(it1->rightChild()!=NULL) it1->rightChild()->setparent(it1);
if(c_root->leftChild()!=NULL) c_root->leftChild()->setparent(c_root);
if(it2->balance==1)
{
it1->balance=0;
c_root->balance=-1;
}
else {
it1->balance=1;c_root->balance=0;
if(it1->IsLeaf())it1->balance=0;
}
it2->balance=0;
c_root=it2;
}
else if(c_root->leftChild()!=NULL && c_root->leftChild()->balance==0 )
{
TreeNode * it=c_root->leftChild();
c_root->setLeftChild(it->rightChild());
c_root->leftChild()->setparent(c_root);
it->setRightChild(c_root);
if(c_root->parentNode()!=NULL)
{
if(c_root->parentNode()->getValue()>c_root->getValue())
c_root->parentNode()->setLeftChild(it);
else c_root->parentNode()->setRightChild(it);
}
it->setparent(c_root->parentNode());
c_root->setparent(it);
it->balance=-1;
c_root->balance=1;
c_root=it;
}
}
//当结点的平衡因子为2时，进行右旋转
void R_Balance(Link* listArray,TreeNode* & c_root,int temp,int pos){
//结点为-2的图形为"\" 情况---------------------------
if(c_root->rightChild()!=NULL && c_root->rightChild()->balance==-1)
{
TreeNode*it=c_root->rightChild();
c_root->setRightChild(it->leftChild());
it->setLeftChild(c_root);
it->setparent(c_root->parentNode());
if(it->parentNode()!=NULL)
{
int number1,number2;
string* SubString1=stringCut(listArray[it->getValue()].data,number1);
string* SubString2=stringCut(listArray[it->parentNode()->getValue()].data,number2);
if(SubString1[pos]>SubString2[pos]) it->parentNode()->setRightChild(it);
else it->parentNode()->setLeftChild(it);
}
c_root->setparent(it);
if(c_root->leftChild()!=NULL) c_root->rightChild()->setparent(c_root);
c_root->balance=0;it->balance=0;
c_root=it;
}
//结点为-2 的折线情况---------------------------
else if(c_root->rightChild()!=NULL && c_root->rightChild()->balance==1)
{
TreeNode* it1=c_root->rightChild();
TreeNode* it2=it1->leftChild();
it1->setLeftChild(it2->rightChild());
c_root->setRightChild(it2->leftChild());
it2->setRightChild(it1);
it2->setLeftChild(c_root);
it2->setparent(c_root->parentNode());
if(it2->parentNode()!=NULL)
{
int number1,number2;
string* SubString1=stringCut(listArray[it2->getValue()].data,number1);
string* SubString2=stringCut(listArray[it2->parentNode()->getValue()].data,number2);
if(SubString1[pos]<SubString2[pos]) it2->parentNode()->setLeftChild(it2);
else it2->parentNode()->setRightChild(it2);
}
c_root->setparent(it2);
it1->setparent(it2);
if(it1->leftChild()!=NULL) it1->leftChild()->setparent(it1);
if(c_root->rightChild()!=NULL) c_root->rightChild()->setparent(c_root);
if(it2->balance==-1)
{
it1->balance=0;
c_root->balance=1;
}
else {
it1->balance=-1;c_root->balance=0;
if(it1->IsLeaf()) it1->balance=0;
}
it2->balance=0;
c_root=it2;
}
else if(c_root->rightChild()!=NULL && c_root->rightChild()->balance==0)
{
TreeNode * it=c_root->rightChild();
c_root->setRightChild(it->leftChild());
c_root->rightChild()->setparent(c_root);
it->setLeftChild(c_root);
if(c_root->parentNode()!=NULL)
{
if(c_root->parentNode()->getValue()>c_root->getValue())
c_root->parentNode()->setLeftChild(it);
else c_root->parentNode()->setRightChild(it);
}
it->setparent(c_root->parentNode());
c_root->setparent(it);
it->balance=1;
c_root->balance=-1;
c_root=it;
}
}
public:
AVL(){N_root=NULL;NodeCount=0;}
~AVL(){
clearHlp(N_root);
NodeCount=0;
}
void clear(){
clearHlp(N_root);
N_root=NULL;
NodeCount=0;
}
bool insert(Link* listArray,int temp,int pos){//数据数组的首地址，当前需存储的地址，主键所在的位置
TreeNode* insertNode=NULL;
N_root=insertHlp(listArray,N_root,temp,insertNode,pos);//insertNode是插入的该叶子结点
if(insertNode==NULL) return false;
TreeNode* parent=insertNode->parentNode();//该叶子结点的双亲结点
while(parent!=NULL){
if(parent->leftChild()==insertNode) parent->balance ++;
else if(parent->rightChild()==insertNode) parent->balance--;
if(parent->balance==0) break;
int it=N_root->balance;//it记录根结点平衡因子,若根结点的平衡因子>1,则根结点必须发生变化,当跳出这个循环时,必须将parent赋予根结点
if (parent->balance == -2)R_Balance(listArray,parent,temp,pos);//右旋转
else if (parent->balance == 2)L_Balance(listArray,parent,temp,pos);//左旋转
if (!parent->balance) {if(it==2 || it==-2) N_root=parent;break;}
insertNode=parent; parent = parent->parentNode();//将插入结点和双亲结点同时向上传递，进行比较判断相邻的两个结点是左向上还是右向上来判定是++操作还是 --操作
}
++NodeCount;
return true;
}
void removeMin(TreeNode* &min){
N_root=deletemin(N_root,min);
--NodeCount;
}
//与插入操作类似-删除指定位置的数据---------------------------------------------------------------
bool remove(Link* listArray,int temp,int pos){
if(listArray[temp].sign!=-1) return false;
TreeNode* removeNode=NULL;
N_root=removeHlpNo(listArray,N_root,temp, removeNode,pos);
if(removeNode==NULL) return false;
TreeNode* parent= removeNode->parentNode();//该结点的双亲结点
if(removeNode->parentNode()==NULL && removeNode->IsLeaf()) N_root=NULL;
int j;
j=parent->balance;
while(parent!=NULL){
if(listArray[parent->getValue()].data> listArray[removeNode->getValue()].data )
parent->balance --;
else parent->balance++;
int it1=parent->balance,it2=100,it3=100;
if(parent->leftChild()!=NULL) it2=parent->leftChild()->balance;
if(parent->rightChild()!=NULL) it3=parent->rightChild()->balance;
if(j==0)break;
int it=N_root->balance;//it记录根结点平衡因子,若根结点的平衡因子>1,则根结点必须发生变化,当跳出这个循环时,必须将parent赋予根结
if (parent->balance == -2)R_Balance(listArray,parent,temp,pos);//右旋转
else if (parent->balance == 2)L_Balance(listArray,parent,temp,pos);//左旋转
if( (it1==2 &&it2==0) || (it1==-2 && it3==0) ) break;
if(it==2 || it==-2) N_root=parent;
removeNode=parent; parent = parent->parentNode();//将插入结点和双亲结点同时向上传递，进行比较判断相邻的两个结点是左向上还是右向上来判定是++操作还是 --操作
if(parent!=NULL) j=parent->balance;
}
--NodeCount;
return true;
}
//删除指定主键的数据-----------------------------------------
bool remove(Link* listArray,string MainKeyData,int pos,int& getPos){//pos是指主键在数据重点中的位置，getPos是指数据在数组中的位置
TreeNode* removeNode=NULL;
N_root=removeHlpData(listArray,N_root,MainKeyData, removeNode,pos);
if(removeNode==NULL) return false;
int temp=removeNode->getValue();
getPos=temp;
TreeNode* parent= removeNode->parentNode();//该结点的双亲结点
if(removeNode->parentNode()==NULL && removeNode->IsLeaf()) N_root=NULL;
int j=parent->balance;
while(parent!=NULL){
if(listArray[parent->getValue()].data> listArray[removeNode->getValue()].data )
parent->balance --;
else parent->balance++;
int it1=parent->balance,it2=100,it3=100;
if(parent->leftChild()!=NULL) it2=parent->leftChild()->balance;
if(parent->rightChild()!=NULL) it3=parent->rightChild()->balance;
if(j==0)break;
int it=N_root->balance;//it记录根结点平衡因子,若根结点的平衡因子>1,则根结点必须发生变化,当跳出这个循环时,必须将parent赋予根结
if (parent->balance == -2)R_Balance(listArray,parent,temp,pos);//右旋转
else if (parent->balance == 2)L_Balance(listArray,parent,temp,pos);//左旋转
if( (it1==2 &&it2==0) || (it1==-2 && it3==0) ) break;
if(it==2 || it==-2) N_root=parent;
removeNode=parent; parent = parent->parentNode();//将插入结点和双亲结点同时向上传递，进行比较判断相邻的两个结点是左向上还是右向上来判定是++操作还是 --操作
if(parent!=NULL) j=parent->balance;
}
--NodeCount;
return true;
}
bool find(Link* listArray,const string k,TreeNode*& e,int pos){
return findHlp(listArray,N_root,k,e,pos);
}
void print(Link* listArray){
printHlp(listArray,N_root,2);
}
TreeNode* TreeRoot(){return N_root;}
void InOrderRoot(string Sbegin,string Send,Link* listArray,int pos,Tableheader header){
InOrder(Sbegin,Send,listArray,N_root,pos,header);
}
string* stringCut(string pString, int& number)const{
int counter, divideLines;
counter = (int)pString.length(); //counter is used to store the length of the string
divideLines = 0; //to count the total number of the divideLine "\"
while(counter){
//get the total number of the divideLines
if(pString.substr(counter,1) == "\\")
++divideLines;
--counter;
}
//creat an array to store the subStrings that we will get
string *pSubString = new string[divideLines+1];
int i, j = 0, start = 0, end;
counter = (int)pString.length();
//to get and store the subStrings
for(i=0; i<counter; ++i){
//to avoid the situation that the first of word is "\"
if(i == 0 && pString.substr(i,1) == "\\"){
++i;
start = 1;
}
if(pString.substr(i,1) == "\\"){
end = i-1;
pSubString[j++] = pString.substr(start, end-start+1);
start = i+1;
}
if(i == counter-1 && pString.substr(i,1) != "\\"){
end = i;
pSubString[j++] = pString.substr(start, end-start+1);
}
}
number = j;
return pSubString;
}
};
#endif⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -