AVL Tree problem

StTheo 0 Newbie Poster
14 Years Ago
I'm working on an AVL tree, and I've been getting segfault errors when trying to access one of my nodes. The error is raised when I try to call the balance() function for one of my node's children.
//////////////////////////////////////////////////////////////////////
/// @file main.cpp
/// @brief The main implementation file
//////////////////////////////////////////////////////////////////////

#include <cppunit/extensions/TestFactoryRegistry.h>
#include <cppunit/ui/text/TestRunner.h>

int main ()
{
    CppUnit::TextUi::TestRunner runner;
    CppUnit::TestFactoryRegistry &registry
        = CppUnit::TestFactoryRegistry::getRegistry();
		
    runner.addTest (registry.makeTest ());
    return runner.run ("", false);
}
//////////////////////////////////////////////////////////////////////
/// @file exception.h
/// @brief The header file for custom exceptions
//////////////////////////////////////////////////////////////////////

#ifndef EXCEPTION_H
#define EXCEPTION_H

#include <string>
using std::string;

enum Error_Type { CONTAINER_FULL, CONTAINER_EMPTY, OUT_OF_BOUNDS };

class Exception
{
  public:
    Exception (Error_Type, string);
    Error_Type error_code ();
    string error_message ();

  private:
    Error_Type m_error_code;
    string m_error_message;
};

#endif
//////////////////////////////////////////////////////////////////////
/// @file exception.cpp
/// @brief The implementation file for custom exceptions
//////////////////////////////////////////////////////////////////////

#include "exception.h"

Exception::Exception (Error_Type _error_code, string _error_message)
{
    m_error_code = _error_code;
    m_error_message = _error_message;
}

Error_Type Exception::error_code ()
{
    return m_error_code;
}

string Exception::error_message ()
{
    return m_error_message;
}
//////////////////////////////////////////////////////////////////////
/// @file bt.h
/// @brief Header file for the binary tree
//////////////////////////////////////////////////////////////////////

#ifndef BT_H
#define BT_H

#include "btn.h"
#include "exception.h"
#include "btpreorderiterator.h"
#include "btinorderiterator.h"
#include "btpostorderiterator.h"

template <class generic>
class BT
{
public:
	BT();												// 
	~BT();												// 
	BT(BT &);											// 
	BT & operator= (const BT &);						// 
	void clear ();										// 
	bool empty ();										// Complete
	unsigned int size ();								// Complete
	typedef BTPreorderIterator<generic> PreOrder;		// Complete
	typedef BTInorderIterator<generic> InOrder;			// Complete
	typedef BTPostorderIterator<generic> PostOrder;		// Complete
	PreOrder pre_begin () const;						// Complete
	PreOrder pre_end () const;							// Complete
	InOrder in_begin () const;							// Complete
	InOrder in_end () const;							// Complete
	PostOrder post_begin () const;						// Complete
	PostOrder post_end () const;						// Complete

protected:
	BTN<generic> * m_root;
	unsigned int m_size;
	void swap (BTN<generic> *, BTN<generic> *);
};

#include "bt.hpp"
#endif

//////////////////////////////////////////////////////////////////////
/// @file bt.hpp
/// @brief Function implementation for the avl class
//////////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;

template <class generic>			/* Constructor */
Avl<generic>::Avl () {
	BT<generic>::m_root = NULL;
	BT<generic>::m_size = 0;
}

template <class generic>			/* Destructor */
Avl<generic>::~Avl () {
}

template <class generic>			/* Insert */
void Avl<generic>::insert (generic x) {
	if (Bst<generic>::hasValue(x)) {
		return;
	}
	Bst<generic>::insert (x);
	BTN<generic> * temp = Bst<generic>::p_search (x);
	while (abs(BT<generic>::m_root->balance())>1) {
		if (temp->balance() == 2) {
			int lBalance = temp->l->balance();
			if (lBalance == -1) {
				rotateLL(temp);
			} else {
				rotateLR(temp);
			}
		} else if (temp->balance() == -2) {
			int rBalance = temp->r->balance();
			if (rBalance == 1) {
				rotateRR(temp);
			} else {
				rotateRL(temp);
			}
		}
		if ((abs(temp->balance())<=1)&&(temp->hasP())) {
			temp = temp->p;
		}
	}	
}

