트리(Tree)_1

트리 용어

• 노드 : 데이터 원소
• 간선 : 노드 사이의 부모-자식 관계를 표시
• 루트 : 트리 맨 위에 있는 부모가 없는 노드
• 내부노드(중간노드) : 적어도 한 개의 자식을 가진 노드
• 외부노드(잎) : 자식이 없는 노드
• 형제 : 같은 부모를 가진 노드들
• 노드의 조상 : 루트를 향해 간선을 따라 올라가면 만나게 되는 부모, 조부모, 증조부모 등의 직계 상위 노드들
• 노드의 자손 : 잎을 향해 간선을 따라 내려가면 만나게 되는 자식, 손주, 증손주 등의 직계 하위 노드들
• 부트리 : 노드와 그 노드의 자손들로 구성된 트리

 

 

 

 

 

 

 

 

 

 

• 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스
• 경로길이 : 경로 내 간선의 수
• 노드의 깊이 : 루트로부터 그 노드에 이르는 유일한 경로의 길이
• 노드의 높이 : 그 노드로부터 외부노드에 이르는 가장 긴 경로의 길이
• 트리의 높이 : 루트의 높이
• 순서트리 : 각 노드의 자식들에 대해 선형 순서가 정의되어 있는 트리
• 무순트리 : 순서가 중요하지는 않은 트리

 

트리 ADT 메쏘드

일반메쏘드

• boolean isEmpty() : 트리가 비어 있는지 여부를 반환 (트리가 비어 있지 않다고 전제할 경우 항상 거짓 반환)
• integer size() : 트리의 노드 수를 반환

접근 메쏘드

• node root() : 트리의 루트 노드를 반환
• node parent(v) : 노드 v의 부모노드를 반환
• node children(v) :  노드 v의 자식노드들을 반환
• element element(v) : 노드 v에 저장된 원소를 반환

질의 메드

• boolean isInternal(v) : 노드 v가 내부노드인지 여부를 반환
• boolean isExternal(v) : 노드 v가 외부노드인지 여부를 반환
• boolean isRoot(v) : 노드 v가 루트인지 여부를 반환

갱신 메쏘드

• swapElements(v,w) : 노드 v와 w에 저장된 원소를 교환
• element setElements(v,e) : 노드 v에 원소 e저장

예외

• invalidNodeException() : 불법노드(즉, 존재하지 않는 노드)에 대한 접근 시 발령

노드 v의 깊이 (재귀)

• 만약 v가 루트면, v의 깊이는 0
• 그렇지 않으면, v의 깊이는 v의 부모의 깊이 더하기 1
• 시간 복잡도 : O(n) 
• n : 트리 내 총 노드 수
• 계속해서 자식이 한 개인 편향 트리인 경우 최악 실행시간 n이 나옴
• 일반 generic 트리 : 상세 구현이 특정되어 있지 않은 추상적 트리 (트리 ADT)
• 일반 general 트리 : 여러 개의 자식노드를 가진 트리 (이진 트리와 구별하는 의미에서)

노드 v의 높이 (재귀)

• 만약 v가 외부노드면, v의 높이는 0
• 그렇지 않으면, v의 높이는 v의 자식들 중 최대 높이 더하기 1
• 시간 복잡도 : O(n)
• n : 트리 내 총 노드 수
• 편향 트리인 경우 최악 실행시간 n이 나옴
• 루트의 높이 = 트리의 높이

트리 순회- 선위순회

• 선위순회 : 노드를 그 자손들보다 앞서 방문
• 시간 복잡도 : O(n)  모든 노드를 정확히 한 번씩 방문하므로
• n : 트리 내 총 노드 수

트리순회- 후위순회

• 후위순회 : 노드를 그 자손들보다 나중에 방문
• 시간 복잡도 : O(n)  모든 노드를 정확히 한 번씩 방문하므로
• n : 트리 내 총 노드 

트리순회- 레벨순회

• 레벨순회 : 각 레벨을 위에서 아래 방향으로 순회
• 큐를 이용하여 깊이 d의 모든 노드들을 깊이 d+1의 노드들에 앞서 방문함
• 큐의 선입선출 특성을 이용하여 트리의 특정 레벨에 저장된 노드들에 대한 방문을 모두 마친 후에야 다음레벨의 노드들에 대해 처리함

 

 

 

 

 

 

 

 

 

 

 

 

• 시간 복잡도 : O(n)  모든 노드를 정확히 한번씩 방문하므로

이진트리 ADT

이진트리 binary tree : 자식을 두 개만 가지는 트리

• 사람의 부모족보, 대진표
• 수식, 문답식 도움말
• 왼 자식, 오른 자식의 고유한 의미가 있음 (두 의미를 왔다 갔다 하지말기)
• 이진트리 ADT는 순서트리를 모델링함
• 트리의 각 내부노드는 두 개의 자식을 가짐 (왼쪽 자식, 오른쪽 자식)
• 적정이진트리 proper binary tree : 모든 내부노드가 왼쪽, 오른쪽 자식을 둘 다 가지는 이진트리
• 알고리즘 작성의 용이성을 위해 아무 원소도 저장하지 않는 외부노드를 추가 설정함으로써 적정이진트리로 만들어버리기도 함
• 재귀적 정의 : 루트가 자식의 순서쌍 ordered pair 을 가지며, 그 각각의 자식이 내부노드인 경우에 이진트리다.
• 트리가 비어 있지 않다고 전제할 경우 알고리즘이 단순화됨

