#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 条件。