포스팅 목적
이진 트리를 공부하시는 분들께 도움이 되기 위함입니다. 실질적인 예시들과 함께 이진트리에 대한 이해를 돕고자 합니다.
1. 후위 순회 (postorder)
이진 트리(binary tree)의 후위 순회 알고리즘이 사용될 수 있는 대표적인 예는 특정 디렉토리(directory)의 용량 계산이다. 단, 이진 트리이기 때문에 특정 디렉토리(=폴더)의 서브 디렉토리의 개수는 2개 이하로만 존재해야 한다. 삼진 트리(ternary tree)였다면 서브 디렉토리는 총 3개까지 존재할 수 있다.
1.1 디렉토리의 용량 계산
디렉토리의 용량 계산을 위해서는 어떤 알고리즘이 사용되야하는가를 먼저 고민해보자. 생각을 할 때 구체적인 상황을 두고 예시를 들어보면 이해가 빠르다. 현재 사용하는 컴퓨터에 datastructure
라는 디렉토리가 있다고 가정해보자. 이 datastructure
디렉토리 내부에는 stack
, queue
라는 서브 디렉토리가 존재한다.
datastructure/stack
datastructure/queue
이 때datastructure
디렉토리의 크기를 구하려면 어떻게 해야할까?
서브 디렉토리인 stack
디렉토리와 queue
디렉토리의 크기를 각 계산하여 합하면 datastructure
폴더의 크기를 계산할 수 있다. 서브 디렉토리의 크기를 더해 현재 디렉토리의 크기를 계산한다는 아이디어를 생각해보면 서브 디렉토리의 크기를 먼저 계산하는데, 바로 이러한 특징 때문에 후위 순회 알고리즘을 사용해야 한다.
1.2 코드
후위 순회:: 트리를 탐색할 때 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문하는 순회 알고리즘을 일컫는 말이다. 후위 순회 알고리즘은 아래와 같다.
위와 같은 후위 순회를 사용하여 디렉토리 크기를 계산하는 코드를 작성해보도록 한다. 순환 호출되는 함수가 용량을 반환하도록 만들어줘야 한다.
2. 이진 트리의 높이 구하기
트리의 높이를 구할 때의 핵심 개념은 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이를 비교하여 더 큰 쪽을 택한다는 것이다. 그렇다면 우리에게 필요한 건 서브트리의 높이와 오른쪽 서브트리의 높이다. 높이는 어떻게 구할 수 있을까?
2.1 코드
위 코드를 이해해보자. 순환 알고리즘이 적용된 코드를 작성하거나 읽을 때는 탈출 조건 보다는 순환호출 되는 부분을 먼저 살펴봐야 한다. 호출되는 부분은 int left_h = get_height(root->left)
, int right_h = get_height(root->right)
이 두 부분이다.
위 순환 호출되는 코드로 왼쪽 서브트리의 높이 left_h
와 오른쪽 서브트리의 높이 right_h
를 구하기 위해 순환 함수로 각 서브트리의 끝(단말 노드)까지 방문할 수 있다. 방문 순서는 get_height(root->left
가 먼저 호출되었으므로 먼저 왼쪽 서브트리의 단말노드까지 방문할 것이고 탈출 조건 if (!root)
를 만나면서 왼쪽 서브트리를 빠져나오면 오른쪽 서브트리로 진입한다(get_height(root->right)
.
다음으로 탈출되는 조건을 살펴보자. 위 코드에서 상정한 탈출 조건은 단말노드를 만났을 때다. 단말노드란 자식이 없는 노드를 뜻한다. 그렇다면 단말노드인 것은 어떻게 알 수 있을까?
자식이 없는 노드가 단말노드이므로 아래와 같은 두 조건을 생각해볼 수 있다.
root == NULL
의 의미를 좀 더 풀어서 설명하자면 자식 노드가 있나 살펴보려 서브 트리를 방문했는데 아무것도 발견할 수 없었다라는 의미다. 위 코드는 이 조건을 적용한 코드다.
마지막으로 ger_height
함수에서 맨 아래 리턴하는 부분을 살펴보자. **왜 1을 더해서 리턴해주는 걸까?**라는 의문이 든다면 그 이전에 어떤 작업을 시행했는지를 살펴보자. 특히 첫번째 완전한 순환이 끝났을 때를 생각해보자. 순환을 계속하면서 각 서브 트리의 끝까지 방문한 상태(정확히는 오른쪽 서브트리를 끝까지 방문한 상태)에서 한 단계 더 내려가 root == NULL
이라는 탈출 조건을 만났다. 그렇게 탈출 조건을 만나 빠져나오면 마지막 리턴문을 만나게 되는데 이때의 상황은 더 이상의 자식노드, 서브트리가 없는 상황이므로 리턴문에 있는 left_h
와 right_h
는 둘 다 0이 될 것이다.
위 상황에 대한 결론을 내려보면 나에게 자식노드, 서브트리는 존재하지 않지만 적어도 나는 존재한다는 것을 입증했다는 것이다. 따라서 나 자신을 하나의 개수로 칠 수 있다. 그래서 1을 더하는 것이다. 1을 더한 후에는 왼쪽 서브트리와 오른쪽 서브트리의 높이 중 더 큰 값을 택하기만 하면 되는 것이다.
순환의 개념을 접할 때는 추상적으로 이해하면 이해에 좀 더 도움이 된다. 큼지막한 매커니즘, 예를 들어 왼쪽 서브트리 높이 구하기, 오른쪽 서브트리 높이 구하기들이 대략 어떤 순서로 실행되는지를 파악하고 리턴은 언제 되고 탈출 조건은 어떻게 되는지를 살펴보는 것이다. 실행 흐름을 하나 하나 다 따지려 하기보다는 먼저 이렇게 개념적으로 접근한 후에 세부적으로 이해하려고 하면 좀 더 편하다.
3. 이진 트리의 단말 노드 개수 구하기
2번에서 살펴본 알고리즘을 그대로 적용하면 의외로 쉽게 구할 수 있다. 아래의 코드만 보고 개념을 이해하도록 해보자.
3.1 코드
위 코드의 탈출 조건은 if (root->left == NULL && root->right == NULL)
다. 즉 자식노드 혹은 서브트리가 존재하지 않을 때가 탈출 조건이다. 의미는 자식 노드는 존재하지 않지만 내가 존재한다는 건 적어도 증명했으니 난 1개로 셀 수 있다는 것이다. 첫번째 if (!root)
의 조건은 누군가 이 함수를 사용할 때 존재하지 않는 노드를 매개변수로 넘겼을 때를 대비하기 위함이다 .오류를 방지하는 용도로서의 의미를 가진 조건이다. 이 조건을 탈출 조건으로 쓸 수 없는 것은 이 조건 만으로는 단말 노드의 여부를 증명할 수 없기 때문이다. 아무것도 존재하지 않으므로 개수를 셀 수 없다.
Originally published at gist.github.com.