Мой алгоритм работает неправильно, если удалять несбалансированный корневой элемент, потому что в этом случае не происходит балансировка, так как у него нет родителей. Делал вроде по классическому алгоритму, но не уверен что манипулирую правильно указателями при замещении... Хочется сделать элегантно, без многочисленных условий.
Код:
// удаление узла из дерева
TTree removeNode(TTree T, int key, bool* reduced) {
TTree Q;
TKey bkey;
if (T == NULL)
return NULL;
if (key == T->key) {
if (T->left == NULL) {
Q = T->right;
_release(T);
*reduced = TRUE;
return Q;
}
else if (T->right == NULL) {
Q = T->left;
_release(T);
*reduced = TRUE;
return Q;
}
// здесь идет замена. в зависимости баланса удаляемого узла, выбирается симметричный ей узел в левом или правом поддереве
if (T->balance == L) {
Q = getRightNode(T->left);
bkey = Q->key;
Q->key = T->key;
T->key = bkey;
T->left = removeNode(Q, key, reduced);
T->balance = Q->balance;
return T;
}
else {
Q = getLeftNode(T->right);
bkey = Q->key;
Q->key = T->key;
T->key = bkey;
T->right = removeNode(Q, key, reduced);
T->balance = Q->balance;
return T;
}
}
if (key < T->key) {
T->left = removeNode(T->left, key, reduced);
if (*reduced == TRUE) {
switch (T->balance) {
case B:
T->balance = R;
*reduced = FALSE;
break;
case L:
T->balance = B;
break;
case R:
if (T->right->balance == L)
T = leftBigRot(T);
else
T = leftSmallRot(T);
T->balance = B;
};
}
}
if (key > T->key) {
T->right = removeNode(T->right, key, reduced);
if (*reduced == TRUE) {
switch (T->balance) {
case B:
T->balance = L;
*reduced = FALSE;
break;
case R:
T->balance = B;
break;
case L:
if (T->left->balance == R)
T = rightBigRot(T);
else
T = rightSmallRot(T);
T->balance = B;
};
}
}
return T;
}
День на это потратил, обидно не разобраться!