template <class generic>			/* Remove */
void Avl<generic>::remove (generic x) {
	Bst<generic>::remove (x);
}

template <class generic>
void Avl<generic>::rotateRR(BTN<generic> * rootNode){
	BTN<generic> * pivot = rootNode->r;
	// Put pivot->l to rootNode->r 
	if (pivot->hasL()) {
		rootNode->r = pivot->l;
		rootNode->r->p = rootNode;
	} else {
		rootNode->r = NULL;
	}
	// Make parent-child link
	if (rootNode->lChild()) {
		rootNode->p->l = pivot;
		pivot->p = rootNode->p;
	} else if (rootNode->rChild()) {
		rootNode->p->r = pivot;
		pivot->p = rootNode->p;
	} else {
		BT<generic>::m_root = pivot;
		pivot->p = NULL;
	}
	pivot->l = rootNode;
	rootNode->p = pivot;
}

template <class generic>
void Avl<generic>::rotateRL(BTN<generic> * rootNode){
	BTN<generic> * root1 = rootNode->r;
	BTN<generic> * pivot = rootNode->r->l;
	if (pivot->hasR()) {
		root1->l = pivot->r;
		root1->l->p = root1;
	} else {
		root1->l = NULL;
	}
	pivot->r = root1;
	root1->p = pivot;
	rotateRR(rootNode);
}

template <class generic>
void Avl<generic>::rotateLL(BTN<generic> * rootNode){
	BTN<generic> * pivot = rootNode->l;
	// Put pivot->r to rootNode->l 
	if (pivot->hasR()) {
		rootNode->l = pivot->r;
		rootNode->l->p = rootNode;
	} else {
		rootNode->l = NULL;
	}
	// Make parent-child link
	if (rootNode->lChild()) {
		rootNode->p->l = pivot;
		pivot->p = rootNode->p;
	} else if (rootNode->rChild()) {
		rootNode->p->r = pivot;
		pivot->p = rootNode->p;
	} else {
		BT<generic>::m_root = pivot;
		pivot->p = NULL;
	}
	pivot->r = rootNode;
	rootNode->p = pivot;
}

template <class generic>
void Avl<generic>::rotateLR(BTN<generic> * rootNode){
	BTN<generic> * root1 = rootNode->l;
	BTN<generic> * pivot = rootNode->l->r;
	if (pivot->hasL()) {
		root1->r = pivot->l;
		root1->r->p = root1;
	} else {
		root1->r = NULL;
	}
	pivot->l = root1;
	root1->p = pivot;
	rotateLL(rootNode);
}
//////////////////////////////////////////////////////////////////////
/// @file bst.h
/// @brief The header file for the binary search tree
//////////////////////////////////////////////////////////////////////

#ifndef BST_H
#define BST_H

#include "bt.h"
#include "btn.h"
#include "exception.h"

template <class generic>
class Bst : public BT<generic>
{
public:
	void insert (generic);
	void remove (generic);
	typedef BTPreorderIterator<generic> PreOrder;
	typedef BTInorderIterator<generic> InOrder;
	typedef BTPostorderIterator<generic> PostOrder;
	PreOrder pre_search (generic);
	InOrder in_search (generic);
	PostOrder post_search (generic);
	bool hasValue(generic);
	
protected:
    BTN<generic> * p_search (generic); //returns a pointer to the node containing the found data
};

#include "bst.hpp"
#endif
//////////////////////////////////////////////////////////////////////
/// @file bst.hpp
/// @brief Function implementation for the binary search tree
//////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;

