[Part2. CS] - 자료구조 (2)

Red Black Tree (출처: 위키백과)

Red Black Tree

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

 

Red-Black Tree 정의

Red-Black Tree는 다음의 성질들을 만족하는 BST이다.

1. 각 노드는 Red or Black이라는 색을 가짐

2. 루트 노드는 Black이다.

3. 각 단말 노드는 Black이다.

4. 어떤 노드의 색이 red라면 두 children의 색은 모두 black이다.

5. 각 노드에 대해서 노드로부터 자식노드 까지의 단순 경로는 모두 같은 수의 black nodes를 포함하고 있다. 이를 해당 노드의 Black-Height라고 함.

 

Red-Black Tree 특징

1. 이진 탐색 트리이므로 그 특징을 모두 갖는다.

2. 루트 노드 부터 단말 노드까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지않다. 이러한 상태를 balanced라고 한다.

3. 노드의 자식이 없을 경우 자식을 가리키는 포인터는 NIL값을 저장. 이러한 NIL들을 단말 노드로 간주한다.

 

삽입

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

 

삭제

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

 

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

 

Hash Table

hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다. 특정한 값을 Search하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대해 시간 복잡도가 O(1)이 된다. 하지만 문제는 이 인덱스로 저장되는 키값이 불규칙하다.

 

Hash Function

'특별한 알고리즘'이란 것을 통해 고유한 인덱스 값을 설정하는 것이 중요해 보인다. 이 특별한 알고리즘을 hash method 또는 해시 함수라고 하고 이 메소드에 의해 반환된 데이터의 고유 숫자 값을 hashcode라고 한다. 저장되는 값들의 key값을 hash function을 통해 작은 범위의 값들로 바꿔준다.

 

하지만 어설픈 해쉬함수를 통해 키값들을 결정한다면 동일한 값이 도출될 수가 있다. 이렇게 되면 동일한 키값에 복수개의 데이터가 하나의 테이블에 존재할 수 있게 되는데 이를 Collision이라 부른다. (Collision : 서로 다른 두개의 키가 같은 인덱스로 Hashing되면 같은 곳에 저장할 수 없게 된다.)

좋은 Hash Function이란?

일반적으로 좋은 hash function은 키의 일부분을 참조해서 해쉬 값을 만들지 않고 키 전체를 참조하여 해쉬 값을 만들어 낸다. 하지만 좋은 해쉬 함수는 키가 어떤 특성을 갖고 있느냐에 따라 달라진다.

 

hash function을 무조건 1:1로 만들기 보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능하기도 하지만 그런 hash function은 배열과 다를바 없고 메모리를 많이 차지한다.

 

Collision이 많을 수록 Search에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워진다. 좋은 해쉬함수를 선택하는 것은 해쉬 테이블의 성능향상에 필수적이다. Collision 해결 방법들에 대해 알아보자.

Resolve Conflict

해쉬 충돌을 해결하기 위한 다양한 방법들이 있지만 다음의 두 가지 방법을 응용한 것들이다.

 

1. Open Address 방식 (개방주소법)

 

해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식이다. 이 알고리즘은 Collision이 발생하면 데이터를 저장할 장소를 찾아 헤맨다. Worst Case의 경우 비어있는 버킷을 찾지 못하고 탐색 시작 위치까지 되돌아 올수도 있다. 이 과정도 여러 방법들이 존재하는데, 다음 세 가지에 대해 알아보자.

 

1. Linear Probing 순차적으로 탐색하며 비어있는 버킷을 찾을 때까지 계속 진행된다.

2. Quadratic Probing 2차 함수를 이용해 탐색할 위치를 찾는다.

3. Double hashing Probing 하나의 해쉬 함수에서 충돌이 발생하면 2차 해쉬함수를 이용해 새로운 주소를 할당한다. 위 두 가지 방법에 비해 많은 연산량을 요구한다.

 

2. Separate Chaining 방식 (분리연결법)

 

일반적으로 Open Addressing 은 Separate Chaining보다 느리다. Open Addressing의 경우 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아진다. 반면 Separate Chaining 방식은 해시 출동이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워지는 빈도를 줄일 수 있다. Java 7에서는 Separate Chaining 을 사용하여 HashMap을 구현한다. 

 

1. 연결 리스트를 사용하는 방식(Linked List) 각각의 버킷들을 연결리스트로 만들어 Collision이 발생하면 해당 bucket의 list에 추가하는 방식이다. 연결리스트의 특징을 그대로 이어받아 삭제, 삽입이 간단하다. 하지만 단점도 그대로 물려받아 작은 데이터들을 저장할 때 연결 리스트 자체의 오버헤드가 부담된다. 또 다른 특징으로는, 버킷을 계속해서 사용하는 Open Address 방식에 비해 테이블의 확장을 늦출 수 있다.

 

2. Tree 사용 방식 (RBT) 기본적 알고리즘은 Separate Chaining 방식과 동일하며 연결 리스트 대신 트리를 사용하는 방식이다. 연결리스트를 사용할 것인가와 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키값 쌍의 개수다. 데이터의 개수가 적다면 Linked List를 사용하는게 맞다. 트리는 기본적으로 메모리 사용량이 많기 때문이다. 데이터 개수가 적을 때 Worst Case를 살펴보면 트리와 Linked List의 성능상 차이가 거의 없다. 따라서 메모리 측면을 봤을 때, 데이터 개수가 적을 때는 Linked List를 사용한다.

 

Open Address vs Separate Chaining

두 방식 모두 Worst Case 에서 O(M)이다. 하지만 Open Address 방식은 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높다. 따라서 데이터의 개수가 충분히 적다면 Open Address방식이 Separate Chaining보다 더 성능이 좋다. 한 가지 차이점이 더 존재한다. Separate Chaining 방식에 비해 Open Address 방식은 버킷을 계속해서 사용한다. 따라서 Separate Chaining방식은 테이블의 확장을 보다 늦출 수 있다.

 

보조 해시 함수 : 보조 해시 함수의 목적은 키의 해시 값을 변형하여 해시 충돌 가능성을 줄이는 것이다. Separate Chaining 방식을 사용할 때 함께 사용되며 보조 해시 함수로 Worst Case에 가까워지는 경우를 줄일 수 있다.

 

해시 버킷 동적 확장(Resize)

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키값 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다. 또 애매모호한 '일정 개수 이상'이라는 표현이 등장했다. 해시 버킷 크기를 두 배로 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor라고 불린다.