티스토리 뷰

트리

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을 해준다. ( 레드블랙 트리가 이 중 하나 )


댓글
댓글쓰기 폼