Deleting a node from binary search tree

earachefl · #1 25-Jun-2006, 01:49

OK, general ? here. If one is deleting a node from a binary search tree that is within the tree and has lots of descendants, say the node with value 40 from this example:

CPP / C++ / C Code:

                                    50
                                   /  \
                                  /    \
                                40      60
                                / \     / \
                               /   \
                              /     \
                             /       \
                           30         45
                           / \        / \
                          /   \      /   \
                        20   35     41    46

my first instinct when figuring out how to delete the node and keep its children in order is to take the remaining nodes in order, put them in a temporary stack, and then rebuild the tree starting from the parent of the deleted node, which would end up like a linked list on that side of the tree;

CPP / C++ / C Code:

I was wondering if there's a more efficient way of accomplishing this goal. It just seems that removing a node in the middle of the tree really opens up a can of worms. Also, I would think that searching the tree would become more efficient after having been restructured in this way.

Hope I've made myself clear.

Blake · #2 25-Jun-2006, 07:57

When you delete a node, if the left subtree is null, replace the node you're deleting with the root of the right subtree. If the left subtree is not null, replace the node with largest element of the left subtree. You can to do it by moving few pointers around. There's no need for temporary stacks or rebuilding the tree.

earachefl · #3 27-Jun-2006, 23:00

I've love it if someone would critique my "dele" function. I'm not sure I've covered all the possible scenarios, and I feel like I've really fumbled my way through this. I find it hard to visualize the way the pointers get shuffled around when deleting a node with two subtrees. Here's the header:

CPP / C++ / C Code:

/*
 *  binaryTree.h
 */

#include <iostream>
#include <cstdlib>
using namespace std;

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

template<class treeElement>
class binaryTree
{
    public:
        binaryTree()
        {
            root = NULL;
        }
        
        bool insert (treeElement& el)
        {
            return insert (root, el);
        }
     
        bool dele (treeElement& el)
        {
            return dele (root, el);
        }

        void display () const
        {
            if (root == NULL)
                cout << "No elements to display" << endl;
            else
                display (root);
        }

///////////////////////////////////////////////////////////////////////////////////
    private:
        struct treeNode
        {
            treeElement data;
            treeNode *left;
            treeNode *right;
        };
        treeNode *root;
        
        //Private member functions
        bool insert (treeNode*& aRoot, treeElement& el)
        {
            if (aRoot == NULL) {
                aRoot = new treeNode;
                aRoot->left = NULL;
                aRoot->right = NULL;
                aRoot->data = el;
                //cout << aRoot->data << endl;
                return true;
            }
            else if (el == aRoot->data) {
                cout << "Duplicate entry - not inserted" << endl;
                return false;
            }
            else if (el < aRoot->data)
                return insert (aRoot->left, el);
            else
                return insert (aRoot->right, el);
        }
        
         bool dele (treeNode*& aRoot, treeElement& el)
        {
            treeNode *goner, *gonerL, *gonerR, *replacement, *oldRoot, *replacementL;
            oldRoot = aRoot;
            replacementL = NULL;
            
            //stopping condition 1
            if (aRoot == NULL) {
                cerr << "No elements to delete" << endl;
                return false;
            }
            //stopping condition 2
            else if (aRoot->data == el) { //data found - replace
                //leaf node
                if (aRoot->left == NULL && aRoot->right == NULL) { 
                    cout << "Leaf node found " << endl;
                    goner = aRoot;
                    aRoot = NULL;
                    delete goner;
                    return true;
                }
                //node has right branch only
                else if (aRoot->left == NULL) { 
                    cout << "Node with right branch found" << endl;
                    goner = aRoot;
                    aRoot = aRoot->right;
                    delete goner;
                    return true;
                }
                //node has left branch only
                else if (aRoot->right == NULL) { 
                    cout << "Node with left branch found" << endl;
                    goner = aRoot;
                    aRoot = aRoot->left;
                    delete goner;
                    return true;
                }
                //node has two branches
                else {                          
                    cout << "Node with two branches found" << endl;
                    goner = aRoot;              //store node to be deleted
                    gonerL = aRoot->left;       //store left subtree root
                    gonerR = aRoot->right;      //store right subtree root
                    
                    //search for largest value in left subtree and store in pointer replacement
                    replacement = gonerL;
                    while (replacement->right != NULL)
                        replacement = replacement->right;
                        
                    //If the node with the replacement value has a left subtree, store the address of that subtree
                    if (replacement->left != NULL)
                        replacementL = replacement->left;
                                            
                    //Start rearranging tree
                    //If target is first node, that will be replacement
                    if (aRoot == oldRoot)
                        aRoot = replacement;
                    else {
                        aRoot = oldRoot;
                    
                        if (replacement->data < aRoot->data)
                            aRoot->left = replacement;
                        else
                            aRoot->right = replacement;
                    }    
                    // make sure there are no nodes looping back
                    replacement->left = gonerL;
                    if (gonerL->right == gonerL)
                        gonerL->right = NULL;
                    if (gonerL->left == gonerL)
                        gonerL->left = NULL;
                        
                    //if there was a left subtree of the original replacement
                    //, attach it to the proper subtree of the replacement
                    if (replacementL != NULL) {
                        if (replacementL->data < replacement->data)
                            replacement->left = replacementL;
                        else
                            replacement->right = replacementL;
                    }
                    replacement->right = gonerR;
                    
                    delete goner;
                    return true;
                }
            }
            //If neither stopping condition is met, search recursively for the element
            else if (el < aRoot->data) {
                oldRoot = aRoot;
                return dele (aRoot->left, el);
            }
            else {
                oldRoot = aRoot;
                return dele (aRoot->right, el);
            }
        }

        
        void display (treeNode* aRoot) const
        {
            if (aRoot != NULL) {
                display (aRoot->left);
                cout << aRoot->data << endl;
                display (aRoot->right);
            }
        }

};
#endif