template <class generic>								/* Insert Function */
void Bst<generic>::insert (generic x){
	if (BT<generic>::empty()) {		// Empty case
		BT<generic>::m_root = new BTN<generic>;
		BT<generic>::m_root->data=new generic;
		*(BT<generic>::m_root->data)=x;
		BT<generic>::m_size++;
	} else {	// Otherwise:
		BTN<generic> * temp = BT<generic>::m_root; // Prepare temp
		bool Loop = true;
		while (Loop) {	// Find correct position
			if ((*(temp->data)==x)||((temp->l==NULL)&&(temp->r==NULL))) {	// End loop if correct position
				Loop=false;
			} else if (*(temp->data)<x) {
				if (temp->r==NULL) {
					Loop=false;	// End loop if correct position
				} else {
					temp=temp->r;	// Go right if inserted value is bigger
				}
			} else {
				if (temp->l==NULL) {
					Loop=false;	// End loop if correct position
				} else {
					temp=temp->l;	// Go left if inserted value is smaller
				}
			}
		}	// Finish Loop
		if (*(temp->data)>x) {	// If node should be left child
			temp->l = new BTN<generic>;
			temp->l->data = new generic;
			*(temp->l->data) = x;
			temp->l->p = temp;
			temp->l->l = NULL;
			temp->l->r = NULL;
			BT<generic>::m_size++;
		} else if (*(temp->data)<x) {	// If node should be right child
			temp->r = new BTN<generic>;
			temp->r->data = new generic;
			*(temp->r->data) = x;
			temp->r->p = temp;
			temp->r->l = NULL;
			temp->r->r = NULL;
			BT<generic>::m_size++;
		}	// No else: Do not want repeats.
	}							
}

template <class generic>					/* Remove Function */
void Bst<generic>::remove (generic x){
	if (BT<generic>::empty()) {
		throw Exception(CONTAINER_EMPTY,"The container is empty.");	// Can't remove if empty
	}
	BTN<generic> * temp1 = BT<generic>::m_root;	// Set up temp1
	bool contLoop=true;
	while (contLoop) {	// Find x
		if ((*(temp1->data)==x)) {	// Found x
			contLoop=false;
		} else if (*(temp1->data)>x) {
			if (temp1->l==NULL) {
				contLoop==false;	// x not in tree
			} else {
				temp1=temp1->l;	// search left
			}
		} else if (*(temp1->data)<x) {
			if (temp1->r==NULL) {
				contLoop==false;	// x not in tree
			} else {
				temp1=temp1->r;	// search right
			}
		}
	}
	if (*(temp1->data)!=x) {
		throw Exception(OUT_OF_BOUNDS,"The container does not contain this value.");	// x not in tree
	}
	if ((temp1->l == NULL)&&(temp1->r == NULL)) {	// temp1 is a leaf node
		if(temp1->p==NULL){
			BT<generic>::m_root=NULL;
		} else if (temp1==temp1->p->r) {
			temp1->p->r = NULL;
		} else {
			temp1->p->l = NULL;
		}
		delete temp1;
	} else if (temp1->l==NULL) {	// temp1 has no left
		temp1->r->p = temp1->p;
		if (temp1->p==NULL){
			BT<generic>::m_root=temp1->r;
		} else if (temp1->rChild()) {
			temp1->p->r = temp1->r;
		} else {
			temp1->p->l = temp1->r;
		}
		delete temp1;
	} else {
		BTN<generic> * temp2 = temp1->l;	// Further cases require temp2
		while (temp2->r!=NULL) {
			temp2=temp2->r;		// Find temp2 location
		}
		*(temp1->data) = *(temp2->data);	// Swap temp2 & temp1
		if (temp2->l==NULL) {	// temp2 has no left
			if (temp2 == temp2->p->r) {
				temp2->p->r = NULL;
			} else {
				temp2->p->l = NULL;
			}
		} else {				// temp2 has a left
			if (temp2==temp2->p->l) {
				temp2->p->l = temp2->l;
			} else {
				temp2->p->r = temp2->l;
			}
			temp2->l->p = temp2->p;
		}
		delete temp2;	// delete temp2
	}
	BT<generic>::m_size--;	// decrease size
}

