트리

1. 트리 구조

 

트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조입니다.

 

실제로는 이진트리 (Binary Tree) 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용됩니다.

 

2. 용어

 

Node : 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함)

Root Node : 트리 맨 위에 있는 노드

Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄

Parent Node : 어떤 노드의 다음 레벨에 연결된 노드

Child Node : 어떤 노드의 상위 레벨에 연결된 노드

Leaf Node (Terminal Node): Child Node가 하나도 없는 노드

Sibling (Brother Node) : 동일한 Parent Node를 가진 노드

Depth : 트리에서 Node가 가질 수 있는 최대 Level

이진트리와 이진 탐색 트리

 

이진트리: 노드의 최대 Branch가 2인 트리

이진 탐색 트리 : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리

 - 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값

 

이진 탐색 트리의 시간 복잡도와 단점

 

탐색 시

 

depth를 h라 표기한다면 O(h)

n개의 노드를 가진다면 h = logn에 가까우므로 시간 복잡도는 O(logn)

즉 50%씩 단축

 

만약 트리 구성이 잘못되어있을 경우 O(n) 시간 복잡도를 나타냄