//If it has a left son, we look for the node that's more to the right from his right son.
actualNode = root->leftSon;
while (actualNode->rightSon != NULL) {
//While it has a right son...
actualNode = actualNode->rightSon;
}
//Once this finished, actualNode is going to point to a node that it hasn't a right son (it's going to be the bigger from the original actualNode's left son).
}
boolSplayTree::study_right_son(Node* &actualNode, int element) {
//If it has not a right son, we have a place to put it.
if (actualNode->rightSon == NULL) {
insert_to_right_son(actualNode, element);
returntrue;
}
//If not, we change the node we are studying. Now it's going to be his right son.
actualNode = actualNode->rightSon;
returnfalse;
}
boolSplayTree::study_left_son(Node* &actualNode, int element) {
//If the node we are evaluating has a bigger value than the one we want to introduce, we study his right son.
if (actualNode->leftSon == NULL) {
insert_to_left_son(actualNode, element);
returntrue;
}
//If not, we change the node we are studying. Now it's going to be his left son.
actualNode = actualNode->leftSon;
returnfalse;
}
voidSplayTree::insert_to_right_son(Node* &actualNode, int element) {
actualNode->rightSon = new Node;
actualNode->rightSon->rightSon = NULL;
actualNode->rightSon->leftSon = NULL;
actualNode->rightSon->father = actualNode;
actualNode->rightSon->value = element;
floation(actualNode->rightSon);
}
voidSplayTree::insert_to_left_son(Node* &actualNode, int element) {
Described here: http://www.ics.uci.edu/~dan/class/165/notes/splay.html
*/
voidSplayTree::L(Node* n) {
Node* aux;
updateParents(n, aux);
aux->rightSon = n->leftSon;
if (n->leftSon != NULL) {
aux->rightSon->father = aux;
}
n->leftSon = aux;
updateGrandpa(n, aux);
}
/*
Represents a R rotation.
Described here: http://www.ics.uci.edu/~dan/class/165/notes/splay.html
*/
voidSplayTree::R(Node* n) {
Node* aux;
updateParents(n, aux);
aux->leftSon = n->rightSon;
if (aux->leftSon != NULL) {
aux->leftSon->father = aux;
}
n->rightSon = aux;
updateGrandpa(n, aux);
}
boolSplayTree::remove_node(Node* &actualNode) {
floation(actualNode);
//If it doesn't have a left son.
if (root->leftSon == NULL) {
if (root->rightSon != NULL) root->rightSon->father = NULL;
root = root->rightSon;
returntrue;
}
//If it has a left son, we look for the node that's more to the right from his right son.
get_biggest(actualNode);
//Once this finished, actualNode is going to point to a node that it hasn't a right son (it's going to be the bigger from the original actualNode's left son).
//Root's right son, if it existed, it's going to be new actualNode's right son.
if (root->rightSon != NULL) {
actualNode->rightSon = root->rightSon;
root->rightSon->father = actualNode;
}
//Root's left son will be the new root.
root = root->leftSon;
root->father = NULL;
returntrue;
}
boolSplayTree::insert_if_empty(int element) {
//We create a node in the root. We put the correct values in every field ( references=NULL and value=element).
root = new Node;
root->rightSon = NULL;
root->leftSon = NULL;
root->father = NULL;
root->value = element;
//There's no need to fload, because the tree has only one node.
//Everything worked correctly, so we return true.
returntrue;
}
boolSplayTree::insert_if_not_empty(int element) {
/*Pointer we are going to use to move through the tree. Points to the node we are studying every moment.
It's going to start pointing to the root.*/
Node* actualNode;
actualNode = root;
//This loop won't stop until a return statement is executed.
while (true) {
if (actualNode->value == element) {
//Insertion didn't work correctly, we've found the element that we are trying to insert. We return false.
floation(actualNode);
returnfalse;
}
elseif (actualNode->value < element) {
//If the node we are evaluating has a lower value than the one we want to introduce, we study his right son.
if (study_right_son(actualNode, element)) returntrue;
}
else {
//If the node we are evaluating has a bigger value than the one we want to introduce, we study his left son.
if (study_left_son(actualNode, element)) returntrue;