template <class generic>					/* Pre Order Search Function */
BTPreorderIterator<generic> Bst<generic>::pre_search(generic x){
	if (!hasValue(x)) {
		throw Exception(OUT_OF_BOUNDS,"The container does not contain this value.");	// x not in tree
	}
	return PreOrder(p_search(x));	// Much simpler than I'd thought
}

template <class generic>					/* In Order Search Function */
BTInorderIterator<generic> Bst<generic>::in_search(generic x){
	if (!hasValue(x)) {
		throw Exception(OUT_OF_BOUNDS,"The container does not contain this value.");	// x not in tree
	}	
	return InOrder(p_search(x));	// I thought I had to make 3 search functions
}

template <class generic>					/* Post Order Search Function */
BTPostorderIterator<generic> Bst<generic>::post_search(generic x){
	if (!hasValue(x)) {
		throw Exception(OUT_OF_BOUNDS,"The container does not contain this value.");	// x not in tree
	}
	return PostOrder(p_search(x));	// Turns out, I only needed 1 to plug in
}

template <class generic>					/* Has Value Function*/
bool Bst<generic>::hasValue(generic x){
	return p_search(x)!=NULL;		// True if x is in tree
}

template <class generic>								/* Search Function */
BTN<generic> * Bst<generic>::p_search (generic x) {	
	BTN<generic> * temp = BT<generic>::m_root;
	if (BT<generic>::empty()) {
		return NULL;	// Won't find anything if tree is empty
	}
	bool Loop = true;
	while (Loop) {	// Start looking for x
		if ((*(temp->data)==x)||((temp->l==NULL)&&(temp->r==NULL))) {
			Loop=false;	// Found x or in leaf node
		} else if (*(temp->data)<x) {	// Go right if temp is smaller
			if (temp->hasR()) {
				temp=temp->r;
			} else {
				Loop=false;
			}
		} else {	// Go left if temp is bigger
			if (temp->hasL()) {
				temp=temp->l;					
			} else {
				Loop=false;
			}
		}
	}	// Finish loop
	if (*(temp->data)==x) {	// If x is found, return temp.  And rejoice.
		return temp;
	} else {
		return NULL;	// Or else you recieve a NULL
	}
}
//////////////////////////////////////////////////////////////////////
/// @file bt.hpp
/// @brief Header file for the avl class
//////////////////////////////////////////////////////////////////////

#ifndef AVL_H
#define AVL_H

#include "bt.h"
#include "btn.h"
#include "bst.h"
template <class generic>
class Avl : public Bst<generic>
{
public:
	Avl();
	~Avl();
    void insert( generic x );
    void remove( generic x );
protected:
	void rotateRR(BTN<generic> * rootNode);
	void rotateRL(BTN<generic> * rootNode);
	void rotateLL(BTN<generic> * rootNode);
	void rotateLR(BTN<generic> * rootNode);
};

#include "avl.hpp"
#endif
//////////////////////////////////////////////////////////////////////
/// @file bt.hpp
/// @brief Function implementation for the avl class
//////////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;

template <class generic>			/* Constructor */
Avl<generic>::Avl () {
	BT<generic>::m_root = NULL;
	BT<generic>::m_size = 0;
}

template <class generic>			/* Destructor */
Avl<generic>::~Avl () {
}

template <class generic>			/* Insert */
void Avl<generic>::insert (generic x) {
	if (Bst<generic>::hasValue(x)) {
		return;
	}
	Bst<generic>::insert (x);
	BTN<generic> * temp = Bst<generic>::p_search (x);
	while (abs(BT<generic>::m_root->balance())>1) {
		if (temp->balance() == 2) {
			int lBalance = temp->l->balance();
			if (lBalance == -1) {
				rotateLL(temp);
			} else {
				rotateLR(temp);
			}
		} else if (temp->balance() == -2) {
			int rBalance = temp->r->balance();
			if (rBalance == 1) {
				rotateRR(temp);
			} else {
				rotateRL(temp);
			}
		}
		if ((abs(temp->balance())<=1)&&(temp->hasP())) {
			temp = temp->p;
		}
	}	
}

