[solved][C] wstawianie elementu do drzewa BST

Chodzi o funkcję, która wstawia element o zadanym kluczu do stworzonego już drzewa.

Funkcja sypie się (nie zawsze, ale tak średnio w 80% przypadków) w miejscu oznaczonym w kodzie (piszę w DevCpp, więc kompilator GCC).

Używając debuggera, udało mi się tylko tyle dowiedzieć, że wskaźnik curr przybiera dość w chwili błędu dziwną wartość 0xfeeefeee. Z tego co udało mi się wygooglować, może to oznaczać jakiś błąd pamięci na stosie. Próbowałem zwiększyć rozmiar stosu, bo z tego co wiem, w Windowsie wynosi on chyba 2 MB (doradzono mi, aby w ustawieniach linkera dodać zwiększyć rozmiar stosu, próbowałem zarówno komendą --stack, jak i --heap, zwiększyłem do kilkudziesięciu MB i nic...). Już sam nie wiem, co z tym robić. Kod wydaje się być poprawny, nie rozumiem, dlaczego się sypie. Czy ktoś mógłby na to zerknąć i pomóc? Bardzo mi na tym zależy.

void insValToBinTree(binTreeNode *root, int valToIns) {
  binTreeNode *curr = root;
	binTreeNode *newItem = NULL;
	while (curr != newItem) {		
    while ((curr != newItem) && (valToIns <= (curr -> value)))  {/* check left child */ /* WYSYPUJE SIĘ ZAWSZE NA TEJ LINII */
      if (curr -> left == NULL)    /* if no node in the right child */
        curr -> left = newItem = allocBinTreeNode(valToIns, curr);    /* insert */
			
      curr = curr -> left;        /* turn left, possibly to newNode (then procedure will stop) */
    }
    while ((curr != newItem) && (valToIns > curr -> value)) {    /* check right child */

      if (curr -> right == NULL)  /* if no node in the right child */
        curr -> right = newItem = allocBinTreeNode(valToIns, curr);  /* insert */

      curr = curr -> right;        /* turn right, possibly to newNode (then procedure will stop) */
    } 
  }
}

Z tego co udało mi się wygooglować, może to oznaczać jakiś błąd pamięci na stosie. Próbowałem zwiększyć rozmiar stosu, bo z tego co wiem, w Windowsie wynosi on chyba 2 MB [...]

Stos nie ma nic do rzeczy, bo algorytm, który podałeś, nie jest rekurencyjny, więc zużycie stosu jest małe. Stawiałbym na dziwaczne warunki z newItem.

Może tak:

void insValToBinTree(binTreeNode **root, int valToIns) 
{
	binTreeNode *curr = *root;
	
	while (curr) 
	{       
		if(valToIns <= curr -> value)
		{
			if (!curr -> left) 
			{
				curr -> left = allocBinTreeNode(valToIns, curr);
				break;
			}
			
			curr = curr -> left;
		}
		else
		{
			if (!curr -> right) 
			{
				curr -> right = allocBinTreeNode(valToIns, curr);
				break;
			}
			
			curr = curr -> right;
		}
	}
	
	if(!curr) *root = allocBinTreeNode(valToIns, *root); /* nie wiem czy 2 parametr jest dobry */
}

Dzięki za pomoc, faktycznie tę funkcję można uprościć.

Nie zmienia to faktu, że nadal nie działa :-(

I wysypuje się na tej samej linii: warunek if(valToIns <= curr -> value)

A i ostatnia funkcja w Twoim kodzie:
if(!curr) *root = allocBinTreeNode(valToIns, *root); /* nie wiem czy 2 parametr jest dobry */

powinna mieć postać

if(!curr) *root = allocBinTreeNode(valToIns, NULL);

bo root nie ma rodzica (root -> parent wskazuje na NULL).

Tak już myślałem, że może samo drzewo jest źle tworzone - bo wysypuje się na tym curr -> value, ale to raczej niemożliwe, bo wypisywanie całego drzewa w porządku in-order działa prawidłowo...

Tak już myślałem, że może samo drzewo jest źle tworzone - bo wysypuje się na tym curr -> value

No musi być coś nie tak z drzewem, jeśli się wysypuje. NULL odpada, więc pozostaje przypadkowy adres, ale skąd? Pokaż może zawartość allocBinTreeNode.

A i ostatnia funkcja w Twoim kodzie:
[...]
powinna mieć postać
[...]

Aha, czyli nie pomyliłem się ;)

No musi być coś nie tak z drzewem, jeśli się wysypuje. NULL odpada, więc pozostaje przypadkowy adres, ale skąd? Pokaż może zawartość allocBinTreeNode.

