Tree

- 비선형 자료구조

- 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조

- 가지를 늘려가며 표현하게 된다.

 

Tree의 구조

- 노드(node) : 2, 7, 5, 2, 6, 5, 11, 4, 9와 같은 요소들

- 간선(edge) : 노드와 노드를 연결하는 연결선

- 루트 노드(root) : 트리 구조에서 최상위에 존재하는 노드. 2와 같음

- 단말 노드, 잎사귀 노드(terminal node, leaf node) : 아래로 또 다른 노드가 연결되어 있지 않은 5, 11, 4와 같은 노드

- 내부 노드(internal node) : 단말 노드를 제외한 모든 노드

 

- 레벨(level) : 각 층별 위치

- 높이(height) : 트리의 최고 레벨, 이 트리의 높이는 3이다.

 

이진 트리(Binary Tree)

- 루트 노드를 중심으로 두 개의 서브트리로 나뉘어진다.

- 나뉘어진 두 서브 트리 모두 이진 트리여야 한다 => 이진 트리의 재귀적 특성

- 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다.

 

* 서브 트리(Sub Tree)

- 큰 트리에 속하는 작은 트리

 

포화 이진 트리(Full Binary Tree)

- 모든 레벨이 꽉 찬 이진 트리

 

완전 이진 트리(Complete Binary Tree)

- 빈틈 없이 노드가 채워진 이진 트리

- 즉, 노드가 위에서 아래로, 왼쪽에서 오른쪽의 순서대로 채워진 것

 

 

이진 트리 구현

- 재귀적인 특성 때문에 일부 연산은 재귀호출의 형태를 띤다.

- 주로 연결리스트 기반이다.

 

배열 기반

- 주로 연결리스트 기반이지만, 빈번한 탐색이 이루어 질 때 배열을 사용한다.

- 노드에 고유한 번호를 부여해야 한다. => 인덱스 값

- 인덱스가 0인 배열의 요소는 편의상 사용하지 않는다.

- 완전 이진 트리의 구조를 갖는 힙(heap)은 배열을 기반으로 구현한다.

 

연결 리스트 기반

- 연결 리스트 기반으로 트리를 구현할 경우 연결 리스트의 구성 형태와 트리가 일치한다.

 

 

이진 트리의 ADT

TreeNode * MakeTreeNode(void);

- 이진 트리 노드를 생성하고 그 주소를 반환한다.

 

Data GetData(TreeNode *bt);

- 노드에 저장된 데이터를 반환한다.

 

void SetData(TreeNode * bt, Data data);

- 노드에 데이터를 저장한다.

-data로 전달된 값을 저장한다.

 

TreeNode * GetLeftSubTree(TreeNode * bt);

- 왼쪽 서브 트리의 주소 값을 반환한다.

 

TreeNode * GetRightSubTree(TreeNode * bt);

- 오른쪽 서브 트리의 주소 값을 반환한다.

 

void MakeLeftSubTree(TreeNode * main, TreeNode * sub);

- 왼쪽 서브 트리를 연결한다.

 

void MakeRightSubTree(TreeNode * main, TreeNode * sub);

- 오른쪽 서브 트리를 연결한다.

 

 

이진 탐색 트리(Binary Search Tree)

• 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

- O(log n)의 시간 복잡도

- 저장 순서에 따라 한 쪽으로만 노드가 추가되는 Skewed Tree가 될 수 있다. 이 경우에는 Worst case가 되고 시간복잡도가 O(n)이 된다.

- 배열보다 많은 메모리를 사용했는데 탐색에 필요한 시간 복잡도가 같게 된다. => 해결하기 위해 Rebalancing

- Rebalancing : 균형을 잡기 위한 트리 구조의 재조정

 

 

이진 트리의 순회(Traversal)

전위 순회(Preorder Traversal)

- 루트 노드를 먼저

 

중위 순회(Inorder Traversal)

- 루트 노드를 중간에

 

후위 순회(Postorder Traversal)

- 루트 노드를 마지막에

 

 

수식 트리(Expression Tree)

- 이진 트리를 이용하여 수식을 표현해 놓은 것

- 수식을 수식 트리로 표현하면 컴파일러의 수식 해석이 좋아진다.

- 따라서 컴파일러는 수식의 이해를 위해서 수식을 수식 트리로 재 표현한다.

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

 

 

 

-

참고

http://www.ktword.co.kr/test/view/view.php?no=4726 

트리 용어

https://www.codingworldnews.com/news/articleView.html?idxno=3554 

자료구조 어디까지 알고 있니? #5. 트리의 종류 - 코딩월드뉴스

윤성우의 열혈 자료구조

 

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#stack-and-queue

GitHub - JaeYeopHan/Interview_Question_for_Beginner: Technical-Interview guidelines written for those who started studying progr