BST

binary serach tree (이진 탐색 트리)

• 모든 원소는 서로 다른 유일한 키를 갖는다.
• 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.
• 오른쪽 서브 트리에 있는 원소의 키들은 그 루투의 키보다 크다.
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

삭제연산!

BSTNode*		findMax(BSTNode* rootNode)
{
	if (rootNode == NULL)
		return (NULL);
	else if (rootNode->rightNode == NULL)
		return (rootNode);
	else
		return (findMax(rootNode->rightNode));
}

BSTNode*		deleteBSTNode(BSTNode* rootNode, BSTNode element)
{
	if (rootNode == NULL)
		return (NULL);
	if (element.data < rootNode->data)
		rootNode->leftNode = deleteBSTNode(rootNode->leftNode, element);
	else if (element.data > rootNode->data)
		rootNode->rightNode = deleteBSTNode(rootNode->rightNode, element);
	else //element.data == rootNode.data 찾은경우
	{
		if (rootNode->leftNode && rootNode->rightNode) // 자식이 2개인경우
		{
			BSTNode*	canNode;
			canNode = findMax(rootNode->leftNode); //left에서 가장 큰 값 찾기
			rootNode->data = canNode->data;
			rootNode->leftNode = deleteBSTNode(rootNode->leftNode, *canNode);
		}
		else //자식이 1개 이하
		{
			BSTNode*	temp;
			temp = rootNode;
			if (rootNode->leftNode == NULL)
				rootNode = rootNode->rightNode;
			else if (rootNode->rightNode == NULL)
				rootNode = rootNode->leftNode;
			free(temp);
		}
	}
	return (rootNode);
}