[Java]자료구조 - Tree

Tree

 

자료구조 Tree(트리)는 주로 계층적인 구조를 표현하기 위해 사용한다.

 

• /Users/username
• 토너먼트 경기의 대진표
• 조직도

 

트리구조는 루트(Root)라는 최상위 노드에서 시작해 각 데이터를 간선(Edge, Link, Branch)으로 연결한다.

 

두 개의 노드가 상하관계를 가질 때 위의 노드를 부모 노드(Parent Node), 아래의 노드를 자식 노드(Child Node)라 부른다.

 

자식 노드가 없는 노드를 리프 노드(Leaf Node)라고 하며, 리프 노드를 제외한 노드를 인터널 노드(Internal Node)라 부른다.

 

또한 트리구조는 깊이와 레벨, 높이를 측정할 수 있는데 그 정의는 아래와 같다.

 

• 깊이(Depth) - 루트로부터 특정 노드까지의 간선 개수. 위 Animal의 경우 깊이가 2이다.
• 레벨(Level) - 깊이와 같이 0 혹은 1부터 시작한다. 레벨이 같은 노드를 형제 노드(Sibling Node)라 한다.
• 높이(Height) - 트리에 존재하는 레벨의 총 개수. 위 그림 같은 경우 레벨 3까지 있으므로 높이가 3이다.

 

마지막으로 트리의 내부에 존재하는 작은 트리구조를 서브 트리(Sub Tree)라고 한다.

 

---

이진 트리(Binary Tree), 이진 탐색 트리(Binary Search Tree)

 

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리구조를 말한다.

 

자식 노드는 항상 왼쪽 노드인지 오른쪽 노드인지를 부여받으며,

 

같은 key 값을 가지는 자식 노드가 있어도 위치가 다를 경우 다른 트리로 취급하게 된다.

 

또한 이진 트리는 자료의 삽입, 삭제 방법에 따라 세 가지로 나뉜다.

 

정 이진 트리(Full binary tree), 포화 이진 트리(Perfect binary tree), 완전 이진 트리(Complete binary tree)가 그것인데, 

 

각각의 특징은 아래와 같다.

 

계속해서 이진 탐색 트리(Binary Search Tree)는 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 자료구조이다.

 

이름에 걸맞도록 효율적인 탐색을 위해, 이진 탐색 트리는 다음과 같은 특징을 갖는다.

 

• 중복 값을 다루지 않는다.
• 왼쪽 서브 트리 노드들은 루트 값보다 작다.
• 오른쪽 서브 트리 노드들은 루트 값보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

---

이진 트리 순회(Tree Traversals)

 

특정 목적을 가지고 모든 노드를 한 번씩 방문하는 것을 트리 순회라 한다.

 

트리를 순회하는 방법은 크게 세 가지가 있으며, 공통적으로 왼쪽 노드에서 오른쪽 노드로 진행한다.

 

또한 위에서 봤듯이 이진트리의 서브 트리 역시 이진트리이기 때문에, 재귀 함수를 적용하기가 편해진다.

 

순회 중 루트를 방문하는 작업을 V라고 했을 때, 작업에서 V가 위치하는 순서에 따라 순회 방식이 정해진다.

 

• 루트를 가장 먼저 방문하면 전위 순회 - VLR
• 루트를 왼쪽과 오른쪽 서브 트리 중간에 방문하면 중위 순회 - LVR
• 루트를 서브 트리 방문 후에 방문하면 후위 순회 - LRV

 

위 그림은 전위 순회시 노드를 방문하는 순서가 적혀 있다.

 

계속해서 위 그림은 중위 순회에 대한 그림이다.

 

마지막으로 후위 순회에 대한 그림이다.