#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "tools.h"


b_s_t insert_node(b_s_t bst, char* key, void* vp)
{
	if (!bst)
	{
		bst = (b_s_t)malloc(sizeof(struct b_s_t_node_str)); //既然为空所以要生成一个
		bst->data = _strdup(key);
		bst->vp = vp;
		bst->left = NULL;
		bst->right = NULL;
	}
	else
	{
		if (strcmp(key, bst->data) < 0)
		{
			bst->left = insert_node(bst->left, key, vp);
		}
		else if (strcmp(key, bst->data) > 0)
		{
			bst->right = insert_node(bst->right, key, vp);
		}
	}
	return bst;
}

b_s_t find(b_s_t bst, char* key)
{

	b_s_t tmp_bst = bst;

	while (tmp_bst)
	{
		if (strcmp(key, tmp_bst->data) > 0)
		{
			tmp_bst = tmp_bst->right;
		}
		else if (strcmp(key, tmp_bst->data) < 0)
		{
			tmp_bst = tmp_bst->left;
		}
		else
		{
			return tmp_bst;
		}
	}
	return NULL;
}

b_s_t find_min(b_s_t bst)
{
	if (!bst)
	{
		return NULL;
	}
	else if (!bst->left)
		return bst;
	else
		return find_min(bst->left);
}

b_s_t find_max(b_s_t bst)
{
	if (!bst)
		return NULL;
	else if (!bst->right)
		return bst;
	else
		return find_max(bst->right);
}

b_s_t delete_node(b_s_t tree, char* key)
{

	b_s_t tmp_bst = tree;
	b_s_t temp;

	if (!tmp_bst)
	{
		printf("Not Found\n");
	}
	else
	{
		if (strcmp(key, tmp_bst->data) < 0)
		{
			tmp_bst->left = delete_node(tmp_bst->left, key);
		}
		else if (strcmp(key, tmp_bst->data) > 0)
		{
			tmp_bst->right = delete_node(tmp_bst->right, key);
		}
		else
		{
			if (tmp_bst->left && tmp_bst->right)
			{
				temp = find_min(tmp_bst->right);
				tmp_bst->data = temp->data;
				tmp_bst->right = delete_node(tmp_bst->right, temp->data);
			}
			else
			{
				temp = tmp_bst;
				if (tmp_bst->left)
				{
					tmp_bst = tmp_bst->left;
				}
				else if (tmp_bst->right)
				{
					tmp_bst = tmp_bst->right;
				}
				else
				{
					tmp_bst = NULL;
				}
				free(temp);
			}
		}
	}
	return tmp_bst;
}