Tree (트리)

정의

• 트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.
  • 선형 구조: 데이터가 연속적, 순차적으로 나열된 자료구조이다. ex) 배열, 리스트
  • 비선형 구조: 데이터의 관계가 계층적 또는 1:n, n:m 관계를 갖는 자료구조이다. ex) 트리, 그래프
• 트리는 계층적 관계를 표현하는 자료구조이다.
• 트리 내에 또다른 트리가 존재하는 재귀적 자료구조이다.
  • 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다.
• 루프를 가지지 않고, 연결된 무방향 그래프 구조이다.
• 노드가 n개인 트리는 항상 n-1개의 간선을 가진다.

용어

• Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미한다.
• Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미한다.
• Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미한다.
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다.
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다.

---

Binary Tree (이진 트리)

정의

• 각 노드가 최대 2개의 자식 노드로 구성된 트리이다.
  • 각 노드의 차수(자식 노드)가 2 이하인 트리이다.
• 이진 트리의 종류
  • Strict Binary Tree
    • 모든 노드가 두 개의 자식을 가지거나 자식이 없는 트리
  • Full Binary Tree (포화 이진 트리 또는 정 이진 트리)
    • 모든 노드가 두 개의 자식을 가지고, 리프 노드가 같은 레벨에 있는 트리
    • 이름에서 보는 것과 같이 모든 레벨에 노드들이 꽉 채워진 형태라고 할 수 있다.
  • Complete Binary Tree (완전 이진 트리)
    • 마지막 레벨을 제외한 모든 레벨에서 노드들이 채워지고, 마지막 레벨에서는 순차적으로 채워져있는 트리
    • 루트부터 시작하여 각 노드에 순차적으로 번호를 매기면 트리 안의 노드 수까지 완전한 순열을 이룬다.
    • 이진 트리의 높이를 h라고 해보자.모든 리프 노드가 높이 h나 h-1에 있고 순열에서 빠진 숫자가 없을 때 Complete Binary Tree라고 할 수 있다.

구현

• Array를 이용한 구현
• Linked List를 이용한 구현

---

BST (Binary Search Tree, 이진 탐색 트리)

정의

• 효율적인 탐색을 위한 저장 방법으로 데이터 저장 규칙에 따른 이진 트리의 일종이다.
• 데이터 저장 규칙
  • 노드의 왼쪽 서브 트리에는 노드의 키보다 작은 키가 있는 노드만 허용한다.
  • 노드의 오른쪽 서브 트리에는 노드의 키보다 큰 키가 있는 노드만 허용한다.
  • 왼쪽 및 오른쪽 서브 트리도 모두 BST이다.
  • 중복된 키를 허용하지 않는다.

특징

• 탐색 시간 : O(log n) → O(h)
  • 정확히는 트리의 h(높이)만큼의 탐색 시간을 가지게 된다.
  • 높이를 더해갈수록 두 배씩 증가하기 때문에 log n으로도 표현한다.
• Worse Case라면 탐색의 시간 복잡도는 O(n)이 된다.
  • Skewed Tree(편향 트리)는 저장 순서에 따라서 한 쪽으로만 노드가 추가되어 있는 형태이다.
  • 이런 경우에는 배열보다 많은 메모리를 사용하고도 탐색의 시간복잡도는 같은 비효율적인 상황이 발생한다.
  • 이를 해결하는 방법으로는 Rebalancing기법이 있고, 그런 트리에는 AVL Tree, Red-black Tree가 존재한다.
• Inorder Traversal을 수행하여 모든 키를 정렬된 순서로 가져올 수 있다.
  • 이를 이용하면, 주어진 트리가 BST인지 확인할 수 있다(?)

삽입

• 시간 복잡도 : O(log n)
  • 삽입할 위치를 탐색하는 시간

1. 루트노드에서 시작한다.
2. 삽입 값과 루트를 비교한다.
   1. 작다면 왼쪽으로 재귀하고, 크다면 오른쪽으로 재귀한다.
3. 리프 노드에 도달한 후 노드보다 크다면 오른쪽, 작다면 왼쪽에 삽입한다.

삭제

• 시간 복잡도 : O(log n)
  • 삭제 할 위치를 탐색하는 시간
• 삭제할 노드가 리프 노드인 경우
  1. 해당 노드 삭제
• 삭제할 노드에 자식이 하나만 있는 경우
  1. 노드를 삭제한다.
  2. 삭제한 노드의 자식을 부모에 직접 연결한다.
• 삭제할 노드에 자식이 둘 있는 경우
  • successor 노드를 찾는 과정이 필요하다.
    • right subtree의 최솟값
    • 즉, inorder 순회에서 다음 노드
  1. 삭제할 노드를 찾는다.
  2. 삭제할 노드의 successor 노드를 찾는다.
  3. 삭제할 노드와 successor 노드의 자리를 바꾼다.
  4. 노드를 삭제한다.

사용 이유

• BST는 정렬이 된 트리이다. 따라서 탐색 속도가 빠르다.
• Array와 다르게 참조에 의해서 정렬된다.
  • 삽입 과정에서, 새로운 노드를 생성하고 링크를 연결하면 된다.
  • Array는 아예 새로운 공간에 할당을 하므로 더 느리다.

