[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree)

Red-Black Tree

Binary Search Tree를 기반으로 하는 자료구조.

동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어.

연산

• 삽입 insert : O(lon N)
• 조회 search : O(log N)
• 삭제 delete : O(log N)

정의

• 레드 블랙 트리는 다음의 성질들을 만족하는 BST(이진 탐색 트리) 이다.

  1. 모든 노드는 Red(빨강) or Black(검정) 의 색을 갖는다.
  2. 루트 노드는 검정색이다.
  3. 모든 리프 노드들은 검정색이다.
  4. 레드 노드의 자식은 모두 검정색이다
  5. 모든 리프 노드에서 Black Depth는 같다.

  • 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

  6. 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 모두 같은 수의 black nodes 들을 포함하고 있다.
     1. 이를 해당 노드의 Black-Height 혹은 Black Depth라고 한다.
     2. Black-Height: 노드 x 로부터 노드 x 를 포함하지 않은 leaf node 까지의 simple path 상에 있는 black nodes 들의 개수

특징

• Binary Search Tree 이므로 BST 특징을 모두 갖는다.

• 루트 노드로부터 리프 노드까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다.

  • 이러한 상태를 balanced 상태 라고 한다

• 노드의 자식(child)가 없을 경우 child를 가리키는 포인터는 NIL(NULL)값을 저장한다.

  • 이러한 NIL 들을 리프 노드로 간주한다.

삽입

• 우선 BST 특성을 유지하면서 노드를 삽입한다.

• 삽입된 노드의 색을 Red로 지정한다.

  • Red로 지정하는 이유는 Black-Height(Black Depth) 변경을 최소화 하기 위해

• 삽입하려는 위치의 부모가 블랙 일경우 아무 문제 없이 삽입된다.

• 삽입 결과 레드블랙트리의 특성 위배(부모 노드의 색이 레드 일경우) 시 노드의 색깔을 조정하고 Black-Height가 위배 되었다면 회전을 통해 Height를 조절한다.

• 참조

레드 블랙 트리에 새로운 노드를 삽입할 떄 새 노드는 항상 빨간색이다.

레드 노드의 자식은 모두 검정색인데 이렇게되면 레드 노드의 자식은 모두 검정색이다 라는 조건을 위배한다.

• Double Red : 빨간색 노드가 연속으로 2번 나타나는것.

• 이 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다.

• • [참조](https://code-lab1.tistory.com/62

• N (New) : 새로 삽입할 노드

• P (Parent) : 부모 노드

• G (Grand Parent) : 조상 노드

• U (Uncle) : 삼촌 노드

• 삼촌 노드가 검은색이라면 -> Restructuring (구조 재조정, Rotate 회전이라고도 함) 수행
• 삼촌 노드가 빨간색이라면 -> ReColoring (컬러 재설정) 수행

Resturcturing (구조재조정 = Rotate )

삼촌 노드가 검은색일때만 Resturcturing을 한다.

1. 나(z)와 내 부모(v), 내 부모의 부모(Grand Parent)를 오름차순으로 정렬
2. 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 중간값(부모, 부모가 된 중간 값)을 검정(Black)으로 만들고 그 두자식들을 빨강(Red)로 만든다. 

• 삽입의 회전에는 좌 회전, 우 회전이 있다.
  • 우회전은 부모의 부모 (조상, 할아버지) 와 부모의 왼쪽 자식과 위칙을 바꾸는것
    • 우회전을 할 때에는 왼쪽 자식노드의 오른쪽 자식 노드를 부모 노드의 왼쪽 자식으로 붙여줘야 한다.
  • 좌회전은 부모의 부모 (조상, 할아버지)와 부모의 왼쪽 자식과 위치를 바꾸는것
    • 오른쪽 자식 노드의 왼쪽 자식 노드를 부모 노도의 오른쪽 자식으로 연결한다.

• 삽입하려는 노드와, 부모와, 할아버지의 중간값을 부모로 만들고, 부모가 된 중간값을 블랙 노드로

• 부모가 되지 않은 남은 두 노드(셋중에 누가 중간값? 누가 부모가 될지 모름) 더 작은값을 왼쪽자식, 큰값을 오른쪽 자식으로 변경

• 부모가 되지않은 두 노드의 색을 빨강으로 만든다.

• 시각화 : https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

ReColoring( 컬러 재설정)

삼촌 노드가 빨간색(Red) 라면 ReColoring 수행

• 핵심은, ReColoring 시에 블랙 노드가 2번 연속으로 나와도 된다.

  • 레드 노드(빨강) 만 연속으로 2번 나오지만 않으면 된다.

• 루트 노드는 무조건 검은색이여야 한다.

  • 리컬러링을 수행하고, 루트노드가 레드가 되면,
    • 루트노드를 블랙으로 바꾸고, 바로 두 자식 노드도 블랙으로 바꿔도 된다.

삭제

만약 삭제하려는 노드가 Red면 그 노드만 삭제하고 부모랑 연결하고,

삭제하려는 노드가 Black 이고 child Node가 red 라면 해당 Black 노드를 삭제해주고 자식을 Black으로 바꿔준다

그러나 삭제하려는 노드와 그 자식 노드가 모두 Black일 경우 문제가 된다.

다음 규칙 을 위반하기 때문.

리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

• https://velog.io/@youngcheon/자료구조-Red-Black-Tree-삭제-구현

• https://blogshine.tistory.com/102

• 추가 학습 https://lemonlemon.tistory.com/135

• https://www.cs.usfca.edu/~galles/visualization/RedBlack.html