자료구조(8) 트리

"트리"는 고급 자료구조로 구분이 된다. 그만큼 학습에 있어서 집중을 요한다. 특히 비선형 자료구조이기때문에 많이 다르게 느껴질 수도 있다!"

 

트리는 계층적 관계를 표현하는 자료구조이다!

 

자료구조! 하면 보통은 무엇인가를 저장하고 꺼내는 것이 전부인 것으로 이해하는 경우가 많다. 앞서 보인 선형 자료구조들은 이에 초점이 맞춰져 있었으니 무리도 아니다. 하지만 자료구조는 근본적으로 무엇인가를 "표현" 하는 도구이다.

 

트리는 데이터의 저과 삭제가 아닌 "표현"에 초점이 맞춰져 있다. 때문에 트리의 ADT를 다음과 같이 바라보면 안된다. "데이터의 저장, 검색 및 삭제가 용이하게 정의되어 있나요?" 대신 다음과 같이 바라봐야 한다.

"트리의 구조로 이뤄진 무엇인가를 표현하기에 적절히 정의되어 있나요?"

 

• 노드(Node) : 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소
• 간선(Edge) : 노드와 노드를 연결하는 연결선
• 루트 노드(root node) : 트리 구조에서 최상위에 존재하는 노드
• 단말 노드[잎사귀 노드] (terminal node) : 아래로 또 다른 노드가 연결되어 있지 않은 노드
• 내부 노드[비단말 노드] (internal node) : 단말 노드를 제외한 모든 노드로 루트노드도 포함!

 

• 부모노드 : 노드 A는 B, C, D의 부모 노드이다
• 자식노드 : 노드 B, C, D는 노드 A의 자식 노드이다
• 형제노드 : 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드이다

그런데 부모와 자식의 관계는 상대적이다. 따라서 노드 B는 노드 A의 자식 노드이지만, 동시에 다른 노드의 부모 노드가 되기도 한다.

조금 더 나아가서 조상, 후손의 관계도 있다. 특정 노드에 위치한 모든 노드를 가리켜 "조상 노드"라고 하고, 특정 노드의 아래에 위치한 모든 노드를 가리켜 "후손 노드"라 한다.

 

큰 트리에 속하는 작은 트리를 가리켜 "서브 트리"라 한다(큰 트리에서 가지치기된 트리들)

 

이진트리의 조건

• 루투 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.
• 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다.

• 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, "공집합" 노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

즉 이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브트리도 이진 트리어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다.(공집합포함) 이로인해 생각보다 이진 트리의 폭이 넓음을 알 수 있다. 따라서 이진 트리도 그 특성에 따라서 보다 세분화된다.

 

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 "레벨"이라 하고, 트리의 최고 레벨을 가리켜 "높이"라 한다

(위에서부터 레벨0부터 시작하는 관계로 최고의 레벨과 높이가 일치하기 때문에, 최고레벨을 높이라 하는것)

 

포화 이진 트리 : 모든 레벨에 공집합없이 꽉 차있는 이진트리

 

완전 이진 트리 : 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈없이 노드가 채워진 이진 트리를 뜻한다. 그리고 여기서 말하는 "차곡차곡 빈 틈없이 노드가 채워진 상태"의 의미는 다음과같다.

"노드가 위에서 아래로 그리고 왼쪽에서 오른쪽의 순서대로 채워졌다!"

 

이진 트리 역시 배열을 기반으로도, 연결 리스트를 기반으로도 구현이 가능하다. 그러나 트리를 표현하기에는

연결 리스트가 더 유연하다. 그러나 이진 트리라면, 특히 다음과 같은 특성을 갖는 완전 이진 트리라면 배열을 기반의 구현도 고려해 볼 만 하다

"트리가 완성 된 이후로부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다(힙+완전 이진 트리)"

 

배열은 분명 연결 리스트에 비해서 탐색이 매우 용이하고 또 빠르기 때문이다.

 

배열을 기반으로 이진 트리를 구현하려면 노드에 고유의 노드 번호(인덱스 값, 0은 빈공간)를 부여해야 한다.

 

데이터가 저장되는 배열의 위치는 노드 번호를 기준으로 결정된다.

 

             1

        2        3

   4       5

 

질문 : 인덱스가 0인 배열의 요소는 사용하지 않나요?

대답 : 사용할 수도 있지만 사용하지 않는 편이 여러모로 구현에 편의를 가져다 주고, 또 실수할 확률도 낮춰주기 때문에 일반적으로 사용하지 않는다.

 

완전 이진 트리의 구조를 갖는 "힙"이라는 자료구조는 배열을 기반으로 구현한다.

 

왼쪽 또는 오른쪽 서브 트리가 존재한다면, 해당 트리를 삭제하고서 새로운 왼쪽, 오른쪽 서브트리를 연결한다.

하지만 심각한 한번의 free 함수호출이 전부이기 때문에, 삭제할 서브 트리가 하나의 노드로 이뤄져 있다면 문제가 되지않지만, 그렇지 않다면 메모리 누수로 이어진다.

모든 노드를 방문해야서 삭제해줘야하는데 여기서 모든 노드를 방문하는 것을 "순회"라고 한다.

이진트리는 연결리스트의 순회와 달리 별도의 방법이 필요하다(재귀적인 방법으로 모든 노드에 방문하게 되는데 "후위순회"를 통해서 접근해야한다)

 

이진 트리의 순회(순회 방법은 재귀적이다)

• 전위 순회 (루트 노드 먼저!)
• 중위 순회 (루트 노드를 중간에!)
• 후위 순회 (루트 노드를 마지막에!)

