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 ®istry
= 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;
}
}