I'm getting a segmentation foult when I am trying to run my tree implementation, and I don't know what's causing it or any way to fix it. Any help would be appreciated.
fatal.h:
CODE
#include <stdio.h>
#include <stdlib.h>
#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )
avltree.h:
CODE
typedef int ElementType;
/* START: fig4_35.txt */
#ifndef _AvlTree_H
#define _AvlTree_H
struct AvlNode;
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
AvlTree MakeEmpty( AvlTree T );
Position Find( int X, AvlTree T );
Position FindMin( AvlTree T );
Position FindMax( AvlTree T );
AvlTree Insert( int X, AvlTree T );
AvlTree Delete( int X, AvlTree T );
ElementType Retrieve( Position P );
void PrintTree(AvlTree T);
#endif /* _AvlTree_H */
/* END */
avltree.c:
CODE
#include "avltree.h"
#include <stdlib.h>
#include "fatal.h"
void printLeftTree(AvlTree T, int depth, int ignore []);
void printRightTree(AvlTree T, int depth, int ignore []);
AvlTree Rotate(AvlTree X, AvlTree Y, AvlTree Z, int NumRot);
int CheckBalance (AvlTree up, AvlTree kid);
struct AvlNode
{
int Number; /*sets element type to int*/
AvlTree Left;
AvlTree Right;
int Height;
int EqFactor; // this and the next attribute may not be necessary, depending on your implementation options
AvlTree Parent;
};
AvlTree MakeEmpty( AvlTree T )
{
if( T != 0 )
{
MakeEmpty( T->Left );
MakeEmpty( T->Right );
free( T );
}
return 0;
}
/* START: fig4_36.txt */
static int Height( Position P )
{
if( P == 0 )
return -1; // height of empty tree is -1
else
return P->Height;
}
/* END */
static int Max( int Lhs, int Rhs )
{
return Lhs > Rhs ? Lhs : Rhs;
}
int Balanced (AvlTree T){
return T->EqFactor==0 || T->EqFactor == 1 || T->EqFactor == -1;
}
int Retrieve( Position P )
{
return P->Number;
}
/*
Prints a binary Tree of the form
1
+-2
| +-3
| | +-4
| | \-5
| \-0
\-0
where 1 is the root, 2 is the root of 1's right child and 0 is the root if 1's left child
If both subtrees of a treenode are null, the subtrees are not printed
If any bugs are found in this function, please email me
If you find a bug in this function and you are able to correct it, you'll get extra credit if you report it before due day
*/
void PrintTree(AvlTree T){
int ignore [Height(T)]; //will be used to know what links need to be included when printing a line
int i;
if(T==0){
printf("0\n"); // prints an empty tree
}
else{
for(i=0; i< Height(T);i++)
ignore[i] = 0; // none of the connectors is ignored
printf("%d\n", T->Number);// print root
if(T->Right != 0 || T->Left!=0){ // if both subtrees are empty, print none
printRightTree(T->Right, 1, ignore); // print right subtree, ignoring no connector
ignore[0] = 1; // ignore first connector because there is no child after the root of the left tree
printLeftTree(T->Left, 1, ignore); // print left tree, considering there is no more children of T after T->left
}
}
}
void printLeftTree(AvlTree T, int depth, int ignore[]){
char start[2*depth +1]; // size of the prefix for this element
start[2*depth] = '\0'; // terminate the line
int i;
// build the prefix string
for(i = 0; i < (depth-1); i++){
start[2*i] = ignore[i]?' ':'|'; // print or not the connector at this level
start[2*i+1] = ' ';
}
start[2*i] = '\\'; // finish the prefix for a left tree
start[2*i+1] = '-';
if(T == 0){
printf("%s0\n",start);
}
else{
printf("%s%d\n",start, T->Number);
if(T->Right != 0 || T->Left != 0){
printRightTree(T->Right, depth+1, ignore); // print right tree
ignore[depth] = 1; // the next will be the last child of the current tree to be printed
printLeftTree(T->Left, depth+1, ignore); // print left tree
ignore[depth] = 0; // so that connections at this depth can be used by other subtrees
}
}
}
void printRightTree(AvlTree T, int depth, int ignore[]){
char start[2*depth +1]; // size of the prefix for this element
start[2*depth] = '\0'; // terminate the line
int i;
for(i = 0; i < depth-1; i++){
start[2*i] = ignore[i]?' ':'|'; // print or not the connector at this level
start[2*i+1] = ' ';
}
start[2*i] = '+'; // finish the prefix for a right tree
start[2*i+1] = '-';
if(T == 0){
printf("%s0\n",start);
}
else{
printf("%s%d\n",start, T->Number);
if(T->Left != 0 || T->Right!= 0){
printRightTree(T->Right, depth+1, ignore);// print right tree
ignore[depth] = 1; // the next will be the last child of the current tree to be printed
printLeftTree(T->Left, depth+1, ignore);// print left tree
ignore[depth] = 0; // so that connections at this depth can be used by other subtrees
}
}
}
/*
* Return the Position (conceptually the same as AvlTree) that contains element
* or 0 if element does not exist
*/
Position Find( int X, AvlTree T )
{
if (X > T->Number)
{
Find(X, T->Right); //searches for given element by following right subtree if X is greater
} // than T's value and the left subtree if X is less than T's value
else if (X < T->Number) // and returns the node that contains the value
{
Find(X, T->Left);
}
else
{
return T;
}
}
/*
* Return Position that contains the lowest element in the Tree
* Remember AVL properties
*/
Position FindMin( AvlTree T )
{
while (T->Left != 0)
{
T = T->Left; //follow left subtrees until end is reached
}
return T;
}
/*
* Return Position that contains the highest element in the Tree
* Remember AVL rules
*/
Position FindMax( AvlTree T )
{
while (T->Right != 0)
{
T = T->Right; //follow right subtrees until the end is reached
}
return T;
}
/*
* Rotates the tree starting at Z
* Returns the new node that replaced Z
* This method should be used in insert and delete
* Feel free to add parameters if you need, correcting also the prototype
* An explanation is required for added parameters
*/
AvlTree Rotate(AvlTree X, AvlTree Y, AvlTree Z, int NumRot)
{
/*if (NumRot =2)
{
if (Y->Number > X->Number)
{
Y->Left = X->Right;
X->Right = Y;
}
else
{
Y->Right = X->Left;
X->Left = Y;
}
}
*/
if (X->Number > Z->Number)
{
Z->Right = X->Left;
X->Left = Z;
}
else
{
Z->Left = X->Right;
X->Right = Z;
}
if (NumRot = 2)
{
Rotate(X, Z, Y, 1);
}
return X;
}
/*
* Feel free to build new functions to use inside Insert
* A recursive Solution may be a good option
* Check the TextBook for the recursive solution using single and double rotation
*/
AvlTree Insert( int X, AvlTree T )
{
AvlTree kid;
if (X > T->Number)
{
if (T->Right = 0)
{
AvlTree insert;
AvlTree up;
insert = malloc(sizeof(struct AvlNode));
T->Right = insert; //puts new node on right leaf
insert->Parent = T; //assigns leaf's parent
insert->Number = X; //assigns leaf's value
insert->Left = 0; //assigns children to 0
insert->Right = 0; // " "
insert->Height = 0; //assigns leaf's height
up = insert;
int count = 0;
while (up->Parent != 0)
{
count++;
if (insert->Parent->Height < count)
{
insert->Parent->Height = count;
}
insert = insert->Parent;
}
CheckBalance(insert->Left, kid);
}
else
{
Insert(X, T->Right);
}
}
else if (X < T-> Number)
{
if (T->Left = 0)
{
AvlTree insert;
insert = malloc(sizeof(struct AvlNode));
T->Left = insert; //see previous
insert->Parent = T;
insert->Number = X;
insert->Left = 0;
insert->Right = 0;
insert->Height = T->Height + 1;
int count = 0;
while (insert->Parent != 0)
{
count++;
if (insert->Parent->Height < count)
{
insert->Parent->Height = count;
}
insert = insert->Parent;
}
CheckBalance(insert->Left, kid);
}
else
{
Insert(X, T->Left);
}
}
}
/*
* Deletes element from T following BST rules
* (Replaced by in order successor or predecessor, if children exist)
* (Node is deleted if it has no children)
*
* Verify if tree is still balanced
* Rebalance if not, using Rotate
*/
AvlTree Delete( int X, AvlTree T )
{
AvlTree remove;
remove = Find(X, T);
AvlTree MaxMin;
MaxMin = remove->Left;
while (MaxMin->Right != 0)
{
MaxMin = MaxMin->Right;
}
MaxMin->Parent = remove->Parent;
MaxMin->Right = remove->Right;
if (MaxMin->Left != 0)
{
MaxMin->Left->Left = remove->Left;
}
else
{
MaxMin->Left = remove->Left;
}
if (MaxMin->Parent->Number > MaxMin->Number)
{
MaxMin->Parent->Left = MaxMin;
}
else
{
MaxMin->Parent->Right = MaxMin;
}
AvlTree kid;
CheckBalance(MaxMin->Left, kid);
}
int CheckBalance (AvlTree up, AvlTree kid)
{
while (up->Parent != 0)
{
up = up->Parent;
int Balance;
Balance = (up->Right->Height)-(up->Left->Height);
if ((Balance < -1) || (Balance > 1))
{
if (Balance < -1)
{
kid = up->Left;
if (kid->Left->Height > kid->Right->Height)
{
Rotate(kid->Left, kid, up, 1);
}
else
{
Rotate(kid->Right, kid, up, 2);
}
}
else if (Balance > 1)
{
kid = up->Right;
if (kid->Right->Height > kid->Left->Height)
{
Rotate(kid->Right, kid, up, 1);
}
else
{
Rotate(kid->Left, up, kid, 2);
}
}
return -1;
}
}
return 1;
}
testavl.c:
CODE
#include "avltree.h"
#include <stdio.h>
main( )
{
AvlTree T;
Position P;
int i;
int j = 0;
T = MakeEmpty( 0 );
for( i = 0; i < 50; i++, j = ( j + 7 ) % 50 )
T = Insert( j, T );
for( i = 0; i < 50; i++ )
if( ( P = Find( i, T ) ) == 0 || Retrieve( P ) != i )
printf( "Error at %d\n", i );
/*
for( i = 0; i < 50; i += 2 )
T = Delete( i, T );
for( i = 1; i < 50; i += 2 )
if( ( P = Find( i, T ) ) == 0 || Retrieve( P ) != i )
printf( "Error at %d\n", i );
for( i = 0; i < 50; i += 2 )
if( ( P = Find( i, T ) ) != 0 )
printf( "Error at %d\n", i );
*/
/*
T = Insert(5,T);
T = Insert(2,T);
T = Insert(3,T);
T = Insert(4,T);
T = Insert(7,T);
T = Insert(10,T);
T = Insert(8,T);
T = Insert(11,T);
T = Insert(1,T);
T = Insert(12,T);
T = Insert(13,T);
T = Insert(14,T);
T = Insert(15,T);
*/
printf( "Min is %d, Max is %d\n", Retrieve( FindMin( T ) ), Retrieve( FindMax( T ) ) );
PrintTree(T);
return 0;
}
| 