세 가지 순회 방법을 재귀적으로 구현하면 된다.

 

중위 순회 순서

• 1단계 : 왼쪽 서브 트리의 순회 (서브트리순회도 중위 순회로)
• 2단계 : 루트 노드의 방문
• 3단계 : 오른쪽 서브 트리의 순회 (서브트리순회도 중위 순회로)

 

중위 순회 하나를 끝내면, 전위 순회와 후위 순회도 끝낸 것이나 다름없다. 노드의 방문 순서가 이들의 유일한 차이점이기 때문이다. (참고로 탈출조건은 재귀함수의 맨처음에 삽입한다)

 

트리의 삭제시 트리의 순회가 필요한데 루트 노드가 마지막에 소멸되어야 하기때문에 후위 순회과정을 통해서 소멸을 진행해야 한다.(삭제하고 나서 남은 노드의 left나 right이 쓰레기값을 가리켜서(노드가 소멸됬음으로) 재조회시 에러발생!

 

이진 트리를 이용해서 수식을 표현해 놓은 것을 가리켜 "수식 트리(+-)"라 한다. 즉 수식 트리는 이진 트리와 구분이 되는 별개의 것이 아니다.

 

result = 7 + 4 * 2 -1; // 중위 표기법

컴파일러는 위의 코드를 실행이 가능한 상태로 만드는 소프트웨어이다. 그런데 그 방법을 인간이 결정하여 컴파일러에게 인식시킨다는 사실을 놓치는 경우가 있따. 컴퓨터에의 유연한 판단을 유도하는 것은 쉽지 않다. 때문에 가급적 정해진 일련의 과정을 거쳐서 수식을 인식할 수 있도록 도와야 한다. 그리고 이를 위해서 수식 트리라는 것을 활용한다. 결론은 수식을 수식트리로 표현하면 컴파일러의 수식해석에 좋아진다는 것이다. 따라서 컴파일러는 수식의 이해를 위해서 수식을 수식 트리로 재 표현한다.

 

              -

      +              1     

 7        *)4,2의 부모는 *임, 7아님

      4       2  

 

질문 : 수식 트리는 중위 표기법을 사용하나요? 아니면 후위 표기법을 사용하나요?

대답 : 수식 트리는 그냥 수식 트리일 뿐이다. 중위 표기법이 수식 표현의 한가지 방법이라면 수식 트리도 이와 대등한, 수식을 표현하는 또 다른 방법일 뿐이다.

 

수식 트리를 구성하는 모든 서브 트리는 기본적으로 다음의 방식으로 연산이 진행된다.

"루트 노드에 저장된 연산자의 연산을 하되, 두 개의 자식 노드에 저장된 두 피 연산자를 대상으로 연산을 한다"

 

중위 표기법의 수식을 곧장 수식트리로 표현하는 것은 복잡하고 힘든 일이다! 하지만 후위 표기법의 수식을 수식 트리로 표현하는 것은 비교적 간단하다. 따라서 다음의 과정을 거쳐서 수식 트리를 만들도록 진행하자!

"중위 표기의 수식 - > 후위 표기법의 수식 -> 수식 트리"

 

후위 표기법의 수식을 기반으로 수식 트리 구성하기

수식 트리의 구성을 위해서는 후위 표기법의 다음 두 가지 특징을 인지하고 있어야 한다.

• 연산 순서대로 왼쪽에서 오른쪽으로 연산자가 나열된다.
• 해당 연산자의 두 피연산자는 연산자 앞에 나열된다.

 

그런데 수식 트리에서는 트리의 아래쪽에 위치한 연산자들의 연산이 먼저 진행된다. 때문에 후위 표기법의 수식에서 먼저 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 트리의 윗부분을 구성해 나가야한다.

 

"후위 표기법의 수식에서 앞쪽에 등장하는 피연산자와 연산자를 이용해서 트리의 하단을 만들고, 이를 바탕으로 점진적으로 수식 트리의 윗부분을 구성해 나간다!"

 

기본원리

• 수식 트리의 구성과정에서 피연산자는(숫자) 무저건 스택으로 옮긴다
• 연산자가 등장하면, 스택에 쌓여있는 두 개의 피연산자를 꺼내어 연산자의 노드로 연결한다. 먼저 꺼내진 피연산자가 오른쪽 자식 노드가 되고, 그 다음에 꺼내진 피연산자가 왼쪽 자식 노드가 된다!!.
• 만들어진 수식 트리 전부를 스택으로 옮긴다.(이것이 다른 연산자의 자식 노드가 되어야 하기 때문이다. + 의미적으로는 수식트리 전부를 스택으로 옮기는 것이 되지만, 실제 코드상에서는 수식트리의 루트 연산자가 저장된 노드의 주소값만 스택으로 옮기면 된다. 자식 노드는 연결되어 있으니 말이다.)

 

수식 트리의 순회방법과 의미들(후기 표기법으로 수식 트리를 만들고 나서 조회!)

• 전위 순회하여 데이터를 출력한 결과 = 전위 표기법의 수식
• 중위 순회하여 데이터를 출력한 결과 = 중위 표기법의 수식
• 후위 순회하여 데이터를 출력한 결과 = 후위 표기법의 수식

 

수식 트리의 계산

수식 트리에 담겨있 수식을 계산하는 함수를 정의하라고 하면, 단말 노드(잎사귀, 맨 밑의 노드)가 붙어 있는 서브 트리에서부터 계산을 해야 한다고 생각한다. 하지만 트리는 재귀적인 구조를 띠므로 접근방법을 달리해야 한다.