02. 자료구조 trees: tree traversal, binary trees, binary expression trees

02. trees: tree traversal, binary trees, binary expression trees

트리, 트리탐색, 이진 트리, 이진 탐색 트리, 트리 순회, 전위 순회, 중위 순회, 후위 순회

---

0. tree

트리란 그래프의 한 종류다.

어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이 때 각 노드는 재사용 되지 않는다.

서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 하나이며, 사이클, 즉 빙빙 돌게 설계된 노드 집합이 존재하지 않고, 반드시 하나의 root(부모 노드가 존재하지 않는 노드, 맨 꼭대기)가 존재한다.

 

다음은 tree에 대한 용어 정리다.

 

• 노드(node) : 트리를 구성하는, 그래프의 정점으로, value값과 부모 자식의 정보를 가지고 있다.
• 엣지(edge, 가지) : 노드들을 연결하는 간선으로 부모 노드와 자식 노드를 연결한다.
• 루트(root node) : 가장 상위 노드로 부모를 가지지 않는다.
• 리프(leaf node, 단말 노드) : 가장 하위 노드로 자식을 가지지 않는다.
• 부모 노드 : 어떤 노드에서 자신과 인접한 노드들 중 루트 노드로 향하는 노드.
• 자식 노드 : 어떤 노드에서 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드.
• 형제  노드 : 같은 부모를 가지는 자식 노드들을 말한다.
• 깊이(depth) : 부모에서 자식으로 이동할 때, 깊이가 1 증가한다. root node의 깊이는 0이다.
• 길이(length) : 임의의 두 노드를 시작, 도착으로 하는 경로에서 거치게 되는 노드의 수
• 차수(degree) : 자식 노드의 개수

트리의 종류는 크게 두가지로 나눌 수 있는데, 이진 트리와 이진 트리가 아닌 트리다.(binary tree and non-binary tree)

 

1. tree traversal

트리 순회. 트리 구조에서 각각의 노드를 한 번씩, 체계적인 방법으로 방문하는 과정을 말한다. 노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회, 레벨 순서 순회로 나눌 수 있다. 재귀를 사용하면 손쉽게 나타낼 수 있다.

 

1) 전위 순회 (preorder)

 

노드를 방문한다 -> 왼쪽 서브 트리를 전위 순회한다. -> 오른쪽 서브 트리를 전위 순회한다.

preorder

전위 순회는 깊이 우선 순회라고도 한다.(depth-first traversal) 깊이 우선 탐색(DFS)와 같다고 할 수 있다.

 

 

2) 중위 순회 (Inorder)

 

왼쪽 서브 트리를 중위 순회한다.->노드를 방문한다.->오른쪽 서브 트리를 중위 순회한다.

inorder

중위 순회는 대칭 순회라고도 한다.(symmetric) 이진 트리에서만 할 수 있는 순회 알고리즘이다.

 

 

3) 후위 순회 (postorder)

 

왼쪽 서브 트리를 후위 순회한다.->오른쪽 서브 트리를 후위 순회한다.->노드를 방문한다.

postorder

 

4) 레벨 순서 순회

모든 노드를 낮은 레벨부터 차례대로 순회한다. 너비 우선 순회라고도 한다.(breadth-first traversal) 너비 우선 탐색(BFS)과도 같다고 할 수 있다.

 

 

2. binary trees

이진 트리는 각 노드에 대해서 2개 이하의 자식을 가지고, 이진트리가 아닌 트리는 자식 개수에 대한 제한이 없다.

non-binary tree의 가장 대표적인 사용처인 trie 자료구조는 후에 다루겠다.(ch 7에서)

 

binary tree중 가장 유명한 알고리즘은 binary-search-tree(BST)다.

BST 란 왼쪽 서브트리와 오른쪽 서브트리의 루트를 자식으로 가지며 이때 무조건 왼쪽 서브트리 <= 자신 <= 오른쪽 서브트리의 값을 가지는 형태다. 즉, 정렬(?)이 되어있는 상태다.

그래서 자료 입력, 삭제, 탐색 모두 시간복잡도가 O(log N)이다. 더 자세한 내용은 ch3에서 다루겠다.

(binary tree 코드 넣기)

 

 

 

3. binary expression trees

 

 

https://en.wikipedia.org/wiki/Binary_expression_tree

 

 

---

reference

http://bitly.kr/MOWBBy

http://www.secmem.org/blog/2019/05/09/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A2%85%EB%A5%98%EC%99%80-%EC%9D%B4%ED%95%B4/

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

 

 

부제목은 제목 3으로

글꼴은 본고딕 L