c++ - AVLTree（加载和平衡二叉树）

Question

#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

//header file 
template <class V>
struct Node{
   int height;
   V key;
   string value;
   Node<V> *Parent;
   Node<V> *Left;
   Node<V> *Right;

   Node (V Key,string Val)
   {
        this->key=Key;
        this->value=Val;
        this->Parent=NULL;
        this->Left=NULL;
        this->Right=NULL;
   }
};

template <class V>
class AVLTree
{
  private:
          Node<V> *Root;
  public:
         AVLTree();
         void deleteTree(Node<V> *node);
         ~AVLTree();
         int height(Node<V> *node);
         int TreeHeight();
         Node<V> *tallGrandChild(Node<V> *node);
         void rotate(Node<V> *node);
         bool isBalanced(Node<V> *node);
         void balance(Node<V> *node);
         void balanceTree();
         void insert(V key,string value);
         void loadTree(const char *file);
         string Search(V key);     
};            

//constructor
template <class T>
AVLTree<T>::AVLTree() 
{
   Root=NULL;
}

template<class V>   
void AVLTree<V>::deleteTree(Node<V> *node)
{
 Node<V> *l=node->Left;
 Node<V> *r=node->Right;

 if (l!=NULL)
    deleteTree(l);
 else if (r!=NULL)
      deleteTree(r);

 delete node;                       
}

//destructor
template<class V>
AVLTree<V>::~AVLTree()
{
    deleteTree(Root);
}                  

//calculating height recursively         
template <class V>
int AVLTree<V>::height(Node<V> *node)
{
   int h=0;
    if (node!=NULL)
    {
        h=max(height(node->Left),height(node->Right))+1;
    }
    return h;
}

//function to find out height of tree
template <class V>
int AVLTree<V>::TreeHeight()
{
  int h=height(Root);
  return h;
}

//get the grandchild of node
template <class V>
Node<V>* AVLTree<V>::tallGrandChild(Node<V> *node)
{
    cout<<"GC before"<<endl;           

    Node<V> *l=node->Left;
    Node<V> *r=node->Right;
    cout<<"GC middle"<<endl;
    if (l!=NULL && r!=NULL)
    {
      if (height(l)>=height(r))
      {
         if (l->Left!=NULL && l->Right!=NULL)
         {                       
           if (height(l->Left)>=height(l->Right))
               return l->Left;
           else
               return l->Right;
         }
      }
     }
     else
     {
        if (r->Left!=NULL && r->Right!=NULL)
        {
          if (height(r->Left)>=height(r->Right))
              return r->Left;
          else
              return r->Right;
        }
     }
  }
cout<<"GC end"<<endl;
return NULL;
}                             


//check node if it is balanced or not                 
template <class V>
bool AVLTree<V>::isBalanced(Node<V> *node)
{
 int l,r;
 if (node->Left==NULL)
     l=0;

 if (node->Right==NULL)
     r=0;

 if (node->Left!=NULL)        
    l=height(node->Left);

 if (node->Right!=NULL)
    r=height(node->Right);

 cout<<"isbalanced checking"<<endl;
 if ((l-r)>1 || (l-r)<-1)
 {
      return false;
 }
 else 
 {
     return true;
 }
}

// rotate the node that is unbalanced,its parent and grandparent
template <class V>
void AVLTree<V>::rotate(Node<V> *node)
{
 if (Root==NULL)
 {
    return;
 }
 if (Root->Left==NULL && Root->Right==NULL)
 {
    return;   
 }
 Node<V> *parent,*grandparent;
 parent=node->Parent;
 grandparent=parent->Parent;
 if (grandparent==NULL)
    return;

 V min=node->key;
 Node<V> *A,*B,*C;
 A=node;

 if (parent->key<min)
 {
     min=parent->key;
     A=parent;
 }        
 if (grandparent->key<min)
 {
      min=grandparent->key;
      A=grandparent;
 }

 if (parent==A)
 {
     if (grandparent->key<node->key)
     {
         B=grandparent;
         C=node;
     }
     else
     {
         B=node;
         C=grandparent;
     }
 }

 if (grandparent==A)
 {
     if (parent->key<node->key)
     {
         B=parent;
         C=node;
     }
     else
     {
         B=node;
         C=parent;
     }
 }

 if (node==A)
 {
     if (grandparent->key<parent->key)
     {
             B=grandparent;
             C=parent;
     }
     else
     {
             B=parent;
             C=grandparent;
     }
 }

 if (grandparent->Parent!=NULL)
 {
    B->Parent=grandparent->Parent;
    B->Left=A;
    B->Right=C;
    A->Parent=B;
    C->Parent=B;
 } 
 else
 {
    B->Left=A;
    B->Right=C;
    A->Parent=B;
    C->Parent=B;
 }       
}     
//balance the node and all nodes following it.this is a recursive function that i //
 //came up with
template <class V>
void AVLTree<V>::balance(Node<V> *node)
{
   if (node->Left!=NULL) 
       balance(node->Left); 
    if (node->Right!=NULL)
       balance(node->Right);

   Node<V> *temp=node;


    if (temp->Parent!=NULL && (temp->Parent)->Parent!=NULL)
    {
       temp=temp->Parent;
       temp=temp->Parent;     
       if (isBalanced(temp)==0)
       {
           cout<<"balance func check 3"<<endl;                    
           Node<V> *temp1=tallGrandChild(temp);
           if (temp1!=NULL)
              rotate(temp1);
       }      
}
}
//function to balance whole tree
template <class V>
void AVLTree<V>::balanceTree()
{
   balance(Root);
}   

//insert a new key and value
template <class V>
void AVLTree<V>::insert(V key,string value)
{
   Node<V> *temp,*temp1;
   if (Root==NULL)
   {
      Root=new Node<V>(key,value);
      return;
   }          
 temp=Root;

 if (Root!=NULL)
 {
    while (temp!=NULL)
    {
       temp1=temp;
       if (key>temp->key)
       {
            temp=temp->Right;
       }
       else if (key<temp->key)
       {
            temp=temp->Left;
       }

    }

    if (temp1!=NULL)
    {
        temp=new Node<V>(key,value);
        temp->Parent=temp1;
        if (temp1->key>key)
        {
            temp1->Left=temp;
        }
        else if (temp1->key<key)
        {
            temp1->Right=temp;
        }
    }
 }               
}                                  

//reading data from a file and storing it in AVLTree using insert function
template <class V>               
void AVLTree<V>::loadTree(const char *file)
{
 ifstream fin;
 fin.open(file);

 if(fin.fail())
 cout<<"Error in opening file!"<<endl;

 while (!fin.eof())
 {
       string buffer;
       V buff;
       getline(fin,buffer,'~');
       fin>>buff;
       if (!buff)
          continue;
       insert(buff,buffer);

 }


 fin.close();
}

我正在制作一个 AVL 树作为分配。平衡树时遇到问题。平衡的
功能是递归的。当我运行代码时，2 到 3 秒后，我得到一个分段错误。当我调试它时，问题出在 if 条件下的平衡函数中：

if (temp->Parent!=NULL && (temp->Parent)->Parent!=NULL)
       temp=temp->Parent;
       temp=temp->Parent;     

但我无法弄清楚什么是错误的，因为只有当节点的父节点和祖父节点不为 NULL 时才能输入 if 条件。