template <class generic>			/* Remove */
void Avl<generic>::remove (generic x) {
	Bst<generic>::remove (x);
}

template <class generic>
void Avl<generic>::rotateRR(BTN<generic> * rootNode){
	BTN<generic> * pivot = rootNode->r;
	// Put pivot->l to rootNode->r 
	if (pivot->hasL()) {
		rootNode->r = pivot->l;
		rootNode->r->p = rootNode;
	} else {
		rootNode->r = NULL;
	}
	// Make parent-child link
	if (rootNode->lChild()) {
		rootNode->p->l = pivot;
		pivot->p = rootNode->p;
	} else if (rootNode->rChild()) {
		rootNode->p->r = pivot;
		pivot->p = rootNode->p;
	} else {
		BT<generic>::m_root = pivot;
		pivot->p = NULL;
	}
	pivot->l = rootNode;
	rootNode->p = pivot;
}

template <class generic>
void Avl<generic>::rotateRL(BTN<generic> * rootNode){
	BTN<generic> * root1 = rootNode->r;
	BTN<generic> * pivot = rootNode->r->l;
	if (pivot->hasR()) {
		root1->l = pivot->r;
		root1->l->p = root1;
	} else {
		root1->l = NULL;
	}
	pivot->r = root1;
	root1->p = pivot;
	rotateRR(rootNode);
}

template <class generic>
void Avl<generic>::rotateLL(BTN<generic> * rootNode){
	BTN<generic> * pivot = rootNode->l;
	// Put pivot->r to rootNode->l 
	if (pivot->hasR()) {
		rootNode->l = pivot->r;
		rootNode->l->p = rootNode;
	} else {
		rootNode->l = NULL;
	}
	// Make parent-child link
	if (rootNode->lChild()) {
		rootNode->p->l = pivot;
		pivot->p = rootNode->p;
	} else if (rootNode->rChild()) {
		rootNode->p->r = pivot;
		pivot->p = rootNode->p;
	} else {
		BT<generic>::m_root = pivot;
		pivot->p = NULL;
	}
	pivot->r = rootNode;
	rootNode->p = pivot;
}

template <class generic>
void Avl<generic>::rotateLR(BTN<generic> * rootNode){
	BTN<generic> * root1 = rootNode->l;
	BTN<generic> * pivot = rootNode->l->r;
	if (pivot->hasL()) {
		root1->r = pivot->l;
		root1->r->p = root1;
	} else {
		root1->r = NULL;
	}
	pivot->l = root1;
	root1->p = pivot;
	rotateLL(rootNode);
}//////////////////////////////////////////////////////////////////////
/// @file test_avl.hpp
/// @brief Header file for the avl test
//////////////////////////////////////////////////////////////////////

#ifndef TEST_AVL_H
#define TEST_AVL_H

#include <cppunit/extensions/HelperMacros.h>
#include <cppunit/config/SourcePrefix.h>

#include "avl.h"
#include "exception.h"

class Test_avl : public CPPUNIT_NS::TestFixture
{
private:
    CPPUNIT_TEST_SUITE (Test_avl);
	CPPUNIT_TEST (test_insert);
	CPPUNIT_TEST (test_remove);
	CPPUNIT_TEST_SUITE_END ();
protected:
	void test_insert ();
	void test_remove ();
};

#endif

//////////////////////////////////////////////////////////////////////
/// @file test_avl.cpp
/// @brief The implementation file for the avl test
//////////////////////////////////////////////////////////////////////

#include "test_avl.h"
#include <ctime>
#include <iostream>
using namespace std;

