Skip to main content Link Search Menu Expand Document (external link)
Dev.chanul

22.10.31

Red-Black Tree

Deletion

레드-블랙 트리의 삭제는 기본적으로 이진 탐색 트리의 삭제를 기반한다.
이진 탐색 트리와 같이 노드를 삭제한 후에 레드-블랙 트리의 규칙을 복원하는 과정이 필요할 수 있다.
삭제되는 노드의 색상이 Red라면 아무 문제가 없지만 Black이라면 레드-블랙 트리 규칙에서 벗어나기 때문이다. 삭제하려는 노드를 M, 자리를 대체하는 노드를 C, 삭제하려는 노드의 형제를 S라고 나타내기로 한다.
Black노드를 제거하여 규칙에서 벗어나는 상황은 다음과 같다.

  1. C가 Red인 경우 : C의 색상을 Black으로 변경
  2. C가 Black인 경우 : Double Black 처리

C가 Black이라면 레드-블랙 트리의 다섯번째 조건를 위반하기 때문에 구조를 변경하여 조건을 충족시켜야 한다.
삭제하려는 노드의 형제인 S의 왼쪽 자식을 SL, 오른쪽 자식을 SR이라고 나타내기로 하며, C가 S의 왼쪽에 있다고 가정한다.
다음과 같이 상황에 따라서 Double Black를 해결하는 방법이 다르다. 또한, 밸런스를 복구하는 작업은 루트에 도달하기 전까지 계속될 수 있다.

  1. S가 Red인 경우
1
2
3
4
5

if (s.color == RED)
	s.color = BLACK
	c.p.color = RED
	left_rotate(x.p)
	s = x.p.right
  1. S가 Black이고, SL, SR이 모두 Black인 경우
1
2
3

if (s.left.color == BLACK && s.right.color == BLACK)
	s.color = RED
	c = c.p
  1. S가 Black이고, SL은 Red, SR은 Black인 경우
1
2
3
4
5

if (s.right.color == BLACK)
	s.left.color = BLACK
	s.color = RED
	right_rotate(s)
	s = c.p.right
  1. S가 Black이고, SR이 Red인 경우
1
2
3
4
5

s.color = c.p.color
c.p.color = BLACK
s.right.color = BLACK
left_rotate(c.p)
c = root

Allocator rebind

중첩 템플릿 구조체인 rebind는 STL allocator를 만들 때 반드시 제공해야 한다.
만약에 노드 기반 컨테이너에 어떠한 자료 T를 저장한다면 컨테이너는 T를 노드 객체로 rebinding하여 저장한다.
이때 다른 객체를 할당하기 위해서 rebind를 사용한다. T 타입의 allocator로 할당한다면 컴파일시 에러가 발생된다.
vector를 제외한 나머지 컨테이너들은 해당 T 타입이 아닌 별도의 타입으로 저장하기 때문에 rebind를 사용한다.
list의 경우를 살펴보면 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

template <class T>
class allocator {
  
// ...

template <class U>
  struct rebind { typedef allocator<U> other; };

// ...

template <class U>
  allocator(const allocator<U>&);
};

template <class T, class Allocator = allocator<T> >
class list {
private:
typedef  . . .  listnode;
typedef typename Allocator::rebind<listnode>::other Node_allocator;

Node_allocator alloc_;

list_node* make_node() 
  { return new(alloc_.allocate(1)) list_node; }

public:
list(const Allocator& a = Allocator())
  : alloc_(a) { }  // implicit conversion
. . .

};
  • 참조 : http://egloos.zum.com/sweeper/v/2966785, https://rookiecj.tistory.com/118

22.10.28

Red-Black Tree

레드-블랙 트리(Red-Black Tree)는 균형 이진 탐색 트리이다. 복잡한 자료구조이지만 효율적이고 우수한 실행 시간을 보인다. 트리에 n개의 요소가 있을때 O(log n)의 시간복잡도로 탐색, 삽입, 제거를 할 수 있다.

이진 트리의 특수한 형태로 레드-블랙 트리는 각각의 자료를 노드에 저장한다.
노드는 최대 두 개의 자식 노드를 가질 수 있고, 자식 노드도 최대 두 개의 자식 노드를 가질 수 있어서 이런식으로 계속 연결된다.
어떤 노드에 자식 노드가 없다면 트리의 가장 자리에 있다고 하여 그 노드를 리프 노트라고 한다. 레드-블랙 트리의 리프 노드는 자료를 가지고 있지 않으며 비어 있다.
보통 이진 탐색 트리에서 노드들은 다음과 같은 관계를 가지고 있다. 자신이 가진 자료는 자신의 왼쪽에 있는 노드가 가진 자료보다 크거나 같고, 자신의 오른쪽에 있는 노드가 가진 자료보다 작거나 같다.

레드-블랙 트리는 각각의 노드가 Red 또는 Black인 색상 속성을 가지고 있는 이진 탐색 트리이다.
다음과 같은 조건을 충족해야 유효한 레드-블랙 트리라고 한다.

  1. 노드는 Red 또는 Black이다.
  2. 루트 노드는 Black이다.
  3. 모든 리프 노드는 Black이다.
  4. Red 노드의 자식 노드는 모두 Black이다.
  5. 어떤 노드에서 시작하여 하위의 리프 노드에 도달하는 경로에 있는 Black 노드의 개수는 모두 같다.

