[C 구현] 이분 탐색 트리

Binary Search Tree는 값 삽입을 시도 할 때, 그 값이 있어야 할 위치를 방문하는 노드와의 대소 구분에 따라 재량껏 위치를 찾아간 뒤 자리를 잡는 자동 균형 유지 트리이다.

typedef struct _bstnode{
	int item;
	struct _bstnode *left;
	struct _bstnode *right;
} BSTNode;

기본적으로 구현은 이렇게 이루어진다. 한 노드는 내용을 담을 item, 그리고 좌 우를 가리킨다.

void insertBSTNode(BSTNode **node, int value){
	if (*node == NULL)
	{
		*node = malloc(sizeof(BSTNode));

		if (*node != NULL) {
			(*node)->item = value;
			(*node)->left = NULL;
			(*node)->right = NULL;
		}
	}
	else
	{
		if (value < (*node)->item)
		{
			insertBSTNode(&((*node)->left), value);
		}
		else if (value >(*node)->item)
		{
			insertBSTNode(&((*node)->right), value);
		}
		else
			return;
	}
}

그리고 새로운 노드를 삽입하는 코드이다.

void removeAll(BSTNode **node)
{
	if (*node != NULL)
	{
		removeAll(&((*node)->left));
		removeAll(&((*node)->right));
		free(*node);
		*node = NULL;
	}
}

시연 코드 작성 특성 상 한 개 제거 말고 전체 제거 형태만 고려되었다.

---

Quest #1 : Level order Traversal, 층 단위 순회 하기

층 단위 순회를 queue를 통해 구현하는 과제이다. 위의 트리에 대해서의 결과는 "20, 15, 50, 10, 18, 25, 80" 이다.
보면은 생각 해 볼 수 있는 것이, 한번 출력(액션)을 하고, 해당 노드 이후의 후속 노드를 고려해야하는 점에 초점을 맞췄다.

즉, 20, 15, 50만 봐도 뭘 해야 할지 조금은 보였다. 어쨌든 자기 자신 - 왼쪽 - 오른쪽 이렇게 보면 된다.

