July 9, 2008 06:22am pdt

1. TheLearn... 89,600
2. Dhaest 87,023
3. apeter 79,170
4. jaime_ol... 61,453
5. jpaulino 52,240
6. jcoehoorn 44,175
7. emoreau 39,468
8. angelIII 36,950
9. GreenGhost 28,795
10. naspinski 28,000
11. TimCottee 25,359
12. gregoryy... 23,000
13. Fernando... 22,854
14. PockyMaster 22,198
15. PaulHews 21,040

1. TheLearn... 277,635
2. Dhaest 139,036
3. jaime_ol... 101,740
4. jpaulino 93,470
5. gregoryy... 91,132
6. angelIII 88,255
7. Idle_Mind 87,825
8. Fernando... 82,381
9. emoreau 79,387
10. apeter 79,170
11. Sancler 68,120
12. VBRocks 67,430
13. jaiganes... 57,145
14. jcoehoorn 52,550
15. surajguptha 44,050

01.29.2008 at 08:55PM PST, ID: 23121811

	[x] Attachment Details

[x]

The Solution Rating System

With so many solutions, how can you tell which solutions are most likely to help you and which ones are not? To provide you with a tool to use, we rate our solutions based on various elements that most accurately determine if a solution is a quality solution. To explain what factors affect the solution rating, here are the elements we take into consideration when formulating our solution rating.

The Grade of the Solution
The Zone Rank of the Expert Providing the Solution
The Number of Author and Expert Comments
The Number of Experts Contributing
The Feedback of the Community

Your Input Matters
Because of the way the system is set up, the most important variable in this equation is you. As a member of Experts Exchange, you are able to cast your vote on the quality of the solutions in regard to how complete, accurate, helpful and easy to understand each solution is. When you provide your feedback, each rating is adjusted accordingly. So, if you see a solution that has a poor rating that you think is a good solution, let us know by rating it. As you do, the rating will be adjusted and will become more accurate for other members of our site.

If you have any suggestions that you would like to make for our rating system, please ask a question in the Suggestions Zone of Community Support.

Thank you!

7.6

Delete Node From Binary Search Tree

Zones: .Net Editors & IDEs, Microsoft Visual C++.Net, Microsoft Visual C#.Net

Tags: C#

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.

         
           
             1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:

           
           
             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();
        }

           
         

Start your free trial to view this solution

Question Stats

Zone: Programming

Question Asked By: jmkotman

Solution Provided By: Infinity08

Participating Experts: 1

Solution Grade: A

Translate:

Loading Advertisement...

Microsoft

Internet Protocols
Applications

Development
OS

Hardware
Windows Security

Apple

Operating Systems
Hardware

Programming
Networking

Software

Internet

Search Engines
File Sharing
WebTrends / Stats
Spy / Ad Blockers

Web Browsers
New Net Users
Web Development
Chat / IM

Anti Spam
Web Servers
Anti-Virus
Email Clients

Gamers

Tips
Online / MMORPG
Puzzle
Emulators

Action / Adventure
Role Playing
Consoles
Game Programming

Strategy
Sports
Misc
Computer Games

Digital Living

Hardware
New Net Users
New Users

Software
Digital Music
Gaming World

Home Security
Apple
Networking Hardware

Virus & Spyware

Vulnerabilities
IDS
Encryption
Anti-Virus

Operating Systems Security
Software Firewalls
WebApplications
Cell Phones

Operating Systems
Internet
Hardware Firewalls

Hardware

Handhelds / PDAs
Displays / Monitors
Components
Networking Hardware

Peripherals
Laptops/Notebooks
Storage
Servers

Desktops
New Users
Misc
Apple

Software

System Utilities
Industry Specific
Network Management
Photos / Graphics
Page Layout
VMWare
Misc
Web Development

OS
CYGWIN
Voice Recognition
Message Queue
Quality Assurance
Security
Firewalls
MultiMedia Applications

