Tree / Heap

Tree

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

용어

• 루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다.

• 단말 노드(leaf node) : 자식이 없는 노드이다.

• 내부(internal) 노드 : 리프 노드가 아닌 노드.

• 링크(link) : 노드를 연결하는 선 (edge, branch 라고도 부름).

• 형제(sibling) : 같은 부모를 가지는 노드.

• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수.

B의 크기 : 6

• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

D의 깊이 : 2 H의 깊이 : 3

• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합

A의 레벨 : 1

• 노드의 차수(degree) : 부(하위) 트리 갯수/간선수 (degree) = 각 노드가 지닌 가지의 수

A의 차수 = 2 E의 차수 = 1

• 트리의 차수(degree of tree) : 트리의 최대 차수

• 트리의 높이(height) : 리프노드에서 부터 자기 자신까지의 높이

C의 높이 = 1 B의 높이 = 2

Binary Tree

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

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

이진트리 vs 완전이진트리 vs 포화 이진트리

완전 이진 트리(complete binary tree)

높이가 k일 때, 레벨 1부터 k-1까지는 노드가 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리로, 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만, 중간에 빈 곳이 있으면 안 된다.

포화 이진 트리(full binary tree)

각 레벨에 노드가 꽉 차 있는 이진 트리로, 각 노드에 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있다. 부여된 번호는 항상 일정하다.

BST(Binary Search Tree)

효율적인 탐색을 위해서는 어떻게 찾을까만 고민해서는 안된다. 그보다는 효율적인 탐색을 위한 저장방법이 무엇일까를 고민해야 한다. 이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다.

• 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 규칙 2. 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
• 규칙 3. 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
• 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

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

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

AVL Tree

AVL 트리(AVL tree)는 가장 초기에 나온 균형 잡힌(balanced) 이진 탐색 트리이다.

모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하입니다. 위의 그림에서 좌우 높이 차이가 1보다 큰 트리를 찾을 수 있나요? 없죠. 이렇게 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장할 수 있습니다.

AVL 트리에서는 높이차이가 발생하면 회전을 하게 되는데 single rotation과 double rotation이 있습니다.

Single Rotation

삽입 연산시 single rotation은 다음과 같은 방식으로 수행합니다.

single rotation은 rotation을 한 차례 수행해 위와 같이 원하는 결과를 얻을 수 있는 경우를 가리킵니다. 삽입 연산의 single rotation은 다음 두 가지 경우에 V(U의 자식노드, BF 절대값이 1이하)를 중심으로 실시합니다. (U는 BF의 절대값이 2 이상이면서 새 노드와 가장 가까운 조상 노드)

• V가 U의 왼쪽 자식노드, V의 왼쪽 서브트리에 새 노드 삽입 : V를 기준으로 right rotation
• V가 U의 오른쪽 자식노드, V의 오른쪽 서브트리에 새 노드 삽입 : V를 기준으로 left rotation

Double Rotation

rotation 한 차례만으로 원하는 삽입 결과를 내지 못하는 케이스가 존재합니다. 다음 두 가지 경우 double rotation을 수행해 줍니다.

• V가 U의 왼쪽 자식노드, V의 오른쪽 서브트리에 새 노드 삽입
• V가 U의 오른쪽 자식노드, V의 왼쪽 서브트리에 새 노드 삽입

Red Black Tree

RB 트리는 다음 다섯 가지 속성을 만족하는 이진탐색트리(Binary Search Tree)의 일종입니다.

1. 모든 노드는 빨간색, 검은색 둘 중 하나다.
2. 루트노드는 검은색이다.
3. 모든 잎새노드(NIL)는 검은색이다.
4. 어떤 노드가 빨간색이라면 두 개 자식노드는 모두 검은색이다. (따라서 빨간색 노드가 같은 경로상에 연이어 등장하지 않는다)
5. 각 노드~자손 잎새노드 사이의 모든 경로’에 대해 검은색 노드의 수가 같다.

RB 트리의 예는 다음 그림과 같습니다. 위 다섯가지 속성을 만족하고 있음을 확인할 수 있습니다.

삽입

삽입에는 ReStructing, ReColoring 두 가지 케이스가 있는데 아래 블로그에 정리가 잘 되어있으니 들어가서 확인해보시면 될거같습니다.

알고리즘 ) Red-Black Tree

ResStructing은 한 번만 수행해도 됩니다. 하지만, ReColoring일 경우 4가 루트노드일 경우 흑색으로 변경이 됩니다.

만약 4번이 루트노드가 아니고 4위에 또 빨간 노드가 있을경우 Double Red가 생김으로 상황에따라 Recoloring과 Restructuring을 수행하게 됩니다.

즉, Recoloring의 경우 Restructuring과 다르게 propagation될 수 있습니다.

최악의경우 루트노드까지 갈 수 있게되죠.

