TIL 8 | 자료구조 Tree

Tree

트리는 비선형 자료구조이다. 계층적 관계를 표현하는 자료구조로 표현에 집중한다. 무언가 저장하고, 꺼낸다는 사고에서 벗어나서 보자

• 용어
  Node(노드) : 트리를 구성하는 각 요소
  Edge(간선) : 노드와 노드를 연결하는 선
  Root Node(루트노드) : 트리 구조에서 최상위 노드
  Leaf Node(단말 노드) : 하위에 다른 노드가 없는 노드
  Internal Node(비단말 노드) : 단말 노드를 제외한 모든 노드, 루트 노드 포함

• 이진 트리
  이진 트리는 가장 많이 사용하는 트리구조이다. 이진 트리는 모든 노드가 두개의 서브트리를 가지는 구조로 서브트리는 노드가 있을수도 있고 없을수도 있다.

1. 편향 이진트리
   모든 자식 노드가 부모 노드의 왼쪽 또는 오른쪽으로 편향된 이진 트리이다.
   

2. 포화 이진트리
   이진 트리가 보유할 수 있는 최대 노드를 가진 형태 이진 트리이다.
   

3. 완전 이진트리
   높이가 k일 때 레벨 1부터 k-1까지는 모든 노드가 채워져 있고, 마지막 레벨 k에서 왼쪽부터 오른쪽으로 노드가 순서대로 채워진 이진 트리이다.
   

• 이진 탐색 트리(BST, Binary Search Tree)
  효율적인 탐색을 위해 효율적인 저장방법을 사용했다.

1. 노드에 저장된 키는 유일하다.
2. 부모 키가 왼쪽 자식 노드의 키보다 크다
3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리는 위 4가지의 규칙을 가진다.
이진 트리 탐색 연산은 O(log n)의 시간복자도를 가지지만 O(h)라고 할 수도 있다. 트리의 높이를 하나씩 더해가면 노드의 갯수는 2배씩 증가한다. 그리고 이러한 이진 탐색 트리가 편향 트리가 되면 성능에 영향을 미쳐 O(n)의 시간복잡도를 가질 수 있다.