Delete Node From Binary Search Tree

I am working right now on writing a method to delete nodes out of a tree.  I have written a method to find the node to be deleted.  My issue is that i need to somehow point those child pointers of that node so that they are not lost.  I have attached my code that i use to find the node in the array and delete it.
BST ARRAY:
microsoft        3989898989 02 03 
java             1357357357 05 12 
zipinfo          0490080000 04 28 
pizzahut         3789789789 20 07 
google           3333333333 06 08 
cnn              1444444444 21 09 
yahoo            2121212121 11 00 
ilounge          4040404040 18 00 
dictionary       0555555555 31 10 
expedia          1234543210 00 17 
un               3939393939 13 14 
limewire         1010101010 22 00 
quicken          4294967295 00 15 
verizon          2468246824 00 16 
secondlive       1888888888 25 26 
wikipedia        4242424242 00 19 
facebook         1616161616 00 29 
howstuffworks    0000000001 00 00 
xe               0123123123 00 00 
nytimes          1234554321 27 23 
barnesandnoble   1111111111 24 00 
kalamazoocity    2444666888 00 00 
oprah            2999999999 00 00 
amazon           2222222222 00 30 
radioshack       4294000000 00 00 
tripadvisor      0777777777 00 00 
myspace          1234567890 00 32 
zzz              1234512345 00 00 
firefox          2244668800 00 00 
askjeeves        3456776543 34 00 
dell             1515151515 00 33 
netflix          0987654321 00 00 
dellcomputers    1122334455 00 00 
apple            2468013579 00 00 
 
 
        public static void ProcessUpdate()
        {
            int Transactions = 0;
 
            if (menuchoice == 2)
            {
                FileStream ManagerRead = new FileStream("A1 ManagerTransFile a-z.txt", FileMode.OpenOrCreate, FileAccess.Read, FileShare.None);
                StreamReader ReadManager = new StreamReader(ManagerRead);
 
                Transactions = 0;
                data = "";
 
                data = ReadManager.ReadLine();
 
                while (data != null)
                {
                    string InsertData = "";
 
                    for (int i = 0; i < 1; i++)
                    {
                        InsertData += data[i];
                    }
 
                    if (InsertData == "I")
                    {
                        Insert();
 
                        N++;
                        Transactions++;
                        WriteToLog.WriteLine("I: {0} {1} done (search path of {2})", url, ipAddress, NodeCount.ToString("d2"));
                    }
                    else
                    {
                        MethodCall = "D";
                        Delete();
                        Transactions++;
                    }
 
                    data = ReadManager.ReadLine();
                }
 
                WriteToLog.WriteLine("*Update BST done: {0} transactions done", Transactions.ToString("d2"));
                ReadManager.Close();
            }
            else
            {
                FileStream UserRead = new FileStream("A1 UserTransFile a-z.txt", FileMode.OpenOrCreate, FileAccess.Read, FileShare.None);
                StreamReader ReadUser = new StreamReader(UserRead);
 
                Transactions = 0;
                data = "";
 
                data = ReadUser.ReadLine();
 
                while (data != null)
                {
                    if (data == "P")
                    {
                        NodeCount = 0;
                        WriteToLog.WriteLine("P:");
                        Print(rootPtr);
                        WriteToLog.WriteLine();
                        WriteToLog.WriteLine();
                        Transactions++;
                    }
                    else
                    {
                        MethodCall = "Q";
                        Query();
                        Transactions++;
                    }
 
                    data = ReadUser.ReadLine();
                }
 
                WriteToLog.WriteLine("*Process BST done: {0} transactions done", Transactions.ToString("d2"));
            }
        }
 
 public static void Search()
        {
            bool Search = true;
            int count = 0;
            Pointer = 1;
 
            while (Search == true)
            {
                if (string.Compare(Read, BSTHold[Pointer, 0]) < 0)
                {
                    if (Convert.ToInt32(BSTHold[Pointer, 2]) != 0)
                    {
                        Pointer = Convert.ToInt32(BSTHold[Pointer, 2]);
                        count++;
                    }
                    else
                    {
                        if (MethodCall == "Q")
                        {
                            WriteToLog.WriteLine("Q: {0} >> not found  (search path of {1})", Read, count.ToString("d2"));
                        }
                        else
                        {
                            WriteToLog.WriteLine("D: {0} >> not found    (search path of {1})", Read, count.ToString("d2"));
                        }
                        Search = false;
                    }
                }
                else if (string.Compare(Read, BSTHold[Pointer, 0]) > 0)
                {
                    if (Convert.ToInt32(BSTHold[Pointer, 3]) != 0)
                    {
                        Pointer = Convert.ToInt32(BSTHold[Pointer, 3]);
                        count++;
                    }
                    else
                    {
                        if (MethodCall == "Q")
                        {
                            WriteToLog.WriteLine("Q: {0} >> not found  (search path of {1})", Read, count.ToString("d2"));
                        }
                        else
                        {
                            WriteToLog.WriteLine("D: {0} >> not found    (search path of {1})", Read, count.ToString("d2"));
                        }
                        Search = false;
                    }
                }
                else
                {
                    count++;
                    if (MethodCall == "Q")
                    {
                        WriteToLog.WriteLine("Q: {0} >> {1} (search path of {2})", Read, BSTHold[Pointer, 1].ToString(), count.ToString("d2"));
                    }
                    else
                    {
                        BSTHold[Pointer, 0] = "%%% Delete %%%";
                        BSTHold[Pointer, 1] = "0000000000";
                        BSTHold[Pointer, 2] = "00";
                        BSTHold[Pointer, 3] = "00";
 
                        WriteToLog.WriteLine("D: {0} >> deleted      (search path of {1})", Read, count.ToString("d2"));
                    }
                    Search = false;
                }
            }
        }
 
        public static void Delete()
        {
            Read = "";
 
            for (int i = 2; i < 18; i++)
            {
                Read += data[i].ToString(); ;
            }
 
            Search();
        }