Ta funkcja alokuje pamięć dla węzła drzewa. Nie sądzę by to była jej "wina", bo w innych funkcjach wywołana, działa poprawnie.

binTreeNode *allocBinTreeNode(int value, binTreeNode *parent) {       	/* memory allocation for binTreeNode */
  binTreeNode *newItem = (binTreeNode *) malloc (sizeof(binTreeNode));	/* allocation */
  if (newItem == NULL) {
		err("alloc problem!!!\n");  /* pomocnicza funkcja do obsługi błędów, wyświetla napis podany jako parametr, czeka na dowolny klawisz i zamyka program */
	}
  newItem -> left = newItem -> right = NULL;														/* setting proper pointers' values */
  newItem -> parent = parent;
  newItem -> value = value;																							/* setting the key value */
  return newItem;
}

Co mnie najbardziej dziwi w tym niedziałaniu funkcji insertującej to to, że na tej samej zasadzie działa funkcja tworzenia drzewa binarnego i działa bez problemu, a i drzewo wydaje się być tworzone poprawnie, bo in-order działa dobrze. Oto kod:

binTreeNode *createBST(int *arr, int arrSize) {	/* returns a pointer to newly created BST from array 'arr' */
  int i;
	binTreeNode	*root = NULL,	*curr = NULL, *newItem = NULL;
  for (i = 0; i < arrSize; i++) {
    if (root == NULL)                           /* root of BST */
      root = allocBinTreeNode(arr[i], NULL);		/* root has no parent, therefore NULL pointer used */

    else {                                      /* seeking */
      curr = root;															/* start from root */
      newItem = NULL;
      while (curr != newItem) {        					/* repeating until new item is inserted */
        while ((curr != newItem) && (arr[i] <= curr -> value)) {  /* check left child */
          if (curr -> left == NULL)    					/* if no node in left child */
            curr -> left = newItem = allocBinTreeNode(arr[i], curr);  			/* insertion with mem.allocation,
            																																curr is a parent of newNode */
          curr = curr -> left;         					/* turn left, possibly to newNode (then loop will stop) */
                /*printf("curr %d newItem %d\n", curr, newItem);*/

        }
        while ((curr != newItem) && (arr[i] > curr -> value)) {   /* check right child */
          if (curr -> right == NULL)   					/* if no node in right child */
            curr -> right = newItem = allocBinTreeNode(arr[i], curr); 			/* insertion with mem.allocation,
            																																curr is a parent of newNode */
          curr = curr -> right;        					/* turn right, possibly to newNode (then loop will stop) */
                /*printf("curr %d newItem %d\n", curr, newItem);*/

        }
      }
    }
  }
  return root;
}

Zatem naprawdę już nie wiem, co może być powodem błędu w działaniu insValToBinTree. Byłbym bardzo wdzięczny za pomoc.

Nie widzę nic, co mogłoby powodować błąd. Podaj dokładnie treść błędu. Robisz coś jeszcze pomiędzy wywołaniami createBST a insValToBinTree?

Wywołuję procedurę usuwania elementu, by go potem z powrotem wstawić (po prostu program mierzy czas działania tych procedur). Procedura usuwania elementu ma następującą postać (wklejam poniżej). Przepraszam że takie multum kodu (załączam używane w procedurze usuwania funkcje), ale wszystko okomentowałem, żeby było zrozumiałe.

void delValueOfBinTree(binTreeNode **root, int valToDel) {
	delItemFromBinTree(root, findItemInBinTree(*root, valToDel));
}

binTreeNode *findItemInBinTree(binTreeNode *root, int valToFind) {
  binTreeNode *curr = root;
  while (1) {
    if ((curr == NULL) || (curr -> value == valToFind))
      return curr;
    else if (valToFind < curr -> value)
      curr = curr -> left;
    else
      curr = curr -> right;
  }
}


