2강 : 꼬리재귀, 매개변수 다형성, 사용자 정의 타입
3강 : 커링, 스테이징, map, filter, fold
오늘은 우리가 5강에서 배운 모듈을 활용해 균형 이진 탐색 트리의 일종인 레드-블랙 트리를 구현해 볼 것이다.
근데 다 쓰고나서 보니 모듈에 대한 내용은 거의 없네... 그냥 레드-블랙 트리에 대한 강의라 생각해주면 좋겠다.
1. 불변속성
자료구조의 불변속성(Representation Invariant)이란 그 자료구조에 대해 항상 참이여야 하는 것들을 말한다.
예를 들어 균형 이진 탐색 트리의 불변속성은 트리가 균형잡혀 있다는 것이다.
자료구조를 구현하는 코드를 짤때는 항상 함수가 불변속성을 위반하지는 않는지, 만약 그렇다면 다시 불변속성을 만족하도록 어떻게 고칠건지 생각해야 한다.
2. 레드-블랙 트리의 정의
레드-블랙 트리는 O(log n) 탐색과 O(log n) 삽입을 보장하는 균형 이진 탐색 트리의 일종이다.
레드-블랙 트리의 각 노드는 검정색이거나 붉은색이다.
레드-블랙 트리의 불변속성은 다음과 같다.
a) 이진 탐색 트리이다. (노드가 “정렬”되어 있어서 한 노드의 값은 왼쪽 서브트리의 모든 값보다 높거나 같고 오른쪽 서브트리의 모든 값보다 작다.
b) 붉은색 노드의 자식 노드는 검정색이다.
c) 루트 노드에서 출발하여 잎 노드까지 도달하는 모든 경로는 같은 수의 검정색 노드를 가지고 있다. 이걸 흑색높이(black height)라고 한다.
*여러 블로그에 가보니까 블랙높이라고도 하고 원문 그대로 하는 곳도 있었는데 흑색높이가 제일 간지나니까 이 글에서는 흑색높이라고 부르겠다.
레드-블랙 트리의 예시는 다음과 같다.
루트 노드에서부터 잎까지 다다르는 모든 경로가 3개의 검정색 노드를 지나므로 흑색높이는 3이다.
이제 루트 노드에서 잎까지 다다르는 가장 짧은 경로를 생각해보자. c)에 의해 다른 모든 경로는 그 경로와 같은 흑색높이를 갖는다. 가장 긴 경로조차도 가장 짧은 경로와 흑색높이가 같다. 이 흑색높이를 bh라고 두자.
그렇다면 가장 긴 경로에는 몇개의 붉은색 노드가 있을까?
b)에 의하면 붉은색 노드는 연속으로 두개 있을 수 없으므로 검정색 노드 하나당 붉은색 노드는 최대 한개 있을 수 있다.
따라서 가장 긴 경로도 최대 bh + 1개의 붉은색 노드가 있으므로 최대 2bh + 1개의 노드가 있다.
아무 두 경로나 선택했을때 그 둘의 길이은 최대 2배밖에 차이가 안나므로 트리는 O(log n) 탐색과 삽입을 할 수 있다. (여기서 증명하지는 않겠지만 트리의 높이 ≤ 2 log (n + 1)이 성립한다.)
3. 불변속성 유지하기
불변속성이 참이라면 O(log n)탐색과 삽입을 할 수 있다는 사실을 알았다. 그렇다면 이 불변속성을 어떻게 유지할 수 있을까?
간단히 말해 우리는 insert등의 함수를 구현할때 불변속성을 잠시 깨뜨렸다가 바로 복원할 것이다.
아래 트리에 2를 삽입한다고 하자. 2 노드의 색깔을 무엇으로 해야 할까? 검은색이라면 불변속성 c)를 깨뜨리니 안된다. 흑색높이가 달라지기 때문이다.
하지만 붉은색이라면 불변속성 b)를 깨뜨린다. 붉은색 노드의 자식은 붉은색이 될 수 없다! b)를 깨뜨리는걸 red-red violation이라고 부른다.
그렇다면 어떻게 할까? 일단 붉은색으로 칠한뒤에 트리를 회전시켜서 b)와 c)를 만족시키도록 할것이다. 다음과 같이 말이다.
b)와 c)를 둘다 만족시키는 색깔 배치는 다음과 같다. (흑색높이가 같고, red-red violation이 일어나지 않게 하는 배치)
다만 우리는 두번째보다는 첫번째 방식을 택할 것이다. 만약 1에 붉은색 자식 노드가 있었다면 두번째 방식은 red-red violation이 일어나기 때문이다.
이처럼 일단 삽입하는 노드는 붉은색으로 칠하고, 불변조건을 깨뜨린다면 트리를 회전시킨 후 다시 칠하는 방식으로 불변조건을 만족시킬 것이다.
red-red violation이 일어날때를 생각해보자. 맨 아래 노드를 방금 삽입했다고 하고, 그 노드의 자식들은 빈 트리라고 치자 (빈 트리지만 일단 삼각형으로 표시는 하겠다).
그렇다면 맨 위 노드는 원래 불변조건을 만족시키므로 검정색이여야 한다. 따라서 이와 같이 네가지 경우가 있다.
저 네가지 경우를 전부 다음과 같은 모습으로 “회전” 시킬 것이다. 이렇게 회전시키면 절대 1, 2, 3, 4 서브트리에서 red-red violation이 일어나지 않는다.
하지만 만약 y의 부모 노드가 붉은색이였다면? 그렇다면 red-red violation이 일어나지 않는가? 그렇다면 다시 이 회전을 그 부모 노드에 적용시킨다. 잠시 후에 이걸 보여주겠다.
또 잘 생각해보면 흑색높이도 여전히 같아서 c)를 깨뜨릴 일은 없다. 예를 들어 위 네가지 경우 중에 첫번째 경우를 보자. z부터 잎까지 가는 모든 경로의 흑색높이는 같아야 한다. 따라서 1, 2, 3, 4의 흑색높이는 모두 같다.
예시를 하나 보자. 왼쪽의 트리에 2를 붉은색 노드로 삽입하고, red-red violation이 일어났으니 회전한다.
이건 위의 네가지 경우 중에서 세번째에 해당한다. 하지만 회전했더니 다시 red-red violation이 일어났다!
하지만 괜찮다. 만약 4가 루트 노드라면 그냥 4를 검정색으로 칠할 수 있다. 불변조건을 깨뜨리지 않기 때문이다. 루트 노드가 아니였다면 다시 저 회전을 재귀적으로 적용시키면 된다.
4. 레드-블랙 트리의 구현
우선 인터페이스를 쓰자.
signature ORD =
sig
type t
(* order는 SML내장 타입으로, LESS | EQUAL | GREATER로 정의된다. *)
val compare : t * t -> order
end
(* 딕셔너리 인터페이스 *)
signature POLY_DICT =
sig
structure Key : ORD
(* Key.t타입 키와 'a타입 값이 있는 딕셔너리이다. *)
type 'a t
val empty : 'a t
val insert : Key.t * 'a -> 'a t -> 'a t
val lookup : Key.t -> 'a t -> 'a option
end
삽입과 접근을할 수 있는 간단한 딕셔너리이다. 우리는 이 딕셔너리 인터페이스를 레드-블랙 트리로 구현할 것이다.
삭제는 왜 없냐고? 삭제는 조금 있다가 추가할거다.
키는 ORD 인터페이스를 만족하기만 하면 된다. 이러면 int던 string이던 상관없이 제네릭한 키 타입을 지원할 수 있다.
저번시간에 배웠던 함자(함자 아님)를 사용하자.
struct
structure Key = Key
datatype 'a rbtree =
Empty
| Red of 'a rbtree * (Key.t * 'a) * 'a rbtree
| Black of 'a rbtree * (Key.t * 'a) * rbtree
val empty = ...
val insert = ...
val lookup = ...
end
일단 insert의 핵심 보조함수인 restore를 구현하자. restore는 red-red violation이 일어났을때 트리를 회전시켜 불변속성을 복원(restore)하는 함수이다.
Red(Black(t1, x, t2), y, Black(t3, z, t4))
아래의 왼쪽 트리와 오른쪽 트리를 패턴 매칭을 이용해 나타내자.
이런 방식을 세번 더 하자.
다만 아직 끝나지 않았다. 패턴매칭이 모든 경우의 수를 다 따지지 않아서 Match 예외가 발생할것이기 때문이다.
우리가 적은 경우를 제외하면 트리는 red-red violation이 없는 상태란 뜻이므로 복원할 필요가 없으니까 그냥 그대로 둔다.
이제 insert를 구현해보자.
우리는 재귀적으로 restore를 호출하는 ins라는 보조함수를 만들고, 필요하다면 루트를 검정색으로 칠하는 부분은 insert에서 담당할 것이다.
이제 ins를 구현해보겠다. 빈 트리일 경우, 트리의 맨 위가 검정색 노드일 경우, 붉은색 노드일 경우 총 세가지 경우가 있다.
우리는 빈 트리에 붉은색 노드를 삽입하고 red-red violation이 일어나면 복원시키는 방식을 택했으니 코드는 다음과 같다.
이제 재귀적으로 주어진 키-값 쌍을 삽입한다. 키-값 쌍을 삽입한 다음에는 red-red violation이 일어났을지도 모르니 불변속성을 복원한다.
붉은색 노드에 할때는 restore를 할 필요가 없다. 전에 말했듯 red-red violation이 일어나는 네가지 경우 모두 맨 위노드는 검정색이기 때문이다.
자 이제는 lookup을 구현해보자. 이건 쉽다.
lookup : Key.t -> 'a t -> 'a option이니까 다음과 같이 재귀적으로 트리를 탐색해 나가면 된다.
5. delete 구현하기
여긴 사실 넘겨도 좋다. 수업에서 다루지 않는 내용이기 때문이다. 그냥 내가 궁금해서 찾아봤다.
https://www.cs.cornell.edu/courses/cs312/2004fa/lectures/lecture11.htm#deletion
여기에 의하면 아이디어는 다음과 같다.
(1) 삭제할 노드 Z를 찾는다.
(2) 트리에서 다른 알맞은 노드를 삭제하고 그 삭제된 노드의 정보를 Z로 옮긴다.
(3) 불변속성이 깨졌다면 적절히 트리를 변환시켜 복원한다.
일단 붉은색 노드를 삭제한다면 불변속성은 깨지지 않는다 (직접 생각해보자). 검정색 노드를 삭제할때만 주의해야 한다.
여기서부터는 삭제하고자 하는 노드를 Z, Z의 부모노드를 pZ, 임의의 서브트리를 소문자로, 빈 트리는 []로 표시하도록 하겠다. 미안… 직접 그림을 만들기는 귀찮았어…
그렇다면 다음과 같은 네가지 경우가 있다. 물론 Z가 pZ의 왼쪽 자식일 경우에 또 네가지 경우가 있지만 일단 넘어가자.
처음 세가지 경우에는 Z를 삭제하는게 간편하다. 그냥 이어붙이면 그만이기 때문이다. 하지만 A4의 경우를 생각하자. Z를 지우면 b와 c는 어디로 가야 하는가?
따라서 Z를 지우지 않고 다른 삭제하기 쉬운 노드 Y를 지운뒤, 그 노드의 값을 Z와 적절히 바꾼다.
Y는 Z보다 큰 노드 중 가장 작은 노드를 고른다. Z의 “다음” 노드 라고도 볼 수 있겠다.
다음 그림에서 Z를 지운다고 하면 Z의 다음 노드인 60을 Y로 두고 Y를 대신 지운다. Y는 Z처럼 자식 두명이 있을 수 없다. 만약 그랬다면 Y보다 작으면서 Z보다 큰 노드가 있을 것이기 때문이다.
이제 색깔을 생각하자. 방금 “삭제한” 노드 Y가 검정색이였다면? 흑색높이 불변속성을 지키기 위해 Y의 자식 노드인 X를 검정색으로 칠해야 한다. 하지만 만약 X가 원래 검정색이였다면?
사실 검정색인 노드에 다시 검정색을 칠할 수 있다고 생각하는게 도움이 된다. 이걸 껌정색 노드(doubly-black)라고 하겠다. 이중흑색 노드로 번역한 곳도 있지만 난 껌정색이 글자수도 더 적고 맘에 든다.
우리가 해야 할 것은 껌정색 노드가 나타나면 트리를 적절히 변형시켜 검정색 노드로 만드는 것이다.
A1을 다시 보자. Z가 검정색이여도 흑색높이는 전부 같다. 따라서 우리는 A2와 A3만 신경쓰면 된다.
A2에서 Z가 검정색이라면 c의 루트노드를 본다 (X라 하자). X가 붉은색이라면 X를 검정색으로 칠한다. X도 검정색이라면 검정색을 한번 더 칠해서 껌정색으로 만들고, 트리를 적절히 변형시켜 다시 검정색으로 만든다.
A3도 비슷하게 Z가 검정색이라면 b의 루트노드를 X라 하고, X에 검정색을 칠한다.
이제 껌정색 노드를 어떻게 검정색으로 만드나 보자. 보통 레드-블랙 트리에서 삭제를 구현할때 경우의 수가 굉장히 많은데, 적절히 나누면 다음처럼 네가지 경우의 수로 축약할 수 있다.
[B]는 검은색 노드, [R]는 붉은색 노드, [i]와 [i’]는 아무 노드, [x]는 껌정색 노드, [W]는 변형 전 노드가 붉은색이였다면 검정색, 검정색이였다면 껌정색이 된다.
C1은 껌정색 노드의 형제 노드가 붉은색일때, 형제 노드를 검정색으로 만드는 과정이다.
C2, C3, C4는 껌정색 노드의 형제 노드가 검정색일때를 다룬다.
C2는 껌정색노드를 한단계 위로 올려서, 트리 변형이 언젠가는 끝난다는걸 보장한다.
C3은 C4로 가는 중간과정이고.
C4는 바로 트리 변형이 끝날때이다. 잘 보면 루트 노드에서 잎으로 가는 모든 경로의 흑색높이는 변형을 거친 후에도 같다.
자 이제 이걸 구현해보자. SML이 아무도 안쓰는 언어라 그런지 이미 껌정색을 사용해 구현된게 안보이길래 내가 직접 구현해보기로 했다.
.
.
.
한 여섯시간정도 씨름했는데 위에 써놓은 로직이 어딘가 틀렸다는걸 깨달아서 빡종했다. 어딘가 설계단계부터 잘못된것 같아서, 차라리 이미 쓰여져 있는 코드를 SML로 포팅하는게 더 나을것 같다.
https://www.classes.cs.uchicago.edu/archive/2021/winter/22300-1/lectures/RedBlackDelete/index.html
찾아보니 시카고대학에서 elm언어로 쓴게 있었다. 물론 난 elm을 모른다.
저 사이트도 원래는 Racket으로 쓰여진걸 elm으로 포팅한건데, 난 Racket도 모른다. 다행히 elm 문법을 읽어보니 SML이랑 비슷한 부분이 많은것 같아서 큰 무리 없이 코드를 옮겨적을 수는 있었다. Racket을 포팅하려면 처음부터 공사를 해야하는 수준인듯 보였다.
아 또 여기 맨 밑에 보면 하스켈로 구현한 파일이 있는데 볼사람은 봐라.
근데 시카고대학 이놈들 함수를 잘못썼다. 간단한 트리에서도 삭제하려니까 오류가 뜬다. 그래서 Racket을 저 파일을 읽을 수 있을 수준까지 대충 머리에 때려박고 Racket 버전과 교차비교하면서 디버깅을 했다.
참고로 SML은 디버거가 없다. 오늘까지 합해서 delete 고치는데만 한 9시간 걸린듯. 
진짜 무식하게, 저렇게 트리가 뜨면
손으로 무식하게 해독하면서 삭제되야 할게 삭제되었는지, 회전은 잘 되었는지를 확인하면서 디버깅했다. 너희는 이런거 하지마라...
어쨌든 버그 한 4개는 있었는데 다 고치긴 고쳤다. 랜덤으로 사이즈 10,000 인 딕셔너리 만들어서 랜덤으로 다 지웠는데 빈 딕셔너리가 나오는걸 확인하고를 몇십번을 했는데 에러가 안떴다. 이정도면 됐겠지.
최종 코드는 여기 있다.
https://gist.github.com/Daqsa/e72d738481ac9e59a589a22fc0ea4ac5
저 시카고대학 버전 delete는 껌정색 외에도 뿕은색 (doubly red) 을 써서 총 4가지 색이 있다. 껌정색과 뿕은색은 delete 중간단계에서만 잠시 쓰이고 트리 변형 단계에서 잘 조정되어 없어지며, 트리 변형을 더 논리적으로 간편하게 만들어준다.
원래는 시카고대학 버전 delete를 설명하려 했는데 지쳐서 여기까지만 하려고 한다. 애초에 함수형 프로그래밍에서 너무 멀리 왔다.
대충 delete 구현한 후기를 쓰자면, 훨씬 어렵다. 학교에서 insert만 가르치는 이유가 있었다. 최종 코드를 보면 알겠지만 양만 봐도 delete없을때와 비교했을때 세배 가까이 늘었다.
궁금하거나 이해 잘 안되는거 있으면 댓글로 물어보면 내가 아는선에서 최대한 답변해줄테니 많이 물어봐라.
다음에는 시퀀스를 알아보도록 하자.
+) 이 방식으로 구현한 insert와 delete는 영구적(persistent)이다. 트리에 삽입/삭제 함수를 호출할때 기존의 트리를 수정하지 않는다는 뜻이다. 부분적인 복사본을 만들던가 하는식으로 영구적 자료구조를 만들 수 있다. 이렇게 만든 영구적 자료구조는 옛날이던지 최근이던지에 상관없이 모든 버전을 접근 또는 수정 할 수 있기에 계산기하학, 텍스트/파일 수정 프로그램, 또는 아주 고수준 프로그래밍 언어를 구현할때 아주 유용하다고 한다.
++) 찾아보니까 저 시카고 대학 버전 말고도 다른 구현방법들이 있는데 시카고 대학 버전이 제일 이해하기 쉽다고 한다. 더 빠르게 모나드?를 이용해 구현한 방법도 있다. 이 논문은 친절하게도 각 delete 구현방법의 성능을 비교했는데 시카고 대학 버전은 Germane-Might를 보면 되고 중간정도 빠르기이다.