이진트리의 예 : 수식트리 expression tree

• 내부노드 : 연산자 (operators)
• 외부노드 : 피연산자 (operands)
• (2x(a-1))/(3+b)

 

 

 

 

 

 

 

 

 

이진트리 속성

• n : 이진트리의 노드 수
• e : 외부노드의 수
• i : 내부노드의 수
• h : 트리의 높이
• e = i+1
• n = i+e = 2e-1
• h <= i
• h <= (n-1)/2
• e <= 2의 h승
• h >= log 2의 e
• h >= log 2의 (n+1) -1

이진트리 ADT 메쏘드

트리 ADT의 모든 메쏘드들 상속함

 

추가 메쏘드

• node leftChild(v) : 노드 v의 왼쪽 자식노드를 반환
• node rightChild(v) : 노드 v의 오른쪽 자식노드를 반환
• node sibling(v) : 노드 v의 형제노드를반환

노드 v의 깊이

• 만약 v가 루트면, v의 깊이는 0
• 그렇지 않으면, v의 깊이는 v의 부모의 깊이 더하기 1

노드 v의 높이

• 만약 v가 외부노드면, v의 높이는 0
• 그렇지 않으면, v의 높이는 v의 왼쪽과 오른쪽 자식 중 최대 높이 더하기 1

이진트리 순회- 선위순회와 후위순회

• 선위순회에서는 노드를 그의 왼쪽 및 오른쪽 부트리보다 앞서 방문
• 후위순회에서는 노드를 그의 왼쪽 및 오른쪽 부트리보다 나중에 방문

후위순회의 예: 수식트리 평가

• 부트리의 값을 반환하는 재귀적 메쏘드를 사용함
• 내부노드 방문 시에 부트리의 값들을 결합함
•  

  

   

 

 

 

 

 

 

 

• 2방문
• a방문
• 1방문 
• -방문(부트리의 값들 결합을 하지만 단순 a와 1임 a-1) 
• x방문(왼쪽부트리 단순 2 x 오른쪽 부트리 값들 결합 (a-1))
• 3방문
• b방문
• +방문(단순 3과 b임 3+b)
• /방문(왼쪽 부트리 2x(a-1)/오른쪽 부트리 (3+b))

이진트리 순회- 중위순회

• 중위순회 : 노드를 그의 왼쪽 부트리보다는 나중에, 오른쪽 부트리보다는 앞서 방문함
• 시간 복잡도 : O(n)
• n : 이진트리 내 총 노드 수

중위순회 예: 이진트리 그리기

• 주어진 제약 하에 이진트리의 노드들을 xy 평면에 그리는 문제
• 제약조건은 노드의 자식노드들에 대한 사전정보 없이 실시간에 그려야 함
• 좌우 부트리가 펼쳐진 폭의 차이를 사전에 알 수 없어 노드를 x축의 어디쯤위치시켜야 할지 계산할 수 없음 그러므로 위에서 아래 방향으로는 이진트리르 그릴 수 가 없음
• 중위순회를 응용하면 위에서 아래방향으로가 아닌 왼쪽에서 오른쪽 방향으로 그리기가 가능

• 

 

 

 

 

 

 

중위순회 예: 수식인쇄

• 수식을 한줄로 그냥 인쇄하면 연산자 우선순위로 식의 결과값이 바뀔 수 있으므로 괄호를 쳐야함
• 연산자가 피연산자 사이에 와야하므로 당연히 중위순회임
• 노드를 방문 시에 인쇄
• 왼쪽 부트리를 순회하기 전에 '('를 인쇄
• 오른쪽 부트리를 순회한 후에 ')'를 인쇄
•  

  

 

 

 

 

 

 

• 결과 : ((2x(a-1))/(3+b))
• 맨 바깥의 괄호 쌍이 인쇄되지 않도록 하려면?

이진트리에 대한 오일러 투어 순회

 

오일러 투어(Euler Tour) : 이진트리에 대한 일반순회(generic traversal) 즉, 선위, 중위, 후위를 모두 포함하는 순회 방식

• 이진트리의 루트를 출발하여 왼쪽 자식 방향으로 진행
• 이진트리의 간선들을 마치 벽처럼 취급하여, 항상 왼쪽 벽으로 두면서 이진트리의 주위를 걸음
• 각 노드를 3번 방문 -노드의 왼쪽(L), 아래(B), 오른쪽(R)
• 왼쪽, 아래, 오른쪽을 방문했을 때 각각 선위, 중위, 후위 순회에서의 방문 노드에 대한 작업과 같은 작업을 함

• 

 

 

 

 

 

 

 

오일러 투어 응용 예: 이진트리 내 각 부트리의 노드 수 계산

• 이진트리 내에 존재하는 모든 부트리에 속한 노드 수를 계산하는 문제
• 각 노드의 왼쪽을 지날때부터 오른쪽을 지날때까지 지나온 노드수가 그 노드를 루트로 갖는 부트리의 총 노드수가 됨
• 시간 복잡도 : 3*O(n)=O(n)  모든 노드를 정확히 세 번 방문하므로

• 

 

 

 

 

 

 

 

• 카운터 k를 0으로 초기화 후 오일러 투어 시작
• 노드를 왼쪽에서 방문할 때마다 k 하나씩 증가
• 루트가 v인 부트리의 크기는, v를 왼쪽에서 방문했을 때의 k값과 오른쪽에서 방문했을 때의 k값을 차이에 1을 더한 것