[자료구조] 트리

Tree

 스택과 큐와 다르게 비선형 구조이다. 계층적 관계를 표현한다. 그래프의 한 종류이며 사이클이 없다.

트리의 구성 요소

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

용어

• degree(차수) : 해당 노드의 자식노드 개수
• degree of Tree(트리의 차수) : 트리의 최대 차수
• level(레벨) : 트리의 각 층
• depth(노드의 깊이) : 루트에서 어떤 노드에 도달하기 위해 거쳐야하는 간선의 수
• height(트리의 높이) : 트리의 최고 level

Binary Tree(이진 트리)

 이진트리는 각 노드가 최대 두개의 자식노드를 갖는 트리이다. 루트 노드를 중심으로 두개의 서브트리로 나누어진다. 나뉘어진 두개의 서브트리 모두 이진트리어야 한다. 위 조건은 나뉜 두 개의 서브트리 또한 만족해야한다. 즉, 이진 트리의 모든 서브트리는 이진트리여야한다. 리프 노드 또한 위 조건을 만족해야하기 때문에 공집합 또한 이진트리에 포함된다.

• 포화 이진 트리 : 모든 레벨이 꽉 찬 이진 트리

  

  [그림1] 포화 이진 트리 예시

• 완전 이진 트리 : 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리

  

  [그림 2] 완전 이진 트리 예시

• 정 이진 트리 : 모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리

  

  [그림 3] 정 이진 트리 예시

 이진 트리를 배열로 구현할 경우, 트리의 노드의 개수가 n개일때 특정 노드의 인덱스를 i에 대하여 parent(i) = i/2, left_child(i) = i\*2, right_child(i) = i\*2 + 1의 값을 가진다. 예를 들어 그림1을 배열로 표현했을 때 그 배열의 원소는 아래와 같다.

BST(Binary Search Tree)

 이진 트리의 일종으로 데이터의 효율적인 탐색을 위해 사용된다. 이진 탐색 트리는 아래의 규칙을 가진다.

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

 이진탐색트리의 탐색 시간은 $O(h)$이다. 이 때 $h=\log n$ 이기 때문에 이진탐색트리의 탐색 시간은 $O(\log n)$이다. 하지만 이진탐색트리는 편향트리(Skewed Tree)가 될 수 있는데 이 경우, $h = n$이 되어 탐색 시간이 $O(n)$인 worst case가 된다.

Red Black Tree

 RBT는 BST를 기반으로하는 트리이다. Search, Insert, Delete에 모두 $O(\log n)$의 시간복잡도가 소요된다. 동일한 개수의 노드를 가질 때 depth를 최소화 시켜 시간 복잡도를 줄이는 것이 핵심 아이디어이다.

RBT의 조건

1. 각 노드는 Red or Black의 색깔을 갖는다.
2. 루트 노드의 색깔은 Black이다.
3. 각 리프 노드의 색깔은 Black이다.
4. Red 노드의 자식의 색깔의 Black이다.
5. 모든 리프 노드에서의 Black-Depth는 같다.
   (Black-Depth : 특정 노드 X에서 부터 리프 노드까지 X를 포함하지 않는 simple path에 포함되는 black 노드의 개수)

RBT의 특징

1. BST이다.
2. 루트 노드부터 리프 노드까지의 최장 경로의 길이와 최단 경로의 길이의 비는 2를 넘지 않는다. -> balanced한 상태이다.
3. 노드의 child가 없을 경우 포인터는 NIL를 갖는다.

삽입

 BST의 특성을 유지하며 삽입을 한다. 삽입된 노드의 색깔은 Red이다. 삽입 결과 RBT의 조건 4번에 위배되는 경우 Rotation 혹은 Recoloring을 통해 조정을 한다.
 Rotation은 RBT의 조건 4번에 위배되는 경우에서 문제가 발생한 노드의 부모의 형제가 없거나 Black일 때 사용한다.
과정은 아래와 같다.

1. 삽입한 노드와 부모, 부모의 부모를 오름차순으로 정렬한다.
2. 가운데 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 부모가 된 가운데 값을 Black으로 만들고 자식들을 Red로 만든다.

 Recoloring은 RBT의 조건 4번에 위배되는 경우에서 문제가 발생한 노드의 부모의 형제가 red일 때 사용한다.
과정은 아래와 같다.

1. 삽입한 노드의 부모와 부모의 형제를 Black으로 하고 부모의 부모를 Red로 한다.
2. 부모의 부모가 루트 노드일 경우 다시 Black으로 바꾼다.
3. 1번 과정으로 인해 다시 Double Red(4번 조건 위배)가 발생할 수 있다. 이 경우 부모의 부모 위치에서 다시 Recoloring을 진행한다. -> Recoloring은 propagation될 수 있다.(최악의 경우 루트까지 올라감)

Rotaion과 Recoloring 모두 insert 과정에서 최대 $\log n$의 depth에 트리를 탐색하게 되므로 $O(\log n)$의 시간 복잡도를 갖는다. 추가로 Recoloring의 경우 루트까지 propagation될 수 있으므로 최악의 경우 $O(\log n)$의 시간이 걸리게 된다. 결과적으로 둘다 $O(\log n)$의 시간 복잡도를 갖는다.

Binary Heap

 자료구조의 일정으로 Tree의 형식을 하고 있으며, 배열에 기반한 완전 이진 트리이다. 최대힙(Max Heap), 최소힙(Min Heap)이 있다.

 Max Heap이란, 각 노드의 값이 해당 자식의 값보다 크거 나 같은 완전 이진 트리를말한다. (Min Heap은 그 반대이다.)
Max Heap에서는 루트노드의 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간복잡도는 $O(1)$이다. 그리고 완전 이진트리이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다(배열을 사용하기 때문에 random access가 가능하다). Min Heap에서는 반대로 최소값을 찾는데 걸리는 시간복잡도가 $O(1)$이다.

삽입

 Heap에 새로운 요소가 들어오면, 일단 새로운 노드를 Heap의 마지막 리프 노드에 할당 한 후 부모와 비교하는 과정을 반복하여 Max Heap 또는 Min Heap의 조건을 모두 만족하게 한다.
 아래는 Heap의 X의 자리에 15의 값을 삽입하는 예시이다.

삭제

 루트 노드의 값을 지운다. 그리고 가장 끝에 있는 리프노드를 루트노드의 위치로 옮긴다. 이후 자식 노드와 비교하여 Heap의 조건을 만족할 때까지 자식 노드와 위치를 바꾸는 연산을 반복한다.