Development
Database
Office / Productivity
Business Management
OS/2 Apps
Server Software
Internet / Email

ITPro

OS
Storage
Encryption
Operating Systems Security
Apple Hardware
Laptops & Notebooks
Servers
Networking Hardware
Peripherals

Devices
Displays / Monitors
WebTrends / Stats
Search Engines
Firewalls
WebApplications
IDS
Vulnerabilities
Email Clients

File Sharing
Spy / Ad Blockers
Web Browsers
Web Servers
Networking
Anti-Virus
Chat / IM
Anti Spam

Developer

Web Servers
Web Browsers
Game Programming
Dev Tools
Industry Specific
Office / Productivity

Database
CYGWIN
Web Development
Search Engines
File Sharing
WebTrends / Stats

Programming
Content Management
Application Servers
Protocols

Storage

Removable Backup Media
Storage Technology
Servers

Grid
Remote Access
Backup / Restore

Misc
Hard Drives

Miscellaneous
Security
Development
Linux
VMWare

MainFrame OS
Unix
Apple
OS / 2
AS / 400

BeOS
Microsoft
VMS / OpenVMS

Database

Oracle
Miscellaneous
MySQL
Software
Sybase
Contact Management
PostgreSQL
Data Manipulation
Clarion
InterSystems Cache

Siebel
MUMPS
OLAP
SQLBase
SAS
GIS & GPS
4GL
Berkeley DB
DB2
Informix

Interbase / Firebird
FoxPro
Reporting
LDAP
Filemaker Pro
MS SQL Server
dBase
MS Access

Security

Misc
Web Browsers
Software Firewalls
Operating Systems Security
File Sharing

Spy / Ad Blockers
Vulnerabilities
WebApplications
IDS
Anti-Virus

Encryption
Anti Spam
Email Clients
VPN
Chat / IM

Programming

Editors IDEs
Installation
Handhelds / PDAs
Multimedia Programming
System / Kernel

Algorithms
Game
Signal Processing
Project Management
Open Source

Database
Misc
Languages
Processor Platforms
Theory

Web Development

Scripting
Blogs
Web Servers
Software
Search Engines
Web Graphics
Images

Internet Marketing
Images and Photos
Components
Document Imaging
Web Languages/Standards
Illustration
WebApplications

Fonts
WebTrends / Stats
Authoring
Digital Camera Software
Miscellaneous

Networking

Protocols
Apple Networking
Network Management
Message Queue
Application Servers
Content Management
File Servers
Email Servers
Misc
Java Editors & IDEs

Wireless
Networking Hardware
Backup / Restore
System Utilities
ISPs & Hosting
Web Servers
Storage Technology
Removable Backup Media
Servers
Broadband

Grid
OS / 2
Novell Netware
Unix Networking
Windows Networking
Security
Telecommunications
Operating Systems
Linux Networking

Other

Community Advisor
Lounge
Community Support
New Net Users

Philosophy / Religion
Math / Science
Miscellaneous
URLs

Expert Lounge
Politics
Puzzles / Riddles

Community Support

Suggestions
New to EE
New Topics
Community Advisor

CleanUp
Announcements
General

Feedback
Input
EE Bugs

01.29.2008 at 09:02PM PST, ID: 20774782

Rank: Guru

jkr:

Moving you to managed (aka .NET zones), that suits better.

01.30.2008 at 12:51AM PST, ID: 20775572

Infinity08:

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.

Accepted Solution

01.30.2008 at 06:42AM PST, ID: 20777311

jmkotman:

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#

01.30.2008 at 06:44AM PST, ID: 20777338

Infinity08:

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 :)

01.30.2008 at 10:33PM PST, ID: 20784402

jmkotman:

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.

                       
         
           
             1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:

           
           
              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

01.31.2008 at 01:18AM PST, ID: 20785041

Infinity08:

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++).

20080236-EE-VQP-29 / EE_QW_2_20070628