爲什麼我的AVL樹刪除功能不平衡？

-1

我的刪除功能無法正常工作。當它刪除節點時，它不會重新平衡整個樹。有時它會平衡左側的子樹，但會忽略整個右側的子樹。該代碼是很長爲什麼我的AVL樹刪除功能不平衡？

class AVLTree 
{ 
public: 
    void insert(const DataType &item); 
    void graph(ostream &out) const; 
    void remove(DataType &value); 
private: 
    class AVLNode 
    { 
    public: 
     DataType data; 
     int balanceFactor; 
     AVLNode *left; 
     AVLNode *right; 
     AVLNode():balanceFactor(0),left(NULL),right(NULL){} 
     AVLNode(DataType item):balanceFactor(0), data(item),left(NULL), right(NULL){} 
    }; 
    typedef AVLNode* AVLNodePointer; 
    AVLNodePointer myRoot; 
    int height(AVLTree<DataType>::AVLNodePointer temp); 
    int different(AVLTree<DataType>::AVLNodePointer temp); 
    AVLNodePointer ll_rotation(AVLTree<DataType>::AVLNodePointer parent); 
    AVLNodePointer rr_rotation(AVLTree<DataType>::AVLNodePointer parent); 
    AVLNodePointer lr_rotation(AVLTree<DataType>::AVLNodePointer parent); 
    AVLNodePointer rl_rotation(AVLTree<DataType>::AVLNodePointer parent); 
    AVLNodePointer balance_tree(AVLTree<DataType>::AVLNodePointer temp); 
    AVLNodePointer insertAux(AVLTree<DataType>::AVLNodePointer &subtreeRoot,const DataType &value); 
    AVLNodePointer findmin(AVLTree<DataType>::AVLNodePointer temp); 
    AVLNodePointer deleteAux(AVLTree<DataType>::AVLNodePointer temp,DataType &value); 
    void graphAux(ostream &out,int indent, AVLTree<DataType>::AVLNodePointer subtreePtr) const; 
          }; 
template<typename DataType> 
int AVLTree<DataType>::height(AVLTree<DataType>::AVLNodePointer temp) 
{ 
    int h=0; 
    if(temp!=NULL) 
{ 
    int left_height=height(temp->left); 
    int right_height=height(temp->right) 
    int max_height =max(left_height,right_height); 
    h=max_height +1; 
} 
return h; 
} 

template<typename DataType> 
int AVLTree<DataType>::different(AVLTree<DataType>::AVLNodePointer temp) 
{ 
int left_height=height(temp->left); 
int right_height=height(temp->right); 
temp->balanceFactor=left_height-right_height; 
return temp->balanceFactor; 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::ll_rotation(AVLTree<DataType>::AVLNodePointer parent) 
{ 
AVLTree<DataType>::AVLNodePointer temp; 
temp=parent->left; 
parent->left=temp->right; 
temp->right=parent; 
return temp; 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::rr_rotation(AVLTree<DataType>::AVLNodePointer parent) 
{ 
AVLTree<DataType>::AVLNodePointer temp; 
temp=parent->right; 
parent->right=temp->left; 
temp->left=parent; 
return temp; 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::lr_rotation(AVLTree<DataType>::AVLNodePointer parent) 
{ 
AVLTree<DataType>::AVLNodePointer temp; 
temp=parent->left; 
parent->left=rr_rotation(temp); 
return ll_rotation(parent); 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::rl_rotation(AVLTree<DataType>::AVLNodePointer parent) 
{ 
AVLTree<DataType>::AVLNodePointer temp; 
temp=parent->right; 
parent->right=ll_rotation(temp); 
return rr_rotation(parent); 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::balance_tree(AVLTree<DataType>::AVLNodePointer temp) 
{ 
temp->balanceFactor=different(temp); 

if(temp->balanceFactor>1) 
{ 
    if(different(temp->left)>0) 
    { 
     temp=ll_rotation(temp); 
    } 
    else 
    { 
     temp=lr_rotation(temp); 
    } 
} 
else if(temp->balanceFactor<-1) 
{ 
    if(different(temp->right)>0) 
    { 
     temp=rl_rotation(temp); 
    } 
    else 
    { 
     temp=rr_rotation(temp); 
    } 
} 
return temp; //no balance needed 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::findmin(AVLTree<DataType>::AVLNodePointer temp) 
{ 
    if(temp->left==NULL) 
    { 
     return temp; 
    } 
    else 
    { 
     findmin(temp->left); 
    } 
} 
template<typename DataType> 
void AVLTree<DataType>::remove(DataType &value) 
{ 
    deleteAux(myRoot,value); 
} 

template<typename DataType> 
typename AVLTree<DataType>::AVLNodePointer AVLTree<DataType>::deleteAux(AVLTree<DataType>::AVLNodePointer temp,DataType &value) 
{ 

if(temp==NULL) 
{ 
    return temp; 
} 
if (value<temp->data) 
{ 
    temp->left=deleteAux(temp->left,value); 
    temp=balance_tree(temp); 
} 
else if(value>temp->data) 
{ 
    temp->right=deleteAux(temp->right,value); 
    temp= balance_tree(temp); 
} 
else 
{ 
    if(temp->left==NULL && temp->right==NULL) 
    { 
     AVLTree<DataType>::AVLNodePointer temp1; 
     temp1=temp; 
     delete temp1; 
     temp=NULL; 
    } 
    else if(temp->left==NULL) 
    { 
     AVLTree<DataType>::AVLNodePointer temp1=temp; 
     temp=temp->right; 
     delete temp1; 
     temp1=NULL; 

    } 
    else if(temp->right==NULL) 
    { 
     AVLTree<DataType>::AVLNodePointer temp1=temp; 
     temp=temp->left; 
     delete temp1; 
     temp1=NULL; 

    } 
    else 
    { 
     AVLTree<DataType>::AVLNodePointer temp1=findmin(temp->right); 
     temp->data=temp1->data; 
     temp->right=deleteAux(temp->right, temp1->data); 
    } 

} 
return temp; 
}

只需編輯忘了添加刪除功能

來源

2015-04-06 Tony

你應該嘗試使用調試器，看看是怎麼回事，通過您的代碼進行調試。

跳出來的一件事就是您在第一次調用時不使用來自deleteAux的返回值，所以如果deleteAux更改根的值，您將無法獲得正確的根值。嘗試將您的remove功能更改爲：

myRoot = deleteAux(myRoot,value);

來源

2015-04-06 01:23:42

爲什麼我的AVL樹刪除功能不平衡？

回答

相關問題