CPPUNIT_TEST_SUITE_REGISTRATION (Test_avl);

void Test_avl::test_insert () {								/* Test Insert Function */
	Avl<int> a;	
	a.insert(1);
	srand(time(NULL));
	while (a.size()<10) {
		int i = rand()%10+1;
		a.insert(i);
	}
}

void Test_avl::test_remove () {								/* Test Remove Function */
}
//////////////////////////////////////////////////////////////////////
/// @file btn.h
/// @author Ted Gardner, CS 153 Section 1A
/// @brief The header file for the binary tree node
//////////////////////////////////////////////////////////////////////

#ifndef BTN_H
#define BTN_H

#include "bt.h"

template <class generic>
struct BTN
{
	BTN();
	~BTN();
    BTN * p;
    BTN * l;
    BTN * r;
	generic * data;
	bool hasL();
	bool hasR();
	bool hasP();
	bool hasData();
	bool lChild();
	bool rChild();
	int balance();
protected:
	int nodeDepth(BTN<generic> *);
};

#include "btn.hpp"
#endif
//////////////////////////////////////////////////////////////////////
/// @file btn.h
/// @author Ted Gardner, CS 153 Section 1A
/// @brief The function implementation file for the binary tree node
//////////////////////////////////////////////////////////////////////

template <class generic>			/* Constructor */
BTN<generic>::BTN () {
	l = NULL;							//     Initializes the node
	r = NULL;							// to have all its node
	p = NULL;							// pointers set to NULL.
}

template <class generic>			/* Destructor */
BTN<generic>::~BTN () {
	if (hasL()) {						//     Alright.  Segfault
		if (l->p==this) {				// after segfault, I couldn't
			delete l;					// figure out what was wrong.
		}								// Then I realized that I was
	}									// deleting the children during
	if (hasR()) {						// the remove function, where they
		if (r->p==this) {				// had a different parent (not this
			delete r;					// node).  Therefore, if their
		}								// child is still connected
	}									// (as in clear or destructor),
	if (hasData()) {					// the children will be deleted.
		delete data;					// Recursively.
	}
}

template <class generic>			/* Has Left Child */
bool BTN<generic>::hasL(){
	return l != NULL;					//     Returns "true" if the l
}										// pointer isn't NULL.

template <class generic>			/* Has Right Child */
bool BTN<generic>::hasR(){
	return r != NULL;					//     Returns "true" if the r
}										// pointer isn't NULL.

template <class generic>			/* Has Parent Node */
bool BTN<generic>::hasP(){
	return p != NULL;					//     Returns "true" if the p
}										// pointer isn't NULL.

template <class generic>			/* Has Data */
bool BTN<generic>::hasData(){
	return data != NULL;				//     Returns "true" if the
}										// data pointer isn't NULL.

template <class generic>			/* Is Parent's Left Child */
bool BTN<generic>::lChild(){
	if (hasP()) {						//     Returns "true" if the
		return p->l == this;			// parent's left pointer points
	}									// to the current node. If not,
	return false;						// or if there is no parent,
}										// returns "false".

template <class generic>			/* Is Parent's Right Child */
bool BTN<generic>::rChild(){
	if (hasP()) {						//     Returns "true" if the
		return p->r == this;			// parent's right pointer points
	}									// to the current node.  If not,
	return false;						// or if there is no parent,
}										// returns "false".

template<class generic>
int BTN<generic>::balance(){
	int right = 0;
	int left = 0;
	if(hasL()){
		left = nodeDepth(l);
	}
	if (hasR()) {
		right = nodeDepth(r);
	}
	return right-left;
}

template<class generic>
int BTN<generic>::nodeDepth(BTN<generic> * curNode) {
	if (curNode == NULL){
        return 0;
	} else {
		return max(nodeDepth(curNode->l), nodeDepth(curNode->r)) + 1;
	}
}
c++
1 Contributor
0 Replies
41 Views
Be the first to reply
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.