#include "bst.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
/* structure from which binary search tree consists of */
/* Initializes binary search tree.
* Parameter root is pointer to pointer which points to the tree's root.
*/
void bst_init(bst_node_t **root){
bst_node_t *newNode = malloc(sizeof(bst_node_t));
newNode->value = NULL;
newNode->parent = NULL;
newNode->left = NULL;
newNode->right = NULL;
*root = newNode;
}
/* Insert key to binary search tree.
* Parameter root is pointer to pointer which points to the tree's root.
* value is the string which is put to the tree (key), you're not supposed to
* make copy of the string.
* Returns 0 if succesful, -1 otherwise
*/
int bst_insert(bst_node_t **root, char *value){
bst_node_t *newNode = malloc(sizeof(bst_node_t));
newNode->left = NULL;
newNode->right = NULL;
newNode->value = value;
if((*root)->value == NULL){
// printf("Empty tree, making new root\n");
newNode->parent = NULL;
*root = newNode;
return 0;
}
bst_node_t *current = *root;
while(1){
int comparison = strcmp((current->value),value);
// printf("Comparing %s and %s\n", current->value, value);
if(comparison < 0){ //Current->value < value, mennaan oikealle
if(current->right == NULL){
// printf("Inserted right\n");
current->right = newNode;
newNode->parent = current;
return 0;
}
else {
current = current->right;
continue;
}
}
else if(comparison > 0){ //Current->value > value, mennaan vasemmalle
if(current->left == NULL){
current->left = newNode;
newNode->parent = current;
// printf("Inserted left\n");
return 0;
}
else {
current = current->left;
continue;
}
}
else{ // current->data == value, virhe
// printf("Error\n");
return -1;
}
}
}
void replaceNode(bst_node_t* node1, bst_node_t* node2){
if(node1->parent != NULL){
if(node1->parent->left == node1){
node1->parent->left = node2;
}
else{
node1->parent->right = node2;
}
}
else{
if(node2 != NULL) node2->parent = NULL;
}
if(node1->left != node2 && node2 != NULL){
node2->left = node1->left;
if(node1->left != NULL){
node1->left->parent = node2;
}
}
if(node1->right != node2 && node2 != NULL){
node2->right = node1->right;
if(node1->right != NULL){
node1->right->parent = node2;
}
}
}
/* Delete key from binary search tree.
* Parameter root is pointer to pointer which points to the tree's root.
* Node is pointer to node which needs to be removed.
* Returns pointer to value of the removed node if succesful, null otherwise.
*/
char *bst_delete(bst_node_t **root, bst_node_t *node){
char* value = node->value;
bst_node_t* newRoot = NULL;
int changingRoot = 0;
if(node == *root) changingRoot = 1;
if(node->left == NULL && node->right == NULL){ //No children
replaceNode(node,NULL);
if(changingRoot == 1){
(*root)->value = NULL;
return value;
}
free(node);
}
else if(!(node->left != NULL && node->right != NULL)){ // One child
if(node->left != NULL){
newRoot = node->left;
replaceNode(node,node->left);
free(node);
}
else{
newRoot = node->right;
replaceNode(node,node->right);
free(node);
}
}
else { //Two children
bst_node_t* successor = bst_next(node);
replaceNode(node,successor);
if(node->left != NULL){
newRoot = node->left;
replaceNode(node,node->left);
free(node);
}
else{
newRoot = node->right;
replaceNode(node,node->right);
free(node);
}
}
if(changingRoot == 1){
*root = newRoot;
}
return value;
}
/* Find key from bst (binary search tree).
* Parameter root is pointer to the trees root.
* value is the key which we are searching
* Returns pointer to the node which has the same value when compared using
* strcmp.
*/
bst_node_t *bst_find(bst_node_t *root, char *value){
bst_node_t* current = root;
while(1){
// printf("Comparing %s and %s\n", current->value, value);
int comparison = strcmp((current->value),value);
if(comparison < 0){ //Current->data < value, mennaan oikealle
if(current->right == NULL){ //Not found
return NULL;
}
else {
current = current->right;
continue;
}
}
else if(comparison > 0){ //Current->data > value, mennaan vasemmalle
if(current->left == NULL){ //Not found
return NULL;
}
else {
current = current->left;
continue;
}
}
else{ // current->data == value, loytyi
return current;
}
}
}
/* Find next node from the node passed in parameter (meaning that the value
* of the node pointed by parameter node is smaller than the value of the
* successor but there are no nodes in bst that have value smaller than
* successor and greater than node pointed by parameter node)
* Parameter node gives pointer to node which successor we are finding of.
* Returns pointer to successor node.
*/
bst_node_t *bst_next(bst_node_t *node){
if(node->right == NULL){ //Mennaan ylos, kunnes siirrytaan oikealle
bst_node_t* current = node;
while(1){
bst_node_t* parentNode = current->parent;
if(parentNode == NULL){
return NULL;
}
if(parentNode->left == current){
return parentNode;
}
else{
current = parentNode;
}
}
}
else{ //Yksi oikealle, ja sitten vasemmalle niin pitkalle, kuin paasee
bst_node_t* current = node->right;
while(current->left != NULL){
current = current->left;
}
return current;
}
}
/* Find node that has minimal value in bst.
* Parameter root gives pointer to the root of the tree.
* Returns pointer to node that has minimal value in bst.
*/
bst_node_t *bst_find_min(bst_node_t *root){
//Mennaan vasemmalle niin pitkalle kuin paasee
bst_node_t* current = root;
while(current->left != NULL){
current = current->left;
}
return current;
}
/* Find node that has maximal value in bst.
* Parameter root gives pointer to the root of the tree.
* Returns pointer to node that has maximal value in bst.
*/
bst_node_t *bst_find_max(bst_node_t *root){
//Mennaan oikealle niin pitkalle kuin paasee
bst_node_t* current = root;
while(current->right != NULL){
current = current->right;
}
return current;
}