Tree

정의

• 그래프의 일종으로, 여러 노드가 한 노드를 가르킬 수 없는 구조이다. (사이클이 없는 그래프)
• 스택이나 큐와 다르게 비선형의 자료구조이다.

이진 트리 (Binary Tree)

• 루트 노드를 중심으로 두 개의 서브트리로 나누어지는 트리이다. 나누어진 트리도 두개의 서브트리로 나누어져야한다.
• 공집합도 이진트리이다.
• 이진트리에는 완전 이진 트리, 포화 이진 트리, 정 이진 트리가 있다.

완전 이진 트리 (Complete Binary Tree)

• 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 채워지는 이진 트리를 완전 이진트리라고 한다.
• 이진 힙 (Binary Heap)은 완전 이진 트리의 형태를 기반으로 하고 있다.

이진 힙 (Binary Heap)

• 이진 힙에는 최대 힙과 최소 힙이 존재한다.
• 최대 힙은 각 노드의 값이 자식 노드보다 크거나 같은 완전 이진 트리이다. (최소 힙은 그 반대)
• 트리의 최대/최소 값을 탐색하는데 O(1)의 시간이 소요되지만, 힙에서 루트 노드를 재설정하는 과정에서 log n이 소요된다.

이진 탐색 트리

• 이진 트리의 일종이다.
• 데이터를 저장하는 규칙이 존재한다.

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

• 이진 탐색 트리의 탐색은 O(log n) = O(h) 의 시간 복잡도를 갖는다.
• 이진 탐색 트리는 편향 트리가 될 수 있다는 단점이 있다. 이럴 경우 O(h) = O(n) 이므로 Worst Case는 O(n)의 시간복잡도를 갖는다.
• 이를 해결하기 위하여 Red-Black Tree가 등장했다.

Red-Black Tree