RB RedBlack::balance (RB &tree,RB &nodo,string chiave) {
tree = insert (tree,nodo,chiave);
RB root = new RedBlack ();
root = tree;
// se è radice, colore è nero.
if (nodo == root) {
nodo->parent = NULL;
nodo->colore = black;
}
else nodo->colore = red;
// ripristina lo stack per trovare il padre
erase ();
RB y = new RedBlack ();
if (nodo->parent != NULL) {
while ((nodo->parent->colore == red) && (nodo->parent != NULL)) { // e se il colore del padre è ROSSO
if (nodo->parent == nodo->parent->parent->left) {
y = nodo->parent->parent->right;
if (y->colore == red) {
nodo->parent->colore = black;
y->colore = black;
nodo->parent->parent->colore = red;
nodo = nodo->parent->parent;
} // fine IF
else if (nodo == nodo->parent->right) {
nodo = nodo->parent;
left_rotate (nodo,tree); // albero nodo
nodo->parent->colore = black;
nodo->parent->parent->colore = red;
//right_rotate; // albero padre padre nodo
} // fine ELSE IF
} // if IF GENERALE
// -------------------------------------------------------
else {
y = nodo->parent->parent->left;
if (nodo == nodo->parent->left) {
nodo = nodo->parent;
left_rotate (nodo,tree); // albero nodo
nodo->parent->colore = black;
nodo->parent->parent->colore = red;
// right_rotate; // albero padre padre nodo
} // fine IF
} // fine ELSE
} // fine WHILE
return tree;
} // fine if NODO PARENT NULL
else return tree;
/*
RB y = new RedBlack();
while (nodo->parent != NULL) { // e se il colore del padre è ROSSO
if (nodo->parent == nodo->parent->parent->left) {
y = nodo->parent->parent->right;
if (y->colore == red) {
//nodo->parent->colore = black;
y->colore = black;
nodo->parent->parent->colore = red;
nodo = nodo->parent->parent;
} // fine IF
else if (nodo == nodo->parent->right) {
nodo = nodo->parent;
left_rotate (nodo,tree); // albero nodo
//nodo->parent->colore = black;
nodo->parent->parent->colore = red;
//right_rotate; // albero padre padre nodo
} // fine ELSE IF
} // if IF GENERALE
// -------------------------------------------------------
else {
y = nodo->parent->parent->left;
if (nodo == nodo->parent->left) {
nodo = nodo->parent;
left_rotate (nodo,tree); // albero nodo
//nodo->parent->colore = black;
//nodo->parent->parent->colore = red;
// right_rotate; // albero padre padre nodo
} // fine IF
} // fine ELSE
} // fine WHILE
}*/
return tree;
}
// inserisco il termine all' interno dell' albero
RB RedBlack::insert(RB &tree, RB &nodo, string chiave) {
// inserisci il termine
if (tree == NULL) {
nodo = new RedBlack();
nodo->parola = chiave;
nodo->left = NULL;
nodo->right = NULL;
nodo->parent = padre.back(); // il padre è l' ultimo nodo esaminato
// tree = nodo;
return nodo;
}
// determina la posizione del nodo
else if (chiave < tree->parola) {
padre.push_back (tree); // salva il nodo appena esaminato per trovare il padre
return insert (tree->left,nodo,chiave);
}
else if (chiave > tree->parola) {
padre.push_back (tree);
return insert (tree->right,nodo,chiave);
}
}