#include "class_header.h"
PILA padre; // stack globale per trovare nodo padre
// inizializza albero vuoto
/*RB RedBlack::build (RB tree) {
tree = new RedBlack;
tree = NULL;
tree->left = NULL;
tree->right = NULL;
return tree;
};*/
RedBlack::RedBlack () {
left = right = parent = NULL;
colore = red;
}
// pulisco lo stack ed inserisco una sentinella
void RedBlack::erase () {
padre.clear();
padre.push_back (NULL);
};
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 ();
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,root); // 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,root); // 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);
}
}
RB RedBlack::left_rotate (RB &nodo,RB& root) {
RB y = new RedBlack ();
y = nodo->right;
nodo->right = y->left;
if (y->left != NULL) {
y->left->parent = nodo;
y->parent = nodo->parent;
if (nodo->parent == NULL) root = y;
else if (nodo == nodo->parent->left) nodo->parent->left = y;
else nodo->parent->right = y;
y->left = nodo;
nodo->parent = y;
} // fine IF
return nodo;
}
// stampa l' albero
void RedBlack::write (RB tree,int i) {
if (tree != NULL) {
write (tree->right,i+1);
for (int j = 1; j <= i; j++) cout << " ";
cout << tree->parola << endl;
write (tree->left,i+1);
}
}
