비선형 구조 - 트리

계층적 관계를 갖는 자료구조

노드(Node)와 선분(Branch)로 구성

 

● 용어

- 디그리 : 노드에서 뻗어나온 가지 수

- 근 노드 : 맨 위에 있는 노드

- 자식 노드 : 해당 노드의 하위 레벨에 있는 노드

- 부모 노드 : 해당 노드의 상위 레벨에 있는 노드

- 형제 노드 : 동일한 부모를 갖는 노드(같은 레벨)

- 단말 노드 : 자식이 하나도 없는 노드

 

 

1. 이진트리(Binary Tree)

- 완전이진트리(Complete Binary Tree)

- 정이진트리(Full Binary Tree) : 자식노드의 수는 0이거나 2인 트리 (자식노드가 하나만 있으면 안됨)

- 포화이진트리(Perfect Binary Tree) : 모든 노드가 자식노드 수가 2인 트리

 

2. 이진탐색트리(Binary Search Tree)

이진탐색 + 연결리스트

자식의 갯수는 2이하여야 하고 노드는 중복되지 않아야 한다.

부모노드는 왼쪽 자식의 노드보다 크고 오른쪽 자신의 노드보다 작다 (왼쪽자식 < 부모 < 오른쪽자식)

중위순회를 적용할 시 오름차순이 된다.

 

평균 검색시 : O(logn)

최악 검색시 : O(n)

 

3. 트라이 트리(Trie Tree)

문자열에서 검색을 빠르게 도와주는 이진탐색트리 구조

 

문자열의 길이가 n일때 검색시 : O(n)