B- Tree

B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다.

삽입

• 자료는 항상 Leaf 노드에 추가된다.

• Leaf 노드 선택은 삽입될 키의 하향 탐색에 의하여 결정된다.

• 추가될 Leaf 노드에 여유가 있다면, 그냥 삽입

• 여유가 없다면 노드를 분할한다.

• 분할을 위해서는 키 하나를 부모로 올려야 한다.

• 부모에 여유가 없다면? : 삽입을 위한 하향 탐색을 하면서 꽉 찬 노드는 미리미리 분할을 해줘야 한다.

루트 노드에서 일어나는 경우

서브 노드에서 일어나는 경우

삭제

• 삭제하려는 자료가 있는 노드는 삭제 후에도 m/2 이상의 자료수를 유지해야 한다.

• 만약 자료수가 m/2이하로 된다면 Underflow가 발생하여 형제노드에서 가져온다. 하지만, 형제노드에서 가져올 수 없는경우 루트노드와 병합한다.

형제 노드에서 가져올 수 있는 경우

형제 노드에서 가져올 수 없는 경우

B + Tree

B+ 트리(Quaternary Tree라고도 알려져 있음)는 컴퓨터 과학용어로, 키에 의해서 각각 식별되는 레코드의 효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한 트리자료구조의 일종이다.

이는 동적이며, 각각의 인덱스 세그먼트 (보통 블록 또는 노드라고 불리는) 내에 최대와 최소범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성된다.

B트리와 대조적으로 B+트리는, 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어있다. 오직 키들만이 내부 블록에 저장된다.

삽입

먼저 검색을 실시함으로써 어떤 버킷(공간)에 새로운 레코드를 넣을지를 결정한다.

• 만약 버킷이 꽉차있지 않다면(삽입후 최대 b-1개의 엔트리), 레코드를 추가한다.
• 버킷이 꽉차있다면, 버킷을 쪼갠다.
  • 새로운 단말노드의 메모리를 확보하고, 버킷에 든 구성요소의 절반을 새로운 노드로 옮긴다.
  • 새 단말노드의 최소 키를 부모에게 삽입한다.
  • 만약 부모가 꽉찼다면, 부모 역시 쪼개도록 한다.
    • 부모노드에게 중간키를 추가한다.
  • 쪼개지지 않는 부모를 발견할 때까지 이를 반복한다.
• 루트가 쪼개졌다면, 새로운 루트를 만드는데 이 루트는 1개의 키와 2개의 포인터를 지녀야 한다.(즉, 새 루트로 올라간 값은 기존 노드에서 사라진다.)

Example

키는 부모노드로 올라가고 데이터들은 리프노드에서 연결리스트로 묶이는걸 볼 수 있다.

삭제

• 루트에서 시작하여, 엔트리가 속한 단말노드 L을 찾는다.

엔트리를 삭제한다.

• L이 절반이상 차있다면 종료한다.
• L이 절반 이하라면,
  • 형제(L과 동일한 부모를 가진 인접노드)가 절반 초과라면, 재분배하고 엔트리를 빌려온다.
  • 형제의 엔트리들이 정확히 절반일경우에는 L과 형제를 병합한다.
• 병합이 일어났다면, L의 부모로부터 삭제된 노드를 가리키는 포인터를 삭제한다.
• 병합은 루트까지 전파되어, 트리의 높이를 감소시킬 가능성이 있다.

Example 1

그림 2, 3과 같이 형제노드에서 가져올 수 없는경우 병합한다. 아래는 가져올 수 있는 경우다.

Example 2

B* Tree

B tree의 문제점은 구조를 유지하기 위해 추가적으로 연산을 해야한다는 것, 하지만 대부분의 동작 방식은 비슷하다.

Knuth에 의해 제안된 B* 트리는 이러한 문제를 보안하기 위해 나왔으며 Btree에서 최소 2/M의 키값을 가져야한다는 점을 2/3의 키값을 가져야한다고 변경한것이다.

그림으로 보면 차이를 쉽게 알 수 있다.

오버플로우가 발생하여도 형제노드에 공간이 있으면 부모 노드와 재정렬을 한다.

형제노드까지 모두 노드가 가득차서 넣을 수 없는경우에 아래 그림처럼 나눈다. 이 방식이 기존의 B트리와 가장 큰 차이를 가지게 됩니다.

Heap

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

Min Heap

Max Heap

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

Max heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complexity 이 O(1)이다. 그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. (즉, random access 가 가능하다. Min heap 에서는 최소값을 찾는데 소요되는 연산의 time complexity 가 O(1)이다.) 하지만 heap 의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 여기서 heap 은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다. 이런 경우에는 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 된다.

Trie

트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 우리가 원하는 원소를 찾는 작업을 O(n)에 해결 할 수 있는 자료구조입니다.