Thread: Help with insert/delete binary search tree

a->leftTree = prevPtr->leftTree = currPtr

these are all equal...

I don't know...

Please, can't you just help me? I've been around this function for the past 4 hours, my brain is about to explode, I just can't find my way around to fix it...

Originally Posted by vart

if prevPtr->leftTree == currPtr

it means you are on the LEFT side of the parent

if prevPtr->rightTree == currPtr

it means you are on the RIGHT side of the parent

I see what you mean now... I'm sorry but I'm waaaaaay behind schedule for this and when things like this take more time than it should and I can't figure it out after countless hours debugging, I begin to loose it...

That made see I could improve my function a little bit as per point A) but I wouldn't mind to improve it even further, anyway, here's the updated version, which I suppose has all those problems fixed:

Code:

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
	if(!cTree) return FALSE;
	
	ClientTree currPtr = *cTree;
	ClientTree prevPtr = NULL;
	int nCompare;
	
	while(currPtr) {
		nCompare = strcmp(currPtr->clientName, cName);
		
		if(nCompare > 0) {
			prevPtr = currPtr;
			currPtr = currPtr->leftTree;
		} else if(nCompare < 0) {
			prevPtr = currPtr;
			currPtr = currPtr->rightTree;
		} else {
			/*
			 * A)
			 * 
			 * The following cases have 3 lines in common, the free()
			 * calls and return statement. Is there anyway to improve
			 * this code and make it more compact?
			 * 
			 * Of course, the printf's are to be removed...
			 */
			if(!prevPtr) {
				printf("CASE #1\n");
				
				*cTree = NULL;

				free(currPtr->clientProfile);
				free(currPtr);
				
				return TRUE;
			} else if(!currPtr->leftTree || !currPtr->rightTree) {
				printf("CASE #2\n");
				
				if(prevPtr->leftTree == currPtr) {
					prevPtr->leftTree = currPtr->rightTree;
				} else {
					prevPtr->rightTree = currPtr->leftTree;
				}
				
				free(currPtr->clientProfile);
				free(currPtr);

				return TRUE;
			} else {
				printf("CASE #3\n");
				
				ClientTree tempPtr = currPtr->rightTree;
				
				while(tempPtr->leftTree) {
					tempPtr = tempPtr->leftTree;
				}
				
				/*
				 * C)
				 * 
				 * This has a big problem...
				 * 
				 * If you take a look at the ClientProfile structure,
				 * in the first post, you'll see two ints
				 * (clientNIF/clientAge) and one char* (clientName).
				 * 
				 * The problem is that the following code line is only
				 * copying the integer data, not the string. For some
				 * reason, the string remains the old one.
				 * 
				 * I tried to use strdup() directly on clientName like:
				 * currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
				 * but it still doesn't work.
				 * 
				 * Why everything is being copied but the strings?
				 */
				currPtr->clientProfile = tempPtr->clientProfile;
				
				/*
				 * D)
				 * 
				 * Is there anyway to not call the function itself
				 * and make the while loop once again and delete the
				 * corresponding leaf?
				 */
				return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
			}
		}
	}
	
	return FALSE;
}

The most important problem is C) of course, I need that fixed so the function fully works, at least... I can't understand why the string is not being copied...

Replacing:

Code:

if(!prevPtr)

By:

Code:

if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree)

Fixes it right?

My test tree is inserted in this order: H, F, P, G, L, Z and the output you see is in-order. In the following output I'm trying to remove "H", which is the root node... As you can see, first is called case #3 because there are 2 child nodes and then case #2.

As far as I can see, everything is working, apart from the string that is not copied... Element "L" (in-order successor) values (50 and 5000000) were copied to the "H" element, but no the string "L", I honestly can't understand why this isn't being copied...

Code:

nazgulled ~/LI3 $ make && ./atulco 
gcc -O2 -Wall -g -c atulco.c
gcc -O2 -Wall -g -o atulco atulco.o cities.o clients.o debug.o

F (20, 2000000)
G (40, 4000000)
H (10, 1000000)
L (50, 5000000)
P (30, 3000000)
Z (60, 6000000)

CASE #3
CASE #2
F (20, 2000000)
G (40, 4000000)
H (50, 5000000)
P (30, 3000000)
Z (60, 6000000)

I think I fixed all my problems, let's hope so...

Here's my (supposed) final code:

Code:

bool deleteClientFromTree(ClientTree *cTree, char *cName) {
	if(!cTree) return FALSE;
	
	ClientTree currPtr = *cTree;
	ClientTree prevPtr = NULL;
	int nCompare;
	
	while(currPtr) {
		nCompare = strcmp(currPtr->clientName, cName);
		
		if(nCompare > 0) {
			prevPtr = currPtr;
			currPtr = currPtr->leftTree;
		} else if(nCompare < 0) {
			prevPtr = currPtr;
			currPtr = currPtr->rightTree;
		} else {
			
			if(currPtr->leftTree && currPtr->rightTree) {
				printf("CASE #3: NODE WITH 2 CHILDS\n");
				
				ClientTree tempPtr = currPtr->rightTree;
				
				while(tempPtr->leftTree) {
					tempPtr = tempPtr->leftTree;
				}
				
				currPtr->clientName = tempPtr->clientProfile->clientName;
				
				currPtr->clientProfile = newClientProfile(
					tempPtr->clientProfile->clientName,
					tempPtr->clientProfile->clientAge,
					tempPtr->clientProfile->clientNIF
				);

				cName = tempPtr->clientProfile->clientName;
				
				prevPtr = currPtr;
				currPtr = currPtr->rightTree;
			} else {
				if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
					printf("CASE #1: ROOT NODE\n");
					
					*cTree = NULL;
				} else {
					printf("CASE #2: LEAF OR SINGLE CHILD\n");
					
					if(prevPtr->leftTree == currPtr) {
						prevPtr->leftTree = currPtr->rightTree;
					} else {
						prevPtr->rightTree = currPtr->leftTree;
					}
				}
				
				free(currPtr->clientProfile);
				free(currPtr);
				
				return TRUE;
			}
		}
	}
	
	return FALSE;
}

ClientProfile newClientProfile(char *cName, int cAge, int cNIF) {
	ClientProfile cProfile = malloc(sizeof(nClientProfile));
	
	if(!cProfile) perror("malloc");
	
	cProfile->clientName = strdup(cName);
	
	if(!cProfile->clientName) perror("strdup");
	
	cProfile->clientAge = cAge;
	cProfile->clientNIF = cNIF;
	
	return cProfile;
}

Is it ok now?

/me crosses fingers!