이러한 조건을 만족하면 레드-블랙 트리이며 개략적으로 균형이 잡힌다. 최악의 경우에 시간복잡도가 트리의 높이에 따라 결정되기 때문에 보통의 이진 탐색 트리보다 효율적이라고 할 수 있다.
레드-블랙 트리의 특성을 만족하며 동작하기 위해서는 색 변환과 트리 회전이 필요하다. 삽입과 삭제가 복잡하게 동작하지만 복잡도는 여전히 O(log n)이다.

Insertion

레드-블랙 트리의 삽입은 노드의 색상 속성을 Red로 정하며 시작한다. 단순 이진 탐색 트리에서 노드를 삽입하듯이 노드를 위치한다.
그리고 주위 노드와의 관계를 확인하는데 삼촌 노드(uncle node) 개념을 도입한다. 삼촌 노드는 부모 노드 옆에 있는 노드이다.
노드를 관계를 다음과 같이 명시하도록 한다. 삽입하는 노드는 N, N의 부모 노드를 P, P의 부모를 G, N의 삼촌 노드를 U로 나타내기로 한다.

Red인 P노드에 Red인 N노드가 삽입되면 “Red 노드의 자식 노드는 모두 Black이다”라는 조건을 위반한다.
이를 Double Red이라고 부르며 U노드의 색상에 따라서 해결방법이 달라진다.

  1. U노드가 Red인 경우 : Recoloring
  2. U노드가 Black인 경우 : Restructuring

Recoloring

Double Red인 상황에서 삼촌인 U노드가 Red라면 Recoloring을 한다.
P노드와 U노드를 Black으로 변경하고, 조부모인 G노드를 Red로 변경한다.
색상을 변경한 이후에 G노드를 확인해야 한다. 다음과 같이 두 가지 상황이 있을 수 있다.

  1. G노드가 root인 경우 : G노드를 Black으로 변경
  2. G노드로 인해 Double Red가 발생된 경우 : G노드의 상위 노드에 대하여 Recoloring 또는 Restructuring을 진행

두 번째 상황은 G노드의 부모 노드의 색상이 Red인 경우이다. Double Red가 발생되기 때문에 N노드을 삽입할 때 발생한 경우와 마찬가지로 처리하면 된다.

Restructuring

Double Red인 상황에서 삼촌인 U노드가 Black이라면 Restructuring을 한다.
다음에 나오는 방향은 U노드가 G노드의 왼쪽 자식이라고 가정한 경우이다. 만약에 오른쪽 자식이라면 방향을 반전시켜야 한다.

Restructuring은 부모인 P노드의 어느 쪽에 N노드가 연결되어 있는지에 따라서 달라진다.

  1. N노드가 P노드의 오른쪽인 경우 : G노드 회전
  2. N노드가 P노드의 왼쪽인 경우 : P노드 회전 후 G노드 회전
G노드 회전

G노드는 U노드의 위치로 이동하고, P노드는 기존 G노드의 위치로 이동하여 반시계 방향으로 회전하듯이 위치가 변경된다.

  1. G노드를 P노드의 왼쪽 자식으로 연결
  2. 기존 P노드의 왼쪽 자식은 G노드의 오른쪽 자식으로 연결
  3. 노드의 색상을 변경한다. G노드는 Red, P노드는 Black
P노드 회전

P노드는 N노드의 오른쪽으로 이동하고, N노드는 기존 P노드의 위치로 이동하여 시계 방향으로 회전하듯이 위치가 변경된다.

  1. P노드를 N노드의 오른쪽 자식으로 연결
  2. 만약에 기존 N노드의 오른쪽에 자식이 있었다면 P노드의 왼쪽에 연결
  3. N노드를 P노드가 연결되어 있던 G노드의 오른쪽에 연결

위의 과정을 마치면 G노드 회전을 해야하는 조건이 만들어지므로 다시 한번 회전시킨다.

  • 참조 : https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC, https://zeddios.tistory.com/237, https://www.youtube.com/watch?v=5IBxA-bZZH8&list=RDCMUCzDJwLWoYCUQowF_nG3m5OQ&index=2, https://www.youtube.com/watch?v=iw8N1_keEWA&list=RDCMUCzDJwLWoYCUQowF_nG3m5OQ&index=6, https://assortrock.com/88

22.10.26

c++ map

map은 key value와 mapped value가 쌍으로 정렬되어 저장되는 연관 컨테이너이다. map에서 key value는 요소를 정렬하고 고유하게 식별하는 데 사용되며, mapped value는 key와 연결된 컨텐츠를 저장한다.
key value와 mapped value는 서로 타입이 다를 수 있으며, 두 가지를 결합한 pair 타입인 value_type 멤버 타입으로 그룹화된다.
내부적으로 map은 key를 Compare 객체로 비교하여 정렬한다.
mapped value는 대괄호 연산자(operator[])에 사용하여 해당 key로 직접 접근할 수 있다.
일반적으로 이진 탐색 트리로 구현되어 있다.

  • 참조 : https://cplusplus.com/reference/map/map/