---

Binary Heap

정의

• 최솟값이나 최댓값을 빠르게 찾아내는 연산을 위해서 complete binary tree(완전 이진 트리)이다.
• 부모의 우선 순위가 자식의 우선 순위보다 높은 자료구조이다.
  • 형제끼리의 우선 순위는 고려하지 않는다.
• 최댓값이 루트에 오는 최대힙(max heap)과 최솟값이 루트에 오는 최소힙(min heap)이 있다.

특징

• Tree형태를 띄고 있는데, 배열에 기반한 Complete Binary Tree이다.
  • 개발 편의성과 가독성 때문에 배열 인덱스 1부터 사용한다.
  • 왼쪽 하위 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
  • 오른쪽 하위 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 2
• 부모 노드의 키 값과 자식 노드의 키 값 사이에는 대소 관계가 성립된다.
  • 형제 사이에는 대소 관계가 정해지지 않는다.
• 배열을 통해서 루트 노드에 저장되어 있는 최솟값(혹은 최댓값)에 접근하는데 O(1)이 걸린다.
• Extract : 루트 노드를 제거하고 난 뒤에도 heap구조를 유지한다.
  • 루트 노드를 맨 마지막 노드로 대체한 뒤, heapify 과정을 거쳐서 유지한다.
  • 유지하는 과정에서 결국 O(log n)이 걸리게 된다.
• Insert : 힙의 끝에 값을 삽입하고, heap속성을 만족할 때까지 부모 노드와 비교하여 교환한다.
  • O(log n)시간이 걸리게 된다.
• Delete : 삭제할 노드를 max값으로 설정해서 루트 노드로 보낸 뒤, extract를 수행하여 추출한다.
  • 두가지 과정을 거쳐서 O(log n)시간이 걸린다.
• 완전 이진 트리를 heap으로 만드는 작업은 O(n)이 걸린다.
  • leaf node를 제외한 나머지 노드에서 heapify를 수행한다.

Heapify

• 이진 트리에서 힙 속성을 유지하는 작업을 한다.
• 시간 복잡도: O(log n)
• heapify 작업 (max heap)
  1. 요소 값과 자식 노드의 값과 비교한다.
  2. 만약 자식 노드 값이 크다면 왼쪽과 오른쪽 중에 더 큰 값과 교환한다.
  3. 힙 속성이 유지될 때까지 1, 2 과정을 반복한다.

---

Red Black Tree(RBT)

정의

• BST에서의 편향 트리인 경우의 문제점을 해결하기 위해서 나온 자료구조로 Balanced binary search tree의 한 종류이다.
• 각 노드에 색깔을 저장하는 공간을 추가하여 색을 기준으로 균형을 맞추게 된다.
  • 균형을 맞추는 것을 통하여 동일 노드의 개수일 때, depth가 최소가 되는 complete

규칙

1. 모든 노드는 RED, BLACK이다.
2. 모든 루트와 Leaf 노드는 BLACK이다.
3. RED노드의 자식은 모두 BLACK이다. (연속된 RED노드가 나올 수 없다)
4. 각 노드로부터 그 노드의 자손 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함한다. 이를 해당 노드의 Black-Height라고 한다.

검색

• Red Black Tree도 일반 BST와 동일하게 검색을 한다.
• 시간 복잡도: O(log n)
  • 균형이 잡힌 트리이기 때문에 최악의 경우도 시간 복잡도가 유지된다.

삽입

• 시간 복잡도: O(log n)
• 삽입할 노드의 색은 Red라고 가정하고 시작한다.
• 삽입하려고 하는 노드의 부모 노드의 색이 Black인 경우에는 문제없이 삽입하게 된다.
• 삽입하려고 하는 노드의 부모 노드의 색이 Red인 경우에는 추가 조치가 필요하다.

  • 부모와 대칭점에 있는 노드가 Red인 경우에 그 위의 노드를 Red로 변경시켜준다. 만일 그 위의 노드가 Red였다면 재귀적으로 같은 조치를 취한다.

    

  • 부모와 대칭점에 있는 노드가 Black이고 추가 노드가 left child인 경우에 부모 노드를 중신으로 right rotate 시키고 부모 노드 색을 변경시킨다.

    

  • 부모와 대칭점에 있는 노드가 Black이고 추가 노드가 right child인 경우에 추가 노드를 부모 노드로 변경시킨다. 그러면 Red 노드가 연속적으로 나타나게 되는데 부모와 대칭점에 있는 노드가 Black이고 추가 노드가 left child인 경우와 같이 추가적으로 처리해주면 된다.

삭제

• 시간 복잡도: O(log n)
• 삭제될 노드의 child 개수에 따라 rotation 방법이 달라진다.
• 지워진 노드의 색이 Black이라면 Black-height가 1 감소한 경로에 Black 노드가 추가되도록 rotation하고 색을 조정한다.
• 지워진 노드의 색이 Red라면 violation이 발생하지 않으므로 그대로 유지된다.