and a little function to drive it. Yes, I think the use of "0" to stop the insertion of integers is lame, but I was concentrating on getting the function to work.

CPP / C++ / C Code:

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


int main () {
   
    binaryTree<int> bTree;
    cout << "Enter numbers to insert. Enter 0 to stop:" << endl;
    int next;
    bool success;
    cin >> next;
    while (next != 0) {
        success = bTree.insert(next);
        cin >> next;
    }
    bTree.display();
    
    cout << "Enter number to delete:";
    cin >> next;
    success = bTree.dele(next);
    bTree.display();
    
    return 0;
}

TIA for your constructive criticism

Blake · #4 28-Jun-2006, 07:26

You should be able to to the erase by reassigning pointers only; It can be done without ever deleting a node. If you do delete a node, make sure you make its children NULL first. Your destructor should delete both the left and right children if they are not NULL.

You need to define a destructor. It should look something like this:

CPP / C++ / C Code:

binaryTree::~binaryTree()
{
  if (root != NULL) delete root;
}

treeNode::~treeNode()
{
  if (left != NULL) delete left;
  if (right != NULL) delete right; 
}

Defining a successor function would make your code cleaner. Here's one I wrote awhile back:

CPP / C++ / C Code:

template <typename KEY_TYPE, typename KEY_COMP>
BSTreeNode<KEY_TYPE, KEY_COMP> * BSTreeNode<KEY_TYPE, KEY_COMP>::successor()
{
  if (right != NULL) return right->treeMin();
  RBTreeNode<KEY_TYPE, KEY_COMP> * x = this;
  RBTreeNode<KEY_TYPE, KEY_COMP> * y = parent;
  while (y != NULL && x == y->right)
  {
    x = y;
    y = y->parent;
  }
  return y;
}

And here's the erase function, which uses the successor function and never needs to delete a node:

CPP / C++ / C Code:


template <typename KEY_TYPE, typename KEY_COMP>
BSTreeNode<KEY_TYPE, KEY_COMP> * BSTree<KEY_TYPE, KEY_COMP>::
                                  erase(RBTreeNode<KEY_TYPE, KEY_COMP> * z)
{
  RBTreeNode<KEY_TYPE, KEY_COMP> * x = NULL;
  RBTreeNode<KEY_TYPE, KEY_COMP> * y = NULL;
  if (z->left == NULL || z->right == NULL) y = z;
  else y = z->successor();
  if (y->left != NULL) x = y->left;
  else x = y->right;
  if (x != NULL) x->parent = y->parent;
  if (y->parent == NULL) root = x;
  else
  {
    if (y->isLeftChild()) y->parent->left = x;
    else y->parent->right = x;
  }
  if (y != z) z->key = y->key;
  return y;
}

You may find this helpfull too:

http://www.cs.vassar.edu/~cs241/slides/bst.pdf

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
can anyone help me with my tree :)	bioeng_mtm	C++ Forum	5	22-Apr-2006 12:50
Binary Search Tree in C++	rpg3	C++ Forum	5	02-Apr-2006 09:53
linked list error message	Krandygrl00	C++ Forum	4	22-Jun-2005 14:13
printing binary search tree	nkhambal	C Programming Language	2	26-Mar-2005 03:01
Search Engine Positioning 101 and 201 "How To" Tips...	000	Search Engine Optimization Forum	0	29-May-2003 10:34

Deleting a node from binary search tree

Re: Deleting a node from binary search tree

Re: Deleting a node from binary search tree

Re: Deleting a node from binary search tree