• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 4134
  • Last Modified:

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

0
jmkotman
Asked:
jmkotman
  • 3
  • 2
1 Solution
 
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
 
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

Featured Post

Take Control of Web Hosting For Your Clients

As a web developer or IT admin, successfully managing multiple client accounts can be challenging. In this webinar we will look at the tools provided by Media Temple and Plesk to make managing your clients’ hosting easier.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now