c++ Issue with AVL Binary tree rotations and deleting tree

Question

I am working on an AVL Binary tree implementation and I have most of the code working except for my rotations and my deletion functions. I have tried different methods of implementation but I still cant figure out what I am doing wrong. If anyone could help me with a solution it would be greatly appreciated. If I comment out the balancing function the code will work as needed and insert all the words from an imported text file but the moment I attempt to balance the node the code blows up. And for some reason there is a problem with my:

delete node;

section of my code but I am not really sure why that would be an issue. There is no problem with the recursion going through the tree but as soon as it hits the delete node portion it has a problem, this makes no sense to me...

header:

#ifndef AVLBINARYTREE_H
#define AVLBINARYTREE_H
#include <iostream>
#include <string>
using namespace std;

class LinkedBinaryTree {
private:
    struct Node {
        string word;
        Node* left;
        Node* right;
        Node* parent;
        int wordCount;
        int height;
        Node() : word(), left(NULL), right(NULL), parent(NULL), wordCount(1), height(0) {}
        Node(string s, Node* l, Node* r, Node* p) {
            word = s;
            left = NULL;
            right = NULL;
            parent = p;
            wordCount = 1;
            height = 0;
        }
    };

    Node* _root;

public:
    LinkedBinaryTree();
    ~LinkedBinaryTree();
    void destroyTree();
    void destroyTree(Node* node);
    void insert(string word);
    void display(Node* ptr, int level);
    Node* root();
    void inOrder(Node* node);
    int avlNum(Node* node);
    int getNumWords();

    void insertNode(Node* node, string word);
    int height(Node* node);
    int bfactor(Node* node);
    void fixHeight(Node* node);
    void balance(Node* node);
    void rightRotate(Node* node);
    void leftRotate(Node* node);
    void rightLeftRotate(Node* node);
    void leftRightRotate(Node* node);

    int n;
};
#endif

.cpp:

#include "AVLBinaryTree.h"
#include <algorithm>

void LinkedBinaryTree::inOrder(Node* node) {

    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->wordCount << " " << node->word << endl;
    inOrder(node->right);
}

void LinkedBinaryTree::rightRotate(Node* node) {

    Node* temp;
    temp = node->left;
    node->left = temp->right;
    //node->left->parent = node;
    temp->parent = node->parent;
    temp->right = node;
    node->parent = temp;
    node = temp;
    if (temp->parent == NULL) {
        _root = node;
    }
    fixHeight(node);
    fixHeight(node->right);
    fixHeight(node->left);
}

void LinkedBinaryTree::leftRotate(Node* node) {

    Node* temp;
    temp = node->right;
    node->right = temp->left;
    temp->parent = node->parent;
    temp->left = node;
    node->parent = temp;
    node = temp;
    if (temp->parent == NULL) {
        _root = node;
    }
    fixHeight(node);
    fixHeight(node->right);
    fixHeight(node->left);
}

void LinkedBinaryTree::rightLeftRotate(Node* node) {

    rightRotate(node->left);
    leftRotate(node);
}

void LinkedBinaryTree::leftRightRotate(Node* node) {

    leftRotate(node->right);
    rightRotate(node);
}

int LinkedBinaryTree::height(Node* node) {

    int h = 0;

    if (node != NULL) {
        h = node->height;
    }
    return h;
}

int LinkedBinaryTree::bfactor(Node* node) {

    return height(node->right) - height(node->left);
}

void LinkedBinaryTree::fixHeight(Node* node) {

    int hl = height(node->left);
    int hr = height(node->right);
    node->height = (hl > hr ? hl : hr) + 1;
}

int LinkedBinaryTree::avlNum(Node* node) {

    int leftH = height(node->left);
    int rightH = height(node->right);
    int avlNum = rightH - leftH;
    return avlNum;
}

LinkedBinaryTree::LinkedBinaryTree() {

    _root = NULL;
}

