AVL Tree crashes on remove

This is a discussion on AVL Tree crashes on remove within the C++ Programming forums, part of the General Programming Boards category; Hello, I am trying to program a simple AVL Tree, but it crashes when removing in some cases, I am ...

  1. #1
    Registered User
    Join Date
    Feb 2012
    Posts
    1

    AVL Tree crashes on remove

    Hello, I am trying to program a simple AVL Tree, but it crashes when removing in some cases, I am pretty sure the problem is with remove() not balancedup(), here is my whole code.

    Code:
    #include <iostream>
    #include "BalancedTree.h"
    
    
    using namespace std;
    
    
    Node::Node()
    {
        left = NULL;
        right = NULL;
        height = 0;
    }
    
    
    Node::Node(int input)
    {
        data = input;
        left = NULL;
        right = NULL;
        height = 0;
    }
    
    
    Node::~Node()
    {
      if (left != NULL)
        delete left;
      if (right != NULL)
        delete right; 
    }
    
    
    AVLTree::AVLTree()
    {
        root = NULL;
    }
    
    
    AVLTree::~AVLTree()
    {
        delete root;
    }
    
    
    void AVLTree::balanceup(Node*& p)
    {
        if ((bsheight(p->left) - bsheight(p->right))==2)
        {
            if ((bsheight(p->left->left) - bsheight(p->left->right)) == 1)
                p = srl(p);
            if ((bsheight(p->left->right) - bsheight(p->left->left)) == 1)
                p = drl(p);
            if ((bsheight(p->left->left) - bsheight(p->left->right)) == 0)
                p = srl(p);
        }
        else if ((bsheight(p->right) - bsheight(p->left))==2)
        {
            if ((bsheight(p->right->left) - bsheight(p->right->right)) == 1)
                p = drr(p);
            if ((bsheight(p->right->right) - bsheight(p->right->left)) == 1)
                p = srr(p);
            if ((bsheight(p->right->left) - bsheight(p->right->right)) == 0)
                p = srr(p);
        }
        else if ((bsheight(p->left) - bsheight(p->right))==1)
            return;
        else if ((bsheight(p->right) - bsheight(p->left))==1)
            return;
        int m,n,d;
        m=bsheight(p->left);
        n=bsheight(p->right);
        d=max(m,n);
        p->height = d + 1;
        if (p->left != NULL)
        {
            m=bsheight(p->left->left);
            n=bsheight(p->left->right);
            d=max(m,n);
            p->left->height = d + 1;
        }
        if (p->right != NULL)
        {
            m=bsheight(p->right->left);
            n=bsheight(p->right->right);
            d=max(m,n);
            p->right->height = d + 1;
        }
    }
    void AVLTree::balance(Node*& p)
    {
        if ((bsheight(p->left) - bsheight(p->right))==2)
        {
            if ((bsheight(p->left->left) - bsheight(p->left->right)) == 1)
                p = srl(p);
            if ((bsheight(p->left->right) - bsheight(p->left->left)) == 1)
                p = drl(p);
        }
        else if ((bsheight(p->right) - bsheight(p->left))==2)
        {
            if ((bsheight(p->right->left) - bsheight(p->right->right)) == 1)
                p = drr(p);
            if ((bsheight(p->right->right) - bsheight(p->right->left)) == 1)
                p = srr(p);
        }
        int m,n,d;
        m=bsheight(p->left);
        n=bsheight(p->right);
        d=max(m,n);
        p->height = d + 1;
        if (p->left != NULL)
        {
            m=bsheight(p->left->left);
            n=bsheight(p->left->right);
            d=max(m,n);
            p->left->height = d + 1;
        }
        if (p->right != NULL)
        {
            m=bsheight(p->right->left);
            n=bsheight(p->right->right);
            d=max(m,n);
            p->right->height = d + 1;
        }
    }
    
    
    void AVLTree::insert(int x)
    {
        insert(x, root);
    }
    
    
    void AVLTree::insert(int x,Node*& p)
    {
        if (root == NULL)
        {
            root = new Node(x);
        }
        else if (p == NULL)
        {
            p = new Node(x);
        }
        else
        {
            if (x<p->data)
            {
                if (p->left == NULL)
                    p->left = new Node(x);
                else
                    insert(x,p->left);
                balance(p);
            }
            else if (x>p->data)
            {
                if (p->right == NULL)
                    p->right = new Node(x);
                else
                    insert(x,p->right);
                balance(p);
            }
        }
    }
    
    
    int AVLTree::next(int x)
    {
        int out = next(x, -1, root);
        return out;
    }
    
    
    int AVLTree::next(int x,int max, Node*& p)
    {
        if (p==NULL)
        {
            return max;
        }
        else
        {
            if (x == p->data)
                return p->data;
            else if (x < p->data)
            {
                if (max == -1)
                    next (x, p->data, p->left);
                else if(max > p->data)
                    next(x, p->data, p->left);
                else if (max < p ->data)
                    next(x, max, p->left);
            }
            else if (x > p->data)
                next(x, max, p->right);
        }
    }
    
    
    Node*& AVLTree::getMax(Node*& curr){
        if (curr -> right != NULL)
            return getMax(curr -> right);
        else
            return curr;
    }
    
    
    void AVLTree::remove(int x)
    {
        remove(x, root);
    }
    
    
    void AVLTree::remove(int x,Node*& p)
    {
        Node* d;
        if (p==NULL)
        {
            cout<<"Sorry! data not found\n"<<endl;
        }
        else if ( x < p->data)
        {
            remove(x,p->left);
            balanceup(p);
        }
        else if (x > p->data)
        {
            remove(x,p->right);
            balanceup(p);
        }
        else if ((p->left == NULL) && (p->right == NULL))
        {
            d=p;
            p=NULL;
            delete d;
        }
        else if (p->left == NULL)
        {
            d=p;
            p=p->right;
            delete d;
            balanceup(p);
        }
        else if (p->right == NULL)
        {
            d=p;
            p=p->left;
            delete d;
            balanceup(p);
        }
        else
        {    
            Node*& m = getMax(p->left);
            p->data = m->data;
            remove(m->data, m);
            balanceup(p);
        }
    }
    
    
    void AVLTree::preorder()
    {
        preorder(root);
    }
    
    
    void AVLTree::preorder(Node* p)
    {
        if (p!=NULL)
        {
            cout<<p->data<<"\t";
            preorder(p->left);
            preorder(p->right);
        }
    }
    
    
    void AVLTree::print()
    {
        inorder(root);
    }
    
    
    void AVLTree::inorder()
    {
        inorder(root);
    }
    
    
    void AVLTree::inorder(Node* p)
    {
        if (p!=NULL)
        {
            inorder(p->left);
            cout<<p->data<<"\t";
            inorder(p->right);
        }
    }
    
    
    void AVLTree::postorder()
    {
        postorder(root);
    }
    
    
    void AVLTree::postorder(Node* p)
    {
        if (p!=NULL)
        {
            postorder(p->left);
            postorder(p->right);
            cout<<p->data<<"\t";
        }
    }
    
    
    int AVLTree::max(int value1, int value2)
    {
        return ((value1 > value2) ? value1 : value2);
    }
    
    
    int AVLTree::bsheight()
    {
        bsheight(root);
    }
    
    
    int AVLTree::bsheight(Node* p)
    {
        int t;
        if (p == NULL)
        {
            return -1;
        }
        else
        {
            t = p->height;
            return t;
        }
    }
    
    
    Node* AVLTree:: srl(Node*& p1)
    {
        Node* p2;
        p2 = p1->left;
        p1->left = p2->right;
        p2->right = p1;
        p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
        p2->height = max(bsheight(p2->left),p1->height) + 1;
        return p2;
    }
    
    
    Node* AVLTree:: srr(Node*& p1)
    {
        Node* p2;
        p2 = p1->right;
        p1->right = p2->left;
        p2->left = p1;
        p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
        p2->height = max(p1->height,bsheight(p2->right)) + 1;
        return p2;
    }
    
    
    Node* AVLTree:: drl(Node*& p1)
    {
        p1->left=srr(p1->left);
        return srl(p1);
    }
    
    
    Node* AVLTree::drr(Node*& p1)
    {
        p1->right = srl(p1->right);
        return srr(p1);
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,293
    Welcome to the forum. It looks like there is a lot we can help you with there.

    First off, I like to do a bit of a code review, so here are my observations:

    Best practice is to use constructor initialisation lists, which you are currently not doing. Have a search on the web as to what that is. You can also combine constructors using a default parameter. Basically your only constructor could look like this:
    Code:
    Node::Node(int input = 0) :
        data(input), left(NULL), right(NULL), height(0) {}
    Your destructor performs unnecessary NULL checks. 'delete' already checks for NULL pointers and as such it is always safe to just do: delete left; delete right;

    AVLTree: Use a constructor initialisation list again. Your destructor is good though.

    balanceup and balance: Comparing my own AVL tree implementation to yours, I can tell you straight away that these funtions are too complicated. There are definitely not this many cases that need to be considered. Once you've noticed that the heights differ by two, then you must perform a rotate. Right now you have several if-statements which when true perform a rotate, but what should happen if none of those were true? If that's not possible, then the last one can just be an else. See if you can find other ways of simplifying it.

    insert: In this bit of code:
    Code:
                if (p->left == NULL)
                    p->left = new Node(x);
                else
                    insert(x,p->left);
    The only line you need is the last line. Just let the recursive call do its work and create the node for you.

    getMax: I set it as a small challenge for you to write this one non-recursively using a loop instead.

    preorder, inorder, print, postorder, bsheight: Best practice is to mark member functions which read but do not modify any member variables as const. You do this by putting const at the end of the function signature. E.g.
    Code:
    void AVLTree::postorder() const
    If you continue to program in C++ then you will sooner of later come across a case where it is not only best-practice, but where it wont actually work without doing it.

    inorder: It doesn't look like you use the zero-parameter version of this function. I suggest you remove it.

    max: Any reason not to use std::max? I hope you marked this function as static.

    Okay start with that stuff and see where that gets you. My final advice for now would be to isolate exactly what case it doesn't work in. I.e. what exact sequence of actions causes the bug.
    You would also benefit from a tree-verify routine. That's a function you can call at any time which tells you for certain that the tree is well structured, correctly ordered and correctly-balanced. Call that before and after each insert or remove etc to help narrow down the problem.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Remove a specific char and remove multiple spaces
    By stam in forum C++ Programming
    Replies: 9
    Last Post: 12-18-2010, 06:50 AM
  2. Replies: 2
    Last Post: 08-01-2007, 01:08 PM
  3. display tree data in binary tree format
    By xddxogm3 in forum C++ Programming
    Replies: 4
    Last Post: 12-10-2003, 11:47 PM
  4. Replies: 5
    Last Post: 05-23-2003, 01:11 PM
  5. binary tree: adding first node works than crashes
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2002, 10:49 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21