Binary Tree Program not acting as it should...

[Lowest0ne]

It's generally frowned on (esp. by teachers) to move the data instead of change the node pointers (@line 210 for example).

When I have a "node" I don't put anything in the destructor, I make a recursive function to delete every node one at a time. Your destructors give you trouble @line 177 and 184. If target->right/left has child nodes, then you delete them too, losing whatever data was there.

@line 174:
if (target->left_child == NULL && target->right_child != NULL)
{
  //target->data = target->right_child->data;
  //delete target->right_child;
  //target->right_child = NULL;

  // Need to know the direction from parent
  Node* pDirection = target->data < parent->data ? parent->left : parent->right;

  // Connect parent and right_child

  pDirection->right_child = target->right_child;
  pDirection = target->right_child;  
  
  target->right_child->parent = target->parent;

  // target is not part of the tree, but it is still linking
  // If you change your destructor you don't have to do this 
  target->parent = NULL;
  target->right_child = NULL;
  target->left_child = NULL;

  // free memory
  delete target;
}

I know that doesn't totally answer your question, but I must go.

The simpilest way that I know to remove when there is both a left and right is to find the greatest node on the left side, and then bring that up to replace the target node.

[Catfish3]

D'oh! Forgot to update the parent node's children. Thank you LowestOne.

Well Merriak, I cannot guarantee that this code is 100% bug-free, but here you go. I hope it helps.

Although I have to say, the parent hint is probably cheating, I think a proper implementation shouldn't rely on such information.

#include <cstddef>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <ostream>

class BinarySearchTree
{
    struct Node
    {
        int data;
        Node *parent;
        Node *left_child;
        Node *right_child;

        explicit Node(int data, Node *parent = NULL):
            data(data),
            parent(parent),
            left_child(NULL),
            right_child(NULL)
        {
        }

        ~Node()
        {
            delete left_child;
            delete right_child;
        }
    };

public:

    BinarySearchTree():
        root(NULL),
        sz(0)
    {
        std::srand(std::time(NULL));
    }

    ~BinarySearchTree()
    {
        delete root;
    }

    bool empty() const
    {
        return sz == 0;
    }

    std::size_t size() const
    {
        return sz;
    }

    void insert(int nd) // nd = Node Data
    {
        if (root != NULL)
        {
            Node *temp = root;

            while (true)
                if (nd < temp->data)
                {
                    if (temp->left_child == NULL)
                    {
                        temp->left_child = new Node(nd, temp);
                        break;
                    }
                    else
                        temp = temp->left_child;
                }
                else
                if (nd > temp->data)
                {
                    if (temp->right_child == NULL)
                    {
                        temp->right_child = new Node(nd, temp);
                        break;
                    }
                    else
                        temp = temp->right_child;
                }
                else // nd == temp->data
                    return; // nothing to insert
        }
        else
            root = new Node(nd);

        ++sz;
    }

    void remove(int nd) // nd = Node Data
    {
        if (root == NULL)
            return;

        Node *target = root;
        bool found_nd = false;

        while (true)
            if (nd < target->data)
            {
                if (target->left_child != NULL)
                    target = target->left_child;
                else
                    break;
            }
            else
            if (nd > target->data)
            {
                if (target->right_child != NULL)
                    target = target->right_child;
                else
                    break;
            }
            else // nd == target->data
            {
                found_nd = true;
                break;
            }

        // target wasn't found, nothing to remove
        if (!found_nd)
            return;

        kill_node(target);
        --sz;
    }

    void display(std::ostream &os = std::clog) const
    {
        os << "BinarySearchTree @ " << this << ", size: " << sz << '\n';
        recursive_display_on(os, root);
    }

private:

    void recursive_display_on(std::ostream &os, const Node *n) const
    {
        if (n == NULL)
            return;

        recursive_display_on(os, n->left_child);
        os << n->data << ' ';
        recursive_display_on(os, n->right_child);
    }

