[F-Lab 모각코 챌린지] 7일차 - TreeMap, Red-black Tree, Properties

• 이진 트리를 기반으로 한 Map 컬렉션
• 저장과 동시에 정렬.
  숫자: 값을 기준으로 정렬
  문자: 유니코드를 기반으로 정렬
• 일반적으로 HashMap 에 비해 성능이 떨어짐
• 내부적으로 이진 탐색 트리의 문제점을 보완한 Red-Black Tree 를 사용함 (때문에 성능은 O(log n))

Red-back tree

이진 탐색 트리의 문제점인 데이터 불균형을 해결하기 위해 만들어진 Tree
(데이터가 트리의 한 쪽 노드로 편향되게 되면 최악의 경우 O(n) 이 걸림)

특성

1. 모든 Node 는 Red/Black 중 하나여야 함
2. Root Node 는 반드시 Black
3. 모든 리프 노드는 Black
4. Red Node 의 자식은 언제나 모두 블랙이다.
   (Red 노드가 연속적으로 나타날 수 없음)
5. 모든 리프 노드에서 부모 노드로 탐색 시 Black node 의 갯수는 같다
   어떤 노드로 부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다(리프 노드 제외)

Double Red

Red-Black Tree 에서 삽입 과정에서 일어나는 문제

새로운 노드를 삽입 할 때는 항상 Red 로 삽입을 수행한다.

이럴 경우 특성-4 를 위배 하며 Double Red 문제가 발생한다.

해결 방법

• 삼촌 노드(부모 노드와 같은 depth 의 다른 노드. 위 예제 에서는 노드 7) 가 검은색이라면 Restructuring
• 삼촌 노드가 빨간색 이라면 Recoloring

Restructuring

• 삼촌 노드(부모 노드와 같은 depth 의 다른 노드. 위 예제 에서는 노드 7) 가 검은색이라면 Restructuring

1. 새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬
2. 셋 중 중간 값을 부모로 만들고 나머지 둘을 자식으로 만듬
3. 새로 부모가 된 노드를 Black 으로 만들고 나머지를 Red 로 변경

Recoloring

• 삼촌 노드가 빨간색 이라면 Recoloring

1. 새로운 노드의 부모와 삼촌을 Black 으로 바꾸고 조상을 Red 로 변경
2. 조상이 Root 라면 검은색으로 변경
3. 조상을 Red 로 변경 했을 때 Double Red 문제 발생 시, 문제가 발생하지 않을 때 까지 Restructuring, Recoloring 수행

Red-Black Tree simulator

• HashTable 을 확장하여 만들어짐
• Map 인터페이스에서 제공하는 모든 메서드를 사용 할 수 있음
• 자바에서 시스템 속성은 해당 클래스를 사용하여 만들어짐
• Properties 클래스의 사용 목적은 Properties 에서 제공하는 특수한 함수들 때문.

속성

제공 함수