Przeszukałem forum i nie znalazłem nigdzie rozwiązania następującego problemu:
Otóż chodzi o procedurę usuwania elementu ze standardowego drzewa binarnego (BST). Problem w tym, że procedura działa w stałym czasie, nawet jeśli robię milion powtórzeń i wyciągam średnią - a jak dla mnie, powinna być w czasie O(h), gdzie h jest wysokością drzewa. Drzewo jest tworzone losowo, ergo O(h) == O(lgn)...
Czy mógłby ktoś zerknąć, czy dobrze ta procedura jest napisana? Zawsze jak ktoś z boku spojrzy, to łatwiej błąd wykryje. A musi tu gdzieś siedzieć jakiś błąd, bo oprócz tego czasu bywa, że dla niektórych instancji (rzadko) procedura usuwania się wysypuje - nie mam pojęcia, dlaczego.
void delItemFromBinTree(binTreeNode **item) {
if (((*item) -> left == NULL) && ((*item) -> right == NULL)) {/* has no children */
if ((*item) -> parent != NULL) { /* not root (has parent)*/
if ((*item) -> parent -> left == (*item)) /* is a left son */
(*item) -> parent -> left = NULL; /* null pointer */
else /* otherwise, is a right son */
(*item) -> parent -> right = NULL; /* null pointer */
}
}
else { /* has child or children */
if ((*item) -> left == NULL) { /* hasn't left son */
(*item) -> right -> parent = (*item) -> parent; /* proper parent for linked right node */
if ((*item) -> parent -> left == (*item)) /* is a left son */
(*item) -> parent -> left = (*item) -> right;
else /* otherwise, is a right son */
(*item) -> parent -> right = (*item) -> right;
}
else if ((*item) -> right == NULL) { /* hasn't right son */
(*item) -> left -> parent = (*item) -> parent; /* proper parent for linked left node */
if ((*item) -> parent -> left == (*item)) /* is a left son */
(*item) -> parent -> left = (*item) -> left;
else /* otherwise, is a right son */
(*item) -> parent -> right = (*item) -> left;
}
else { /* has 2 children: */
binTreeNode *toDel /* pred/successor, to be deleted */
= rand3(0, 1) ? succ_binTree(*item) : pred_binTree(*item); /* randomization */
/* it is known, that pred/successor has no children, because it belongs to the subtree of deleted node */
if (toDel -> parent -> left == toDel) /* cutting from parent */
toDel -> parent -> left = NULL;
else
toDel -> parent -> right = NULL;
(*item) -> value = toDel -> value; /* copying value */
free(toDel); /* deletion of successor/predecessor */
return; /* return with no deletion of item */
}
}
free(*item); /* deletion of item */
}