    void kill_node(Node *target)
    {
        // according to Wikipedia, we must now deal with three cases:
        // (1) no children
        // (2) one child
        // (3) two children

        // case (1)
        if (target->left_child == NULL && target->right_child == NULL)
        {
            if (target->parent == NULL) // this can only be the root node
            {
                delete root;
                root = NULL;
                return;
            }
            else
            // determine if `target' is a left child, or a right child
            if (target->parent->data < target->data)
                target->parent->right_child = NULL;
            else
                target->parent->left_child = NULL;

            delete target;
        }
        else
        // case (2)
        if (target->left_child == NULL && target->right_child != NULL)
        {
            if (target->data > target->parent->data)
                target->parent->right_child = target->right_child;
            else
                target->parent->left_child = target->right_child;

            target->right_child->parent = target->parent;
            target->right_child = NULL;
            delete target;
        }
        else
        if (target->left_child != NULL && target->right_child == NULL)
        {
            if (target->data > target->parent->data)
                target->parent->right_child = target->left_child;
            else
                target->parent->left_child = target->left_child;

            target->left_child->parent = target->parent;
            target->left_child = NULL;
            delete target;
        }
        else
        // case (3)
        {
            // according to Wikipedia, we shouldn't be "consistent" in choosing
            // between in-order predecessor and in-order successor

            if (std::rand() % 2 == 0) // go for predecessor
            {
                Node *p = target->left_child;

                while (p->right_child != NULL)
                    p = p->right_child;

                target->data = p->data;
                kill_node(p);
            }
            else // go for successor
            {
                Node *s = target->right_child;

                while (s->left_child != NULL)
                    s = s->left_child;

                target->data = s->data;
                kill_node(s);
            }
        }
    }

    Node *root;
    std::size_t sz;
};

int main()
{
    BinarySearchTree bst;

    bst.remove(27);
    bst.insert(-1);
    bst.insert(-5);
    bst.insert(90);
    bst.insert(0);
    bst.insert(-90);
    bst.insert(25);
    bst.insert(2);
    bst.insert(2);
    bst.insert(2);
    bst.insert(23);
    bst.insert(24);
    bst.remove(-90);
    bst.remove(-1);
    bst.remove(-90);
    bst.remove(25);
    bst.insert(-3);

    bst.display();
}

[Merriak]

Thanks Catfish, you guys are awesome! :D

[Lowest0ne]

Well Merriak, I cannot guarantee that this code is 100% bug-free, but here you go

I think I made a mistake, note line 13 in my previous post

I don't think the killNode works when there is both left and right. killNode only deletes target, which in the case of the recursive call, isn't the "real" target.

I have to work on trees myself, never got the rotations quite right. I'm pretty sure there is never a "while" like we see @line 208 and 218. Instead, there is a recursive function call that magically makes everything balanced.

Maybe this explains a little about what I'm thinking? Tree rotations.
http://en.wikipedia.org/wiki/Tree_rotation

[Catfish3]

I don't think the killNode works when there is both left and right. killNode only deletes target, which in the case of the recursive call, isn't the "real" target.

I don't understand what you mean. I just followed Wikipedia's instructions.

Could you provide some sample input for the removal to fail?

I'm pretty sure there is never a "while" like we see @line 208 and 218. Instead, there is a recursive function call that magically makes everything balanced.

Those two while() loops have the purpose of finding the in-order successor or predecessor. Again, if you could give some sample input to show the failure... because honestly, I don't see the problem.

[Lowest0ne]

Looking at it again, the reason I thought it wouldn't work is wrong.

However, as I said before, you aren't "supposed" to move the data of the node, only change the links. The fact that a tree can be altered without copying/moving data is one of the strengths it has over a sequential data structure (an array).

For every case of removal/balancing, there are only four cases that need be considered. These cases can be found in the link I gave, and using them correctly will keep your tree in good condition.