void delItemFromBinTree(binTreeNode **root, binTreeNode *item) {
	if (item == NULL)
		return;

	if ((item -> left == NULL) && (item -> right == NULL)) {	/* _HASN'T_ children */
			switch (typeOfSon(item)) {
				case 0 :																			/* _IS_ root */
					free(*root);
					*root = NULL;																/* deleting last node (root) */
					break;
				case 1 :																			/* _IS_ left son */
					item -> parent -> left = NULL;		/* change in parent */
					break;
				case 2 :																			/* _IS_ right son */
					item -> parent -> right = NULL;		/* change in parent */
					break;
				default :																			/* pointer error */
					err("Error while deletion node with no descendants");
			}

	}
	else if (item -> left == NULL) {					/* _HAS_ only right son */
				switch (typeOfSon(item)) {
				case 0 :										/* _IS_ root */
					free(root);
					*root = (*root) -> right;		/* right son of root is set as new root */
					(*root) -> parent = NULL;		/* new root has no parents */
					break;
				case 1 :						/* _IS_ left son */
					item -> right -> parent = item -> parent;	/* parent is set as parent of right son */
					item -> parent -> left = item -> right;	    /* right son is set as new left son of parent */
					break;
				case 2 :								/* _IS_ right son */
					item -> right -> parent = item -> parent;	/* parent is set as parent of right son */
					item -> parent -> right = item -> right;		/* right son is set as new right son of parent */
				break;
				default :						/* pointer error */
					err("Error while deletion node with no only right son");
			}
	}
	else if (item -> right == NULL) {		/* _HAS_ only left son */
				switch (typeOfSon(item)) {
				case 0 :					/* _IS_ root */
					free(*root);
					*root = (*root) -> left;		/* left son of root is set as new root */
					(*root) -> parent = NULL;		/* new root has no parents */
					break;
				case 1 :			/* _IS_ left son */
					item -> left -> parent = item -> parent;	/* parent is set as parent of left son */
					item -> parent -> left = item -> left;		/* right son is set as new left son of parent */
					break;
				case 2 :						/* _IS_ right son */
					item -> left -> parent = item -> parent;	/* parent is set as parent of left son */
					item -> parent -> right = item -> left;		  /* left son is set as new right son of parent */
				break;
				default :					/* pointer error */
					err("Error while deletion node with no only left son");
			}
	}
	else {					/* _HAS_ 2 children */
		binTreeNode *toIns = rand3(0, 1) ? succ_binTree(item) : pred_binTree(item);	/* randomization */
		item -> value = toIns -> value;
		delItemFromBinTree(root, toIns);

	}
	if (typeOfSon(item) != 0)			/* if not root, free */
		free(item);
}


int typeOfSon(binTreeNode *item) {
	if (item -> parent == NULL)
		return 0;							/* is root */
	else if (item -> parent -> left == item)
		return 1;							/* is left son */
	else if (item -> parent -> right == item)
		return 2;
	else return -1;							/* error */
}


binTreeNode *pred_binTree(binTreeNode *item) {  /* returns predecessor of item  */
  if (item -> left != NULL)                     /* if has left subtree */
    return max_binTree(item -> left);           /* predecessor is max element of left subtree */
  else {                                        /* hasn't left subtree */
    while (item -> parent -> right != item)     /* seeking up until the current node is a right son */
      item = item -> parent;
   return item;
  }
}


binTreeNode *succ_binTree(binTreeNode *item) {  /* returns successor of item */
  if (item -> right != NULL)                    /* if has right subtree */
    return min_binTree(item -> right);          /* successor is min element of right subtree */
  else {																				/* hasn't right subtree */
    while (item -> parent -> left != item)     	/* seeking up until the current node is a left son */
      item = item -> parent;
  }
}


binTreeNode *max_binTree(binTreeNode *root) {
  while (root -> right != NULL)
    root = root -> right;
  return root;
}


binTreeNode *min_binTree(binTreeNode *root) {
	/*fprintf(flog, "min\n");*/
  while (root -> left != NULL)
    root = root -> left;
  return root;
}

void delItemFromBinTree(binTreeNode **root, ...) 
{
	[...]

	free(root); //<---- co usuwasz?
	*root = (*root) -> right;   //<--- patrz niżej      
	(*root) -> parent = NULL;         

	[...]

	free(*root);
	*root = (*root) -> left;   //<--- na co wskazuje *root (ten po prawej)?           
	(*root) -> parent = NULL;          

	[...]
}

Na razie tyle...

To prawda, najpierw zwalniam, potem próbuję z tego korzystać - błąd.

myślę, że teraz napisałbym to tak:

binTreeNode *toDel;

toDel = *root;
*root = (*root) -> left; /* lub analogicznie */ *root = (*root) -> right;
free(toDel);

Jednak, po tej modyfikacji, znowu nie działa :-( Funkcja insertująca wysypuje się w tej samej linii: if(valToIns <= curr -> value)

Czy jeszcze widzisz może jakieś błędy w tej funkcji usuwającej? Bo jej poświęciłem wcześniej ładnych kilka godzin i nic nie wyłapałem :-(

A co do komunikatu błędu - segmentation fault...

else 
{
	binTreeNode *toIns = rand3(0, 1) ? succ_binTree(item) : pred_binTree(item);
	item -> value = toIns -> value; //<---- 
	delItemFromBinTree(root, toIns);
}
	
if (typeOfSon(item) != 0) free(item); //<--- a to na pewno tu?

Faktycznie, tu był błąd.

Dałem return po wywołaniu rekurencyjnym delItem... i wygląda na to, że działa już ok.

Wielkie, wielkie dzięki za pomoc.