[자료구조] 트리, 이진트리, 이진탐색트리

트리

Node : 트리를 구성하고 있는 각각의 요소를 의미

Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미

Root Node : 트리 구조에서 최상위에 있는 노드를 의미

Terminal Node ( Leaf Node ) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미

Internal Node : Leaf 노드를 제외한 모든 노드로 루트 노드를 포함

Level : 각 층별로 매긴 숫자로 루트노드의 레벨은 0이고, 최고 레벨을 높이라고 한다.

Binary Tree

- 루트노드를 중심으로 두 개의 서브트리로 구성되어 있다.

- 두 개의 서브트리도 모두 이진트리여야 한다.

Full Binary Tree / Complete Binary Tree

모든 레벨이 꽉 찬 이진트리를 말한다.

포화이진트리는 노드의 개수가 n일 때, i번째 노드에 대해서

parent(i) = i/2

left_child(i) = 2*i

right_child(i) = 2*i + 1

Binary Search Tree

이진트리의 일종으로 아래의 규칙을 만족한다.

- 이진 탐색 트리의 노드에 저장된 키는 유일하다.

- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.

- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.

- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

탐색

- 시간복잡도 : O(log n) = O(h)

- worst case : 이진탐색트리가 한쪽 서브트리로만 계속 편향된 경우 트리의 높이가 노드의 수와 같아지므로 O(n)에 가까워진다.

- worst case를 해결하기 위해 트리의 구조를 재조정하는 rebalancing을 해준다. ( 레드블랙 트리가 이 중 하나 )