Tree 구조

 트리는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조입니다. 트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조입니다. 이 트리라는는 자료구조는 표현에 집중합니다. 자료에서 무엇인가를 저장하고 꺼내야 한다는 사고에서 벗어나 트리라는 자료구조를 바라보는 것이 좋습니다.

 

1.  트리를 구성하고 있는 구성요소들(용어)

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

 

2. Tree의 종류

Binary Tree (이진 트리)

 루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 집니다. 또한 나뉘어진 두 서브 트리도 모두 이진 트리어야 합니다. 여기서 공집합도 이진 트리로 포함시켜야 합니다. 그래야 재귀적으로 조건을 확인해갔을 때, leaf node 에 다다랐을 때, 정의가 만족되기 때문입니다. 자연스럽게 노드가 하나 뿐인 것도 이진 트리 정의에 만족하게 됩니다.

 트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 합니다. 레벨의 값은 0 부터 시작하고 따라서 루트 노드의 레벨은 0 입니다. 그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 합니다.

Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리)

https://limkydev.tistory.com/134

(a) 모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 합니다.

(b) 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 합니다.

 

BST (Binary Search Tree) 

 이진 탐색 트리는 이진 트리의 일종입니다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있고, 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있습니다.

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

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖습니다. (정확히 말하면 O(h)) 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문입니다. 하지만 이러한 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있습니다. 저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문입니다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case 가 되고 시간 복잡도는 O(n)이 됩니다. 

 배열보다 많은 메모리를 사용하며 데이터를 저장했지만 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황이 발생합니다. 이를 해결하기 위해 균형을 잡기 위한 트리 구조의 재조정 Rebalancing이라는 기법이 생겼습니다. 이 기법을 구현한 트리에는 여러 종류가 존재하는데 그 중에서 하나가 뒤에서 살펴볼 Red-Black Tree입니다.

 

---

Binary Heap

 자료구조의 일종으로 Tree 의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree입니다. 배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작됩니다. 이는 노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄이기 위함입니다. 힙(Heap)에는 최대힙(max heap), 최소힙(min heap) 두 종류가 있습니다.

 Max Heap이란, 각 노드의 값이 해당 children 의 값보다 크거나 같은 complete binary tree를 말합니다. ( Min Heap 은 그 반대)

Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간복잡도가 O(1)입니다. 그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있습니다다. (random access 가 가능하다. Min heap 에서는 최소값을 찾는데 소요되는 연산의 시간복잡도가 O(1))

 

 위의 그림에서 (a)처럼 5개의 원소를 가진 최대힙이 있다고 한다면, 최대 힙은 완전 이진트리를 따르기 때문에 하나의 원소를 추가시킨다면 (b)가 된다. 삽입되는 원소의 정확한 위치를 결정하기 위해 트리의 새 노드에서 부터 시작해 루트쪽으로 올라가는 방법을 사용합니다. 삽입되는 원소는 새 노드에 삽입되고 나서, 최대 힙이 될 때까지 위로 올라가는 과정을 반복합니다.

 하지만 heap 의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요합니다. 여기서 heap 은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지합니다. 이런 경우에는 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 됩니다.

 

Red Black Tree

 RBT(Red-Black Tree)는 BST 를 기반으로하는 트리 형식의 자료구조입니다다. 결론부터 말하자면 Red-Black Tree 에 데이터를 저장하게되면 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요됩니다. 동일한 노드의 개수일 때, depth 를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어입니다. 동일한 노드의 개수일 때, depth 가 최소가 되는 경우는 tree 가 complete binary tree 인 경우입니다.

Red-Black Tree 의 정의

1. 각 노드는 Red or Black이라는 색깔을 갖는다.
2. Root node 의 색깔은 Black이다.
3. 각 leaf node 는 black이다.
4. 어떤 노드의 색깔이 red라면 두 개의 children 의 색깔은 모두 black 이다.
5. 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. cf) Black-Height: 노드 x 로부터 노드 x 를 포함하지 않은 leaf node 까지의 simple path 상에 있는 black nodes 들의 개수

Red-Black Tree 의 특징

1. Binary Search Tree 이므로 BST 의 특징을 모두 갖습니다.
2. Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않습니다. 이러한 상태를 balanced 상태라고 합니다.
3. 노드의 child 가 없을 경우 child 를 가리키는 포인터는 NIL 값을 저장합니다, 이러한 NIL 들을 leaf node 로 간주합니다.

RBT 는 BST 의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조입니다. 

 

삽입

 우선 BST 의 특성을 유지하면서 노드를 삽입을 합니다,. 그리고 삽입된 노드의 색깔을 RED 로 지정합니다. Red 로 지정하는 이유는 Black-Height 변경을 최소화하기 위함입니다. 삽입 결과 RBT 의 특성 위배(violation)시 노드의 색깔을 조정하고, Black-Height 가 위배되었다면 rotation 을 통해 height 를 조정합니다. 이러한 과정을 통해 RBT 의 동일한 height 에 존재하는 internal node 들의 Black-height 가 같아지게 되고 최소 경로와 최대 경로의 크기 비율이 2 미만으로 유지됩니다.

 

삽입에 문제가 없는 경우

  위와 같은 경우는 문제가 되지 않는 케이스입니다. 흰색으로 표현한 것은 상황에 따라 R/B이 되는 경우인데, R/B으로 칠해진 노드만 집중해서 보기위해 흰색으로 표시했습니다.

문제의 경우

 위 그림처럼 Red node가 연속적으로 오게되면 문제가되어 추가적 조치가 필요합니다.

 

1) s가 red일 경우

 s가 red일 경우는 p와 s노드를 둘 다 black으로 바꿔주고 P의 parent node(P^2)를 red로 바꿔주는 것입니다. 하지만 parent node 또한 red였다면 추가적으로 문제가 생깁니다. 

 

 

 

2) s노드가 black이고 추가하려는 x노드가 p의 left chile일 경우

 이 같은 경우는 p노드를 중심으로 right rotate를 시키고 p노드를 red->black으로 바꿔주면 된다.

 

 

3) s노드가 black이면서 x는 p의 right chiled인 경우

이런식으로 변경하게 되면 x와 p가 연속적으로 red가 나타냈기 때문에 문제가 되는데, 이 경우 위에서 s노드가 black이고 새로운 노드가 left child인 경우에 해당되기 때문에 두번 째 경우로 이동해 추가적 처리를 하면된다.

삭제

 삭제도 삽입과 마찬가지로 BST 의 특성을 유지하면서 해당 노드를 삭제합니다. 삭제될 노드의 child 의 개수에 따라 rotation 방법이 달라지게 됩니다. 그리고 만약 지워진 노드의 색깔이 Black 이라면 Black-Height 가 1 감소한 경로에 black node 가 1 개 추가되도록 rotation 하고 노드의 색깔을 조정합니다. 지워진 노드의 색깔이 red 라면 Violation 이 발생하지 않으므로 RBT 가 그대로 유지됩니다.

Java Collection 에서 TreeMap 도 내부적으로 RBT 로 이루어져 있고, HashMap 에서의 Separate Chaining에서도 사용됩니다. 그만큼 효율이 좋고 중요한 자료구조입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

출처

https://juhee-maeng.tistory.com/94

[자료구조] 힙(Heap)이란? 최대힙(Max Heap)과 최소힙(Min Heap)

https://lemonlemon.tistory.com/135

Red-Black Tree 속성/검색/삽입/삭제