Red Black Tree(RB tree)

일명 RB Tree라고 불린다. 이는 BST(Binary Search Tree)를 기반으로 하는 트리 형식의 자료구조이다.

BST의 단점은 무엇이였냐면 편향적으로 트리구조가 되어있다면 결국 Array와 다를바없이 Search시간이 O(n)의 시간이 걸리게 된다. 이 단점을 극복한게 RB Tree와 AVL Tree가 있다.
이 중에서 Java Collection의 ArrayList, HashMap에서 Separate Chaining 에서 쓰이는 RB Tree에 대해서 알아보자.

RB Tree는 Search, Insert, Delete시에 O(log n)이 걸린다. 동일한 노드의 개수일 때 depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다.

⇒ 동일한 노드일 때 depth를 최소화하는 방법은 트리 구조가 complete binary tree인 경우이다.

정의

1. 각 노드는 Red or Black 이라는 색깔을 갖는다.
2. Root Node의 색깔은 Black 이다.
3. 각 Leaf Node는 Black 이다.
4. 어떤 노드의 색깔이 Red 라면 두 개의 children의 색깔은 모두 Black이다.
5. 각 노드에 대해서 노드로부터 descendant leves까지의 단순 경로는 모두 같은 수의 Black nodes들을 포함하고 있다.
   이를 해당 노드의 Black-Height 라고 한다.

특징

1. BST의 특징을 갖는다.
2. Root Node부터 Leaf Node까지의 모든 경로중 최소 경로와 최대 경로의 크기 비율은 2보다 크지 않다.
3. 노드의 child가 없을 경우 child를 가리키는 포인터는 NIL 값을 저장한다. NIL들을 Leaf Node로 간주한다.

Insert시 전략

Root노드는 Black이고, 추가되는 노드들은 무조건 Red이다.

그러면 4. 어떤 노드의 색깔이 Red 라면 두 개의 children의 색깔은 모두 Black이다. 를 위반할 수 있다.

이걸 어떤 식으로 해결할까?

2가지의 전략을 이용해 해결한다.
바로 Restructuring , Recoloring 이다.

Restructuring

내 부모의 형제(삼촌)가 Black일 경우에 진행한다.

1. 내 부모의 부모, 부모, 나 ⇒ 오름차순으로 정렬한다.
2. 가운데 있는 값을 부모 로 설정하고, 나머지는 자식 노드로 설정한다.
3. 부모 를 검정색으로 변경한 뒤, 자식 노드 들을 빨간색으로 변경한다.

음.. 생각하자면 트리를 회전한다고 생각하면 된다. 오른쪽으로 기울어져 있으면 왼쪽으로 회전, 왼쪽으로 기울어져 있으면 오른쪽으로 회전한다고 생각하자.

Recoloring

내 부모의 형제(삼촌)가 Red일 경우에 진행한다.

1. 내 부모와 삼촌(내 부모의 형제)을 Black으로 변경한다. 그리고 내 부모의 부모는 Red로 변경한다.
2. 이 때, 내 부모의 부모의 부모에게 Double Red으로 위반할 수 있다.
   이 때도 해당 트리에 대해서 Resturcturing, Recoloring을 진행한다.

Delete시 전략

삭제 노드가 빨간색일 경우

그냥 해당 노드를 삭제하면 된다. 제일 간단한 경우.

삭제 노드가 검정색일 경우

검정색 노드를 삭제할 땐 여러가지를 해당 경우를 따져봐야한다.

1. 자식이 빨간색 노드일 경우

현재 노드를 삭제한 후, 자식을 검정색 노드로 변경하면 된다.

2. 자식이 검정색 노드일 경우

삭제 노드를 없애면 5. 각 노드에 대해서 노드로부터 descendant leves까지의 단순 경로는 모두 같은 수의 Black nodes들을 포함하고 있다.에 대해 위반하게 된다. Black Nodes의 개수가 달라지는 것이다.
그렇기 때문에 부모의 서브트리 2개를 동시에 봐야한다.

그림으로 보는게 편하기 때문에
https://assortrock.com/88
https://itstory.tk/entry/레드블랙-트리Red-black-tree
여기를 참고하는게 좋아보인다. 나중에 시간이 나면 정리해야겠다.

RB Tree에 대해서 잘 이해가 안간다면 해당 사이트에서 직접 해보면 이해에 도움이 될 것이다.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

참고
https://lemonlemon.tistory.com/135
https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree
https://zeddios.tistory.com/237
https://itstory.tk/entry/레드블랙-트리Red-black-tree
https://assortrock.com/88