tree 자료구조

tree 자료구조

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

큐, 스택, 리스트와 같은 서형 자료구조와 다르다.

 

parent, child로 노드간의 상위/하위 노드를 표현한다. 

root노드를 제외한 나머지 노드는 단 하나의 부모노드만 갖는다.

 

1 tree에는 사이클이 없다. 

 

2 모든 노드는 모두 연결되어 있다. 

 

3 임의의 노드에서 다른 노드로 가는 경로가 유일하다. 

 

 

쓰임

1 현실 세계 개념을 추상화

 

2 탐색형 자료구조 

 

 

구성 

Node(노드) : tree를 구성 요소 

 

Edge(간선) : Node간에 연결하는 선 

 

Root Node : 트리에서 최상위 노드 

 

Leaf Node : 트리에서 최하위 노드들로 다른 하위 노드가 없다. 

 

Internal Node : Leaf Node를 제외한 나머지 노드

 

 

 

속성

 

Level : 트리의 층별 숫자로 root가 0번이다. 

 

Height : leaf node까지의 엣지 수, level과 반대다. 

 

 

종류

Binary Tree : 자녀 노드가 최대 2개

 

Ternary Tree : 자녀 노드가 최대 3개

 

Balanced Binary Tree : Binary Tree에서 좌우 균형이 맞는 트리 ( 대략적으로 양쪽의 노드 수가 비슷 ) 

 

Binary Search Tree : Binary Tree에서 검색 효율이 좋은 트리

( https://keepgoing0328.tistory.com/entry/Binary-Search-Tree)

 

Complete Binary Tree : Binary tree에서 노드가 위 -> 아래, 왼쪽 -> 오른쪽으로 채워진 트리

 

Full Binary Tree : Complete Binary tree에서 모든 노드는 childeren이 없거나 2개 있다. 

 

Perfect Binary Tree : 모든 레벨에 노드가 꽉 차서 피라미드 구조 트리 

 

 

 

Tree 순회 

순회란 트리에서 root, left subtree, right subtree 를 특정 순서에 따라 방문하는 것

 

3가지 순회 방법이 있다.  root가 언제 순회하는지에 따라 이름이 다르다. 

 

1. preorder : root - 왼쪽 - 오른쪽 순회

 

2. inorder : 왼쪽 - root - 오른쪽 순회

 

3. postorder : 왼쪽 - 오른쪽 - root 순회

 

 

 

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/

트리(tree)와 이진트리(binary tree) · ratsgo's blog