[Go] go를 향한 여행 - 이진트리 비교

go를 향한 여행을 따라가던 중, 이진트리를 비교하는 문제를 만났다.

문제

문제를 읽어보았을 때, Tree를 이해하고자 하였고, 이 사이트에서 구조를 파악할 수 있었다.

Tree는 주어진 수의 배수를 10개의 값으로 갖는 트리를 생성하는 New와 트리 구조를 출력하는 String, 삽입하는 insert로 되어있었다.

나는 해당 함수만을사용하여 문제를 풀어야한다고 생각했었고, string의 값을 channel에 받아 문자열 비교로 접근하였다. 하지만, 삽입되는 값은 random이었고, 문자열의 값이 다를 수 밖에 없었다.

walk함수는 일반적으로 트리를 순회 탐색하여 값을 저장하는 기능을 수행하였고, 재귀적으로 탐색하는 기능으로 다시 구현하여 사용하였다.

아래에 그 코드가 있다.

코드

package main

import "golang.org/x/tour/tree"
import "fmt"

// Walk walks the tree t sending all values
// from the tree to the channel ch.
func Walk(t *tree.Tree, ch chan int) {
	if t != nil {
		Walk(t.Left, ch)
		ch <- t.Value
		Walk(t.Right, ch)
	}
}

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch := make(chan int)
	go Walk(t1, ch)
	
	ch2 := make(chan int)
	go Walk(t2, ch2)
	
	
	for i := <- ch; i < 10; i++ {
	 	d := <-ch2
		if i != d {
			fmt.Println(i)
			fmt.Println(d)
			return false
		}
	}
	return true
}

func main() {
	fmt.Println(Same(tree.New(1), tree.New(1)))
}

same함수를 구현하기 위해 ch1을 range로 접근하여 찾고 ch2에서는 바로 값을 빼내어 비교하였다.

참 결과

false 결과

다만 위의 방식은 for문에서 애초에 개수를 지정하고 있어서 좋은 방식은 아니라고 생각한다.

개선 코드

// Same determines whether the trees
// t1 and t2 contain the same values.
func Same(t1, t2 *tree.Tree) bool {
	ch := make(chan int)
	go Walk(t1, ch)
	defer close(ch)
	
	ch2 := make(chan int)
	go Walk(t2, ch2)
	
	
	for i :=  range ch {
	 	d := <-ch2
		if i != d {
			fmt.Println(i)
			fmt.Println(d)
			return false
		}
	}
	return true
}

코드의 이유

close를 사용한이유
range for문의 경우 채널이 clsoe되기 전까지 계속 값을 추출한다.
close가 없다면 빈 channel에서 값을 빼오려고 하기 때문에

이런 에러가 발생한다.

defer를 사용한 이유
만약 defer를 사용하지 않았다면, 이러한 에러를 만나게 된다.

main goroutine에서 channel을 닫은 상태에서 해당 channel에 값을넣으려고 하기 때문에 모든처리가 끝나고 동작하는 defer를 적용하였다.

true가 출력된 이유
타이밍이 좋다면 channel에 넣기전 range에서 버퍼가 비었다 생각하며 for문 내에 들어가지 않고, 종료될 수 있지만 대부분 에러를 발생시킨다.
즉, channel에 아무런 값이 들어가지 않았고 for문을 돌지 않았으니, true를 바로 출력한 것이고, 에러가 발생한 것은 그 사이에 goroutine에서 값을 삽입하고 있기 떄문이다.