void levelOrderTraversal(BSTNode* root)
{
	Queue q;
	q.head = NULL;
	q.tail = NULL;

	enqueue(&q.head, &q.tail, root);
	while (isEmpty(q.head) == 0)
	{
		BSTNode* poped = dequeue(&q.head, &q.tail);
		printf("%d ", poped->item);
		if(poped->left != NULL)
			enqueue(&q.head, &q.tail, poped->left);

		if(poped->right != NULL)
			enqueue(&q.head, &q.tail, poped->right);
	}

 

 

Quest #2 : inorder traversal : 중위 순회 하기

stack을 이용한 중위 순회 구현이다. 위의 주어진 트리에서 "10, 15, 18, 20, 50" 의 출력을 기대한다.
루트에서부터 시작해서, 왼쪽을 타고타고타고 내려간다. 그리고 pop-printf 하면서 오른쪽을 타고 내려간다.

이렇게 고려하면, 중위 순회의 내용대로 정직하게 구현 할 수 있었다.
예제 출력에서 루트 노드인 20이 어느 번째쯔음 출력 되었는가를 생각하면 금방 감을 잡을 수 있을 것이다.

void inOrderTraversal(BSTNode *root)
{
	Stack sta;
	sta.top = NULL;

	while(root != NULL)
	{
		push(&sta, root);
		root = root->left;
	}

	while (isEmpty(&sta) == 0)
	{
		BSTNode *poped = pop(&sta);

		printf("%d ", poped->item);
		if(poped->right != NULL)
			push(&sta, poped->right);

	}
}

Quest #3 : preorder traversal : 전위 순회 하기

이건 또 뭐야? 오늘도 평화로운 정글스탄.
이번에는 아래 주어진 트리에 대해 전위 순회를 요구하는 과제가 주어졌다.

이 트리가 주어질때 기대되는 출력은 20, 15, 10, 18, 50, 25, 80이다.
우선 자기 자신에 대한 할 일을 끝내고, poped->right 부터 스택에 넣고 나서 left가 이뤄질 때 전체적인 흐름에 맞아떨어진다.

void preOrderIterative(BSTNode *root)
{
	Stack sta;
	sta.top = NULL;

	push(&sta, root);

	while (isEmpty(&sta) == 0)
	{
		BSTNode *poped = pop(&sta);

		printf("%d ", poped->item);
		if(poped->right != NULL)
		push(&sta, poped->right);

		if(poped->left != NULL)
			push(&sta, poped->left);
	}

}

 

Quest #4 : postorder traversal : 후위 순회를 스택 1개로 수행하기

처음엔 무슨 말을 하고 싶은건가 이해를 못했는데 가만보니 뒷 문제랑 유사한 점이 많았다. 뒷 문제는 다음 글에서 설명하겠다.

이제보니 후위순회에 대한 구현을 스택 1개로 이루는 내용이었다.
나중에 보니 스택 2개에서 더 감을 못잡았는데, 결국 스택 2개가 더 쉽고 얘가 더 빡빡한 조건이었음을 알았다.

최근 코어타임 때 스택과 재귀에 대한 관계에 대해 간략하게 설명해준 학우가 있었다. 이 학우의 이야기를 들을때마다 저릿저릿 했던 것이 아 이걸 푸는데 무조건 도움되겠다 해서 주의깊게 들으려 했다. 뭘 말했는지 기억은 안나는데 이 문제에 대한 많은 무의식적 힌트를 제공해주었다.

이 트리에서, 기대되는 호출 순서는 "10, 18, 15, 25, 80, 50, 20"이다.

어쨌든 스택은 1개이고, 뭔가 제대로 생각을 전개하려면 스택 1개로는 모자랐다. 그래서 스택 1개의 대역을 해줄 코드를 생각해보니 재귀적인 생각을 고려 해볼 수 있었다. 물론 함수를 한 개 더 만들어야만 했지만.. 어쨌든 스택은 1개만 썼으니까?

나또한 스택 1개에 넣고 꺼낼때마다 좌우 자식을 체크하거나, 수가 올라가는지, 아까 한번 봤던 숫자인건지에 대한 플래그(혹은 인디케이터)를 생각하는 기법을 고려했는데, 뭔가 그 특유의 복잡함에도 불구하고 반례를 만들라면 순식간에 만들 수 있을 법 했다. 그래서 좀 더 획기적인 무언가가 필요했다.

void postOrderIterativeS1(BSTNode *root)
{
	if(root == NULL)
		return;

	Stack stack;
	stack.top = NULL;

	push(&stack, root);

	if(root->right != NULL)
		postOrderIterativeSub(&stack, root->right);

	if(root->left != NULL)
		postOrderIterativeSub(&stack, root->left);
	


	int isContinue = 1;

	while (isContinue)
	{
		BSTNode *poped = pop(&stack);
		if(poped != NULL)
		{
			printf(" %d", poped->item);
		}
		else
		{
			isContinue = 0;
		}
	}

}

이게 원형 코드이고, 여기서 재귀로 호출되는 postOrderIterativeSub은 아래에 있다.

 

void postOrderIterativeSub(Stack * str, BSTNode *deNode)
{
	push(str, deNode);
	if(deNode->left == NULL && deNode ->right == NULL)	
		return;

	if(deNode->right != NULL)
		postOrderIterativeSub(str, deNode->right);

	if(deNode->left != NULL)
		postOrderIterativeSub(str, deNode->left);


}

출력 상태를 보면 한 쪽 서브트리에 대한걸 완전히 마무리 한 다음에 다음 서브트리에 대해 임하고 있다. 이 점에서 상당히 고민이 많았던 것 같다. 그래서 한 서브트리를 아예 파고 들어 갈 수 있는 재귀함수를 고안한 것이다. 그리고 기존 함수에 그걸 그대로 진행 할 수가 없어 따로 빼낸 모양이 이 것이다.

후일담으로 이거 재귀로 푸는게 아니라고 하더라. 그래서 내심 문제 조건에 섭섭했다.

Quest #5 : 후위 순회를 스택 두 개로 하기

오히려 이 문제는 #4보다 쉽다. 제약 조건이 스택 1개에서 2개로 바뀌었다.

한 아이템을 꺼내서 해당 아이템이 가지고 있는 L R을 차례로 푸시한다. 스택인걸 고려한 작동이다. 그리고 마지막에 자기 자신은 출력 되어야겠지만 진짜 그대로하면 의도랑 다소 달라지므로, 좌우를 살펴봤다는 의미에서 두번째 스택으로 옮겨준다.

void postOrderIterativeS2(BSTNode *root)
{
	Stack s1;
	Stack s2;

	s1.top = NULL;
	s2.top = NULL;

	push(&s1, root);

	while (isEmpty(&s1) == 0)
	{
		BSTNode* poped = pop(&s1);

		if(poped->left != NULL)
			push(&s1, poped->left);

		if(poped->right != NULL)
			push(&s1, poped->right);

		push(&s2, poped);
	}

	while (isEmpty(&s2) == 0)
	{
		BSTNode* poped = pop(&s2);
		printf("%d ", poped->item);
	}

}

즉, 좌우를 살펴보는 것과 출력하는 것 사이에서 Stack 을 배치하여 경유하게 끔 했다. 이게 더 깔끔한 구현을 가능하게 한듯.