Open in new window

jmkotmanAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Infinity08Commented:
Take a look at this :

        http://en.wikipedia.org/wiki/Binary_search_tree#Deletion

which explains how to delete a node from a BST.

Basically, you replace the deleted node with either the left-most child of the right subtree or the right-most child of the left subtree.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
jmkotmanAuthor Commented:
Thanks for the code on wikipedia, looks like its pretty simple.  I am not too familiar with how C++ is written because i have only programmed in C# before.  Could someone tell me how that looks in c#
0
Infinity08Commented:
I don't know C#, but it will be pretty similar to the C++ code listed there ... I'll let someone else give it a go :)
0
jmkotmanAuthor Commented:
I have been working on this and can't seem to get this code to work.  Can someone take a look at it and see if they can make the delete function work.
 int LeftNode = Convert.ToInt32(BSTHold[Pointer, 2]);
                        int CurrentNode = Convert.ToInt32(BSTHold[Pointer, 2]);
                        int CurrentNode2 = 0;
                        bool continueSearch = true;
 
 
                        while (continueSearch)
                        {
                            if (Convert.ToInt32(BSTHold[CurrentNode, 3]) == 0)
                            {
                                LeftNode = CurrentNode;
                                continueSearch = false;
                            }
                            else
                            {
                                CurrentNode = Convert.ToInt32(BSTHold[CurrentNode, 3]);
                            }
 
                        }
 
                        for (int x = 1; x <= N; x++)
                        {
                            if (Convert.ToInt32(BSTHold[x, 3]) == Pointer)
                            {
                                CurrentNode2 = Convert.ToInt32(BSTHold[x, 3]);
                            }
                            if (Convert.ToInt32(BSTHold[x, 2]) == Pointer)
                            {
                                CurrentNode2 = Convert.ToInt32(BSTHold[x, 2]);
                            }
 
                        }
 
                        for (int x = 1; x <= N; x++)
                        {
                            if (BSTHold[x, 0] != "%%% Delete %%%")
                            {
 
                                if (Convert.ToInt32(BSTHold[Convert.ToInt32(BSTHold[x, 3]), 2]) == Convert.ToInt32(BSTHold[CurrentNode2, 2]))
                                {
                                    BSTHold[x, 3] = BSTHold[Convert.ToInt32(BSTHold[x, 3]), 2];
                                    BSTHold[Convert.ToInt32(BSTHold[x, 3]), 3] = BSTHold[CurrentNode2, 3];
                                }
                            }
          
                        }
 
 
                        BSTHold[CurrentNode, 2] = BSTHold[Pointer, 2];
                        BSTHold[CurrentNode, 3] = BSTHold[Pointer, 3];
                        
                        BSTHold[Pointer, 0] = "%%% Delete %%%";
                        BSTHold[Pointer, 1] = "0000000000";
                        BSTHold[Pointer, 2] = "-1";
                        BSTHold[Pointer, 3] = "-1";
 
                        if (Pointer == 1)
                        {
                            rootPtr = CurrentNode;
                        }

Open in new window

0
Infinity08Commented:
As I said, I don't know C#, so I won't be of much help verifying your code. However, if it doesn't work, then I would suggest going over the algorithm explained on that wiki page, and implementing that exactly as stated. Use the C++ code as a guideline (assuming you can read C++).
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
.NET Programming

From novice to tech pro — start learning today.