LinkedBinaryTree::~LinkedBinaryTree() {

    destroyTree();
}
void LinkedBinaryTree::destroyTree() {

    destroyTree(_root);
}
//**********************************************************
// destroyTree is called by the destructor. It deletes  
// all nodes in the tree.                                  
//**********************************************************
void LinkedBinaryTree::destroyTree(Node* node) {

    if (node != NULL) {
        if (node->left != NULL)
            destroyTree(node->left);
        if (node->right != NULL)
            destroyTree(node->right);
        delete node;
    }
}

void LinkedBinaryTree::insertNode(Node* node, string word) {

    if (word < node->word) {
        if (node->left != NULL)
            insertNode(node->left, word);
        else {
            node->left = new Node(word, NULL, NULL, node);
            n++;
            fixHeight(node->left);
        }
    }
    else if (word > node->word) {

        if (node->right != NULL)
            insertNode(node->right, word);
        else {
            node->right = new Node(word, NULL, NULL, node);
            n++;
            fixHeight(node->right);
        }
    }
    else if (word == node->word) {
        node->wordCount++;
    }
    balance(node);
}

void LinkedBinaryTree::insert(string word) {

    if (_root == NULL) {
        _root = new Node(word, NULL, NULL, NULL);
        n++;
    }
    else {
        insertNode(_root, word);
    }
}
void LinkedBinaryTree::display(Node* ptr, int level) {

    int i;
    if (ptr != NULL)
    {
        display(ptr->right, level + 1);
        printf("\n");
        if (ptr == _root)
            cout << "Root -> ";
        for (i = 0; i < level && ptr != _root; i++)
            cout << "        ";
        cout << ptr->word;
        display(ptr->left, level + 1);
    }
}

LinkedBinaryTree::Node * LinkedBinaryTree::root() {

    return _root;
}

void LinkedBinaryTree::balance(Node* node) {

    fixHeight(node);
    if (bfactor(node) == 2) {
        if (bfactor(node->right) < 0)
            rightRotate(node->right);
        else
            leftRotate(node);
    }
    if (bfactor(node) == -2) {
        if (bfactor(node->left) > 0)
            leftRotate(node->left);
        else
            rightRotate(node);
    }
}

int LinkedBinaryTree::getNumWords() {

    return n;
}

main:

#include "AVLBinaryTree.h"
#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <vector>
#include <functional>

int main(int argv, char *argc[]) {

    LinkedBinaryTree t;
    string word("Test."), lastword("");

    for (int i = 0; i < argv; i++)
        cout << argc[i] << endl;

    if (argv < 2) {
        cerr << "No input file specified" << endl;
        system("pause");
        exit(1);
    }
    for (int count = 1; count < argv; count++)
    {
        ifstream input(argc[count]);
        if (!input) {
            cerr << "Cannot open input file" << argc[count] << endl;
            system("pause");
            exit(1);
        }
        while (input >> word)
        {
            transform(word.begin(), word.end(), word.begin(), ::tolower);

            word.erase(remove_if(word.begin(), word.end(), ispunct));

            t.insert(word);
        }
    }

    t.inOrder(t.root());
    cout << endl;

    cout << "--------" << endl;
    cout << t.getNumWords() << "  " << "Total number of different words";
    cout << endl;


    /*t.insert("Yes");
    t.insert("No");
    t.insert("Maybe");
    t.insert("Hopefully");
    t.insert("Absolutely");

    t.display(t.root(), 1);

    cout << endl;
    cout << endl;

    t.inOrder(t.root());
    */

    system("PAUSE");

    t.~LinkedBinaryTree();

    return EXIT_SUCCESS;
}

thanks in advance!

Answer 1

The node = temp; lines in your rotate functions is changing the local value of the pointer that belongs to the function, and not the value stored in the tree. For example, when you call rightRotate(node->right), the value of node->right is the same after the call when it should be updated.

Possible solutions include either passing the node pointer into the rotate function as a reference (void LinkedBinaryTree::rightRotate(Node*& node)) so that the original value gets updated, or returning the updated value (Node *LinkedBinaryTree::rightRotate(Node* node)) and storing that appropriately.

Your balance function and the other rotate functions may be similarly afflicted.