binary_function

C++11에서 더 이상 사용되지 않는 클래스이지만 C++98에서 std::less<T> 클래스가 이를 상속받아 구현되었기 때문에 찾아보았다.
일반적으로 함수 개체는 operator() 맴버 함수가 정의된 클래스이다. 이 맴버 함수를 사용하면 일반 함수 호출과 동일한 구문으로 개체를 사용할 수 있으므로 binary_function 타입을 템플릿 매개 변수로 사용할 수 있다. 이 경우에 operator() 맴버 함수는 두 개의 매개 변수를 사용한다. std::less<T>는 다음과 같이 구현될 수 있다.

1
2
3
4
5
6
7
8
9
10
11

template <class Arg1, class Arg2, class Result>
struct binary_function {
  typedef Arg1 first_argument_type;
  typedef Arg2 second_argument_type;
  typedef Result result_type;
};

template <class T> 
struct less : binary_function <T, T, bool> {
  bool operator() (const T& x, const T& y) const {return x < y;}
};

std::less<T> 클래스는 C++11에서 다음과 같이 변경되었다.

1
2
3
4
5
6
7

template <class T> 
struct less {
  bool operator() (const T& x, const T& y) const {return x<y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};
  • 참조 : https://cplusplus.com/reference/functional/less/, https://cplusplus.com/reference/functional/binary_function/

pair

이 클래스는 서로 다른 타입의 값 쌍을 연결한다. 개별 값은 공개 맴버인 first와 second를 통해 접근할 수 있다.

22.10.25

reverse_iterator

역방향 반복자는 반복자의 방향을 바꾸는 반복자 어댑터이다. 양방향 반복자가 역방향 반복자가 되면 끝에서 시작으로 이동하는 새로운 반복자를 생성한다. 반복자 i에서 생성된 역방향 반복자 r의 경우에 &*r == &*(i-1) 관계가 항상 true이다. 반복자가 반전될 때에 동일한 요소가 아니라 그 앞에 있는 요소를 가리킨다. 이는 반복자의 마지막 요소를 정렬하기 위함이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// reverse_iterator example
#include <iostream>     // std::cout
#include <iterator>     // std::reverse_iterator
#include <vector>       // std::vector

int main () {
  std::vector<int> myvector;
  for (int i=0; i<10; i++) myvector.push_back(i);

  typedef std::vector<int>::iterator iter_type;
  iter_type from (myvector.begin());
  iter_type until (myvector.end());
  std::reverse_iterator<iter_type> rev_until (from);          
  std::reverse_iterator<iter_type> rev_from (until);
  
  // ? 9 8 7 6 5 4 3 2 1 0 ?
  //   ^
  //       ---iter--->
  //                       ^
  //
  // ^
  //      <---r_iter---
  //                     ^

  std::cout << "myvector:";
  while (rev_from != rev_until)
	std::cout << ' ' << *rev_from++;
  std::cout << '\n';

  return 0;
}

explicit keyword

explicit 키워드는 원하지 않는 형변환이 일어나지 않도록 제한하는 키워드이다. 함수에 명시된 타입과 다른 타입의 인자가 들어온다면 자동적으로 형변환을 위해 생성자가 호출된다. 컴파일러가 알아서 형변환하는 상황에는 예상하지 못한 버그가 발생될 수 있기 때문에 explicit 키워드로 이를 방지할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>
class A{
public:
   int num;
   explicit A(int n) : num(n){};
};
void printA(A a){
   std::cout << a.num << std::endl;
}
int main(){
   int n = 26;
   printA(n); //Error!
}
  • 참조 : https://dydtjr1128.github.io/cpp/2019/07/13/Cpp-explicit-keyowrd.html

22.10.07

type traits

C++에서 traits는 어떻게 사용되는지 확인하기 위해서 type traits를 알아본다. type traits는 C++ 템플릿 메타 프로그래밍에서 유용하게 쓰이는 기술 중에 하나이다. type traits를 이용하여 type의 다양한 속성들에 대해 조사하거나 프로퍼티를 변경할 수 있다. 예를 들어 제네릭 타입인 T가 있는 경우, 제네릭 인자로 넘어온 타입 T에 따라서 컴파일되는 코드가 달라지는 조건부 컴파일에 사용된다. 그리고 특정 타입에 const를 붙이거나 제거하거나 참조로 만들거나 포인트로 만들어 타입을 변형하는데 사용된다. 이 모든 것이 컴파일 타임에 완료되어 실행 시간의 패널티 없이 동작한다. 이를 바로 메타 프로그래밍이라고 한다.

iterator_traits

iterator_traits는 반복자의 속성을 정의하는 클래스이다. 템플릿은 컴파일 타임에 인스턴스화되기 때문에 컴파일 타임에 조건에 따른 처리를 위해 traits 클래스를 사용한다. 템플릿 클래스를 사용하다보면 흔히 발생할 수 있기 때문에 반복자 이외에도 라이브러리에서 쉽게 찾아 볼 수 있다.