Red black tree 기초개념 및 구현실습
.
그림, 실습코드 등 학습자료 출처 :
1) https://github.com/ythwork
2) https://m.blog.naver.com/noblea1117/220454721219
레드 블랙트리의 필요성
- 이진 탐색 트리 중에 데이터가 아래 그림과 같이 편향되게 들어오는 경우가 있는데 이럴경우 이진 탐색 트리의 검색 효율을 나쁘게 하므로, 균형을 바로 잡기 위해 레드 블랙 트리라는 알고리즘을 사용한다.
그래서 아래 그림과 같은 필요성이 제기되었고, 그래서 나온 개념이 균형이진트리의 일종이다. 이 균형이진트리의 일종이 레드블랙트리인 것이다.
레드블랙트리의 이해를 위한 ‘확장 이진트리’
-
또한 레드블랙트리는 ‘확장 이진트리’라는 트리개념도 포함하고 있다.
-
아래 그림과 같이 모든 공백 이진 서브트리를 외부노드로 대체한 트리를 말한다.
-
자식이 없는 리프노드(위에서는 4,5,3) 에 노드를 붙여주는데 이 놈들을 외부노드라고 한다.
레드블랙트리의 정의
-
모든 노드의 컬러가 레드 혹은 블랙인 균형이진트리
-
insert, search, delete 모두 최악의 경우 : O(log2n)
레드블랙트리가 균형을 유지하기 위해서 갖는 특징
아래 그림이 전형적인 레드블랙트리의 예시이다.
-
기본적으로 레드 블랙 트리는 이진 탐색 트리를 베이스로 하기 때문에 BST의 특성을 모두 갖는다.
-
추가적으로, 레드블랙트리가 균형을 유지하기 위해 여러 특성을 갖는다.
1) 트리의 모든 노드는 검정색 아니면 빨간색이다.
2) 루트 노드는 무조건 검정색이다.
-> 13번 노드를 보면 알 수 있다.
3) 모든 외부노드는 검정색이다.
여기서 헷갈리면 안되는게 레드블랙 트리에서 리프노드는 외부노드를 말한다
4) 빨간색의 노드 자식들은 모두 검정색이지만, 검정색 노드 자식들은 어느 색깔이든 상관없다.
5) 루트 노드에서 모든 리프노드 사이에 있는 검정색 노드의 수는 모두 동일하다.
다시말해 루트에서 외부노드의 모든 경로에서 블랙노드의 수는 같다는 것이다.
-> 위의 그림에서는 각각 한개씩 있다.
6) 루트에서 외부노드로의 경로중에 레드노드가 연속으로 나올 수 없다.
7) N개의 노드가 있는 레드블랙트리 높이 : 2log2(n+1)
레드블랙트리의 연산
1) 회전
레드 블랙 트리에 새로운 값이 삽입되거나 삭제가 되었을 때 레드 블랙 트리의 특징이 깨지게 되는 경우가 있는데 이때 레드블랙트리의 특징을 유지하기 위해 아래 그림과 같이 ‘회전’ 연산을 수행한다. 우회전, 좌회전 총 두 가지 회전 연산이 있다.
[파이썬 코드 구현시 로테이션 알고리즘]
- 먼저 파이썬 코드 구현을 위한 용어정의
1) key : 트리내에서 유일한 키
2) color : 레드 아니면 블랙
3) left_child : 왼쪽 서브트리
4) right_child : 오른쪽 서브트리
5) parent : 부모노드
[좌회전]
left_notation이라는 함수 구현
STEP1) l을 n.right_child 로 변경
STEP2) n.parent를 r.parent로 변경
STEP3) n을 r.left_child로 변경
[우회전]
right_notation이라는 함수 구현
STEP1) r을 n.left_child로 변경
STEP2) n.parent를 l.parent로 변경
STEP3) n을 l.right_child로 변경
2) 삽입
레드블랙트리는 기본적으로 이진 탐색 트리의 특징을 그대로 갖고 있기 때문에 삽입하는 과정도 이진 탐색 트리와 동일하다. 하지만 새로운 노드를 삽입했을때 트리의 불균형이 깨지는 경우가 자주 있어서 각각의 경우에 따라 불균형한 트리를 fixing해줘야 한다.
삽입 시 알고리즘 수행
STEP1) BST에 노드를 삽입
STEP2) 새로운 노드의 색을 RED로 지정
STEP3) insert_fix를 호출해 노드를 균형있게 재배열
- insert_fix 함수의 필요성
1) 루트노드가 RED일 경우 루트노드를 블랙으로 바꿔줘야 한다.
2) 삽입된 노드와 그 부모노드가 모두 RED라면 RED노드가 연속되어 나올 수 없다는 규칙을 위반하는 것임
아래 그림이 위에서 언급한 불균형한 케이스의 예시이다.
이런 경우에 불균형한 구조를 바로 잡아주는 것이 insert_fix 함수이다.
새로 노드를 삽입하고 나서 트리구조가 연속된 레드노드가 존재할 때 insert_fix 함수의 실행
-
삽입된 노드의 부모노드가 조부모노드의 왼쪽 자식일때 : LLr, LRr, LLb, LRb
-
삽입된 노드의 부모노드가 조부모노드의 오른쪽 자식일때 : RLr, RRr, RLb, RRb
CASE1) 부모의 형제노드가 레드일때
CASE2) 부모의 형제노드가 블랙일때
insert 예시
최초의 트리에서 점점 노드를 추가하는 과정
3) 삭제
레드블랙트리의 노드를 삭제할 때 빨간색, 검정색 중 하나의 노드를 삭제하게 될 것이다. 빨간색 노드를 삭제하게 되는 경우 레드블랙트리의 불균형성을 해치는 경우가 없으므로 고려해야 할 케이스가 아니다. 하지만, 검정색 노드를 삭제하게 되는 경우 트리의 불균형성이 깨지므로 이것도 역시 case에 맞게 잘 fixing해줘야 한다.
- 삭제하는 CASE 별 알고리즘
1) 삭제된 노드를 대체하는 노드가 레드일 경우
우리가 여기서 23번 노드를 삭제한다고 한다면 아래의 그림처럼 ‘빨간색의 노드 자식들은 모두 검정색이지만, 검정색 노드 자식들은 어느 색깔이든 상관없다’는 규칙과 ‘루트 노드에서 모든 리프노드 사이에 있는 검정색 노드의 수는 모두 동일하다.’는 규칙이 깨지게 된다.
그래서 레드블랙트리의 규칙을 유지하기 위해서 21번 노드를 검정색으로 칠해준다. 그러면 아래와 같이 구조가 잡히고 레드블랙트리의 규칙을 모두 지키게 된다.
1번 케이스의 경우 결론 : 삭제된 노드를 대체하는 노드가 레드일 경우, 색상을 블랙으로 변경해준다.
2) 삭제된 노드를 대체하는 노드가 블랙인 경우
이번에도 23번 노드를 삭제한다고 치자. 그러면 결과는 아래 그림과 같다.
이 경우, 삭제한 노드를 대체하는 노드(21번노드)에 블랙을 덧입힌다.
그리고 블랙을 덧입힌 노드를 이중흑색 노드 라고 부른다.
이중흑색 노드를 갖고 있을 경우 첫번째 규칙(모든 노드는 레드 아니면 블랙이다)이 무너진 것으로 간주한다.
(이중흑색노드는 엄격하게 말하면 레드도 아니고 블랙도 아니기 때문에)
그래서 이런 이중흑색노드도 잘 처리해줘야 한다.
이중흑색노드의 처리
CASE1) 형제가 레드인 경우
이때 형제를 블랙, 부모를 레드로 칠한다.
그 후 부모를 기준으로 좌회전해준다.
좌회전을 하면 위와 같은 그림의 형태가 되는데 이런 형태가 되면 21번이 이중흑색이지만 블랙으로 간주해준다.
그러면 이제 문제의 유형이 ‘형제가 블랙인 경우’로 바뀌었다.
2번 항목을 참고하여 이중흑색노드를 제거하면 된다.
CASE2) 형제가 블랙인 경우
이 경우 다시 세가지 케이스로 분류된다.
1) 형제의 오른쪽 자식이 레드인 경우
STEP1) 이중흑색 노드의 부모 노드가 갖고 있는 색을 형제 노드에 칠한다.
이미 부모노드와 형제노드의 색이 같이 때문에 일단 넘어간다.
STEP2) 부모노드와 형제노드의 오른쪽 자식노드를 블랙으로 칠한다.
STEP3) 부모노드를 기준으로 좌회전한다.
STEP4) 이중흑색 노드가 갖고 있던 블랙중 하나를 루트노드에 넘긴다.
최종적으로 루트노드가 이중흑색일 경우는 별도의 조치를 안해줘도 된다.
(루트 노드는 이중흑색도 허용한다는 것으로 레드블랙트리의 특징을 위반하지 않는다.)
2) 형제의 왼쪽 자식은 레드, 오른쪽 자식은 블랙인 경우
STEP1) 형제노드를 레드로 칠하고, 왼쪽 자식을 블랙으로 칠한다.
STEP2) 형제노드를 기준으로 우회전 수행
문제의 유형이 형제의 오른쪽 자식이 레드인 경우로 변경되었고, 그것에 맞춰서 다시 한번 처리해준다.
3) 형제 양쪽 자식이 모두 블랙인 경우
STEP1) 형제노드를 레드로 칠한다.
STEP2) 이중흑색노드가 갖고 있던 두개의 블랙 중 하나를 부모노드로 넘긴다.
부모가 이중흑색 노드가 되었을 경우
위의 예시에서는 이중흑색 노드의 형제가 블랙이고, 형제의 자식이 모두 블랙인 경우이므로 (자식이 하나 밖에 없는데 그 하나가 블랙) 위의 과정을 한 번 더 수행한다.
과정을 반복하여 루트가 이중흑색 노드가 되었을 경우 종료한다.
결국에는 바로 위에서 언급한 내용의 반복이지만 파이썬 코드구현 시는 다음과 같이 구현한다.
삭제된 노드가 블랙이라면 delete_fix를 호출해 노드를 균형있게 재배열 할 것이다.
- delete_fix 함수
[delete_fix 함수가 필요한 경우]
1) 삭제된 노드가 루트 또는 새로운 루트가 레드일때
루트노드를 블랙으로 바꿔줘야한다.
삭제된 노드가 블랙이므로 루트에서 외부노드까지 모든 경로의 블랙 노드의 수는 같다는 규칙이 깨지기 때문이다.
2) 삭제된 노드가 블랙일경우 루트에서 외부노드까지 모든 경로의 블랙노드의 같다는 규칙에 위반된다.
이 경우에도 두가지 케이스로 나뉘어진다.
CASE1) 삭제된 노드의 자식노드가 레드일때 -> 블랙으로 바꿔준다.
CASE2) 삭제된 노드의 자식 노드가 블랙일때
자식 노드에 extra 블랙(=이중흑색)을 주고, 위에 언급했던것처럼 이중흑색일 경우로 처리해준다.
파이썬 코드구현 시 delete case 정의
CASE1) 삭제된 노드의 자식노드 c가 왼쪽 자식노드일때
1) 노드 c의 형제노드 s가 레드일때
그래서 s가 블랙인 케이스를 처리해주면 된다.
2) 노드 c의 형제노드 s가 블랙일때
노드 s의 두자식이 블랙
노드 s의 왼쪽자식이 레드
노드 s의 오른쪽 자식이 레드
CASE2) 삭제된 노드의 자식노드 c가 오른쪽 자식노드일때
위의 삭제알고리즘 들을 고려한 Delete 예시
똑같은 2번 노드를 삭제하는데 크게 두가지 방법이 가능하다. (아래 그림참고)
레드블랙트리 파이썬 코드구현
class RBNode:
def __init__(self, key):
#트리 내에서 유일한 키
self.key=key
#노드의 색 : RED or BLACK
#트리에 insert 연산을 할 때 먼저 새 노드의 색은 RED로 한다.
self.color="RED"
self.left_child=None
self.right_child=None
#부모
self.parent=None
class RedBlackTree:
def __init__(self):
self.root=None
def get_root(self):
return self.root
def preorder_traverse(self, cur, func, *args, **kwargs):
if not cur:
return
func(cur, *args, **kwargs)
self.preorder_traverse(cur.left_child, func, *args, **kwargs)
self.preorder_traverse(cur.right_child, func, *args, **kwargs)
def __left_rotate(self, n):
#n's right child
rc=n.right_child
#rc's left child
rcl=rc.left_child
#rcl을 n의 오른쪽 자식으로
#rcl이 None일 수 있으므로
if rcl:
rcl.parent=n
n.right_child=rcl
#n.parent를 rc.parent로
#n이 루트라면, 트리 루트도 업데이트
if n.parent==None:
self.root=rc
elif n.parent.left_child==n:
n.parent.left_child=rc
else:
n.parent.right_child=rc
rc.parent=n.parent
#n을 rc의 왼쪽 자식으로
rc.left_child=n
n.parent=rc
def __right_rotate(self, n):
#n's left child
lc=n.left_child
#lc's right child
lcr=lc.right_child
#lcr을 n의 왼쪽 자식으로
#lcr이 None일 수 있으므로
if lcr:
lcr.parent=n
n.left_child=lcr
#n.parent를 lc.parent로
#n이 루트라면 트리의 루트도 업데이트
if n.parent==None:
self.root=lc
elif n.parent.left_child==n:
n.parent.left_child=lc
else:
n.parent.right_child=lc
lc.parent=n.parent
#n을 lc의 오른쪽 자식으로
lc.right_child=n
n.parent=lc
def __insert_fix(self, n):
#pn: n's parent
#gn: n's grand parent
#un: pn's sibling
pn=gn=un=None
#en: external node
en=RBNode(None)
en.color="BLACK"
pn=n.parent
#n이 루트가 아니고
#n.parent가 RED --> 연속된 RED
while pn != None and pn.color=="RED":
#pn이 RED이면 반드시 gn이 존재: 루트는 BLACK이므로 pn은 루트가 될 수 없다
gn=pn.parent
#1. pn이 gn의 왼쪽 자식일 때
if gn.left_child == pn:
#조부모의 오른쪽 자식이 외부 노드일 때
#부모 형제를 미리 만들어 둔 en으로 대체
if gn.right_child==None:
un=en
else:
un=gn.right_child
#XYr : 부모 형제가 RED일 때
if un.color=="RED":
#부모, 부모 형제와 조부모의 색을 변경
gn.color="RED"
pn.color=un.color="BLACK"
#gn을 새로운 n으로 만든 후 연속된 레드가 또 일어나는지 확인
n = gn
pn = n.parent
#XYb : 부모 형제가 BLACK일 때
else:
#LRb일 때
if pn.right_child==n:
#LEFT-ROTATE(pn)
self.__left_rotate(pn)
n, pn = pn, n
#LLb일 때
#부모와 조부모의 색을 바꾸고
pn.color, gn.color=gn.color, pn.color
#RIGHT-ROATE(gn)
self.__right_rotate(gn)
#2. pn이 gn의 오른쪽 자식일 때
else:
#조부모의 왼쪽 자식이 외부 노드일 때
#부모 형제를 en으로 대체
if gn.left_child==None:
un=en
else:
un=gn.left_child
if un.color=="RED":
gn.color="RED"
pn.color=un.color="BLACK"
n=gn
pn=n.parent
else:
if pn.left_child==n:
self.__right_rotate(pn)
n, pn = pn, n
pn.color, gn.color=gn.color, pn.color
self.__left_rotate(gn)
#연속된 레드가 루트까지 올라갔을 경우에는
#루트를 BLACK으로 만들어주면 된다
self.root.color="BLACK"
def insert(self, key):
new_node=RBNode(key)
cur=self.root
if not cur:
self.root=new_node
#루트 노드는 BLACK
new_node.color="BLACK"
return
while True:
parent=cur
if key < cur.key:
cur=cur.left_child
if not cur:
parent.left_child=new_node
#노드의 parent 설정
new_node.parent=parent
break
else:
cur=cur.right_child
if not cur:
parent.right_child=new_node
#노드의 parent 설정
new_node.parent=parent
break
#노드 삽입 후 처리
self.__insert_fix(new_node)
def search(self, target):
cur=self.root
while cur:
if cur.key==target:
return cur
elif cur.key > target:
cur=cur.left_child
elif cur.key < target:
cur=cur.right_child
return cur
def __remove_recursion(self, cur, target):
if not cur:
return None, None
elif target < cur.key:
cur.left_child, rem_node=self.__remove_recursion(cur.left_child, target)
#왼쪽 자식 노드의 부모 설정
if cur.left_child:
cur.left_child.parent=cur
elif target > cur.key:
cur.right_child, rem_node=self.__remove_recursion(cur.right_child, target)
#오른쪽 자식 노드의 부모 설정
if cur.right_child:
cur.right_child.parent=cur
else:
if not cur.left_child and not cur.right_child:
rem_node=cur
cur=None
elif not cur.right_child:
rem_node=cur
cur=cur.left_child
elif not cur.left_child:
rem_node=cur
cur=cur.right_child
else:
replace=cur.left_child
while replace.right_child:
replace=replace.right_child
cur.key, replace.key=replace.key, cur.key
cur.left_child, rem_node=self.__remove_recursion(cur.left_child, replace.key)
#왼쪽 자식 노드의 부모 설정
if cur.left_child:
cur.left_child.parent=cur
return cur, rem_node
def __remove_fix(self, c):
#노드 c가 루트가 아니고 : 루트면 extra BLACK 제거 후 종료
#노드 c가 BLACK이면 : RED이면 BLACK으로 만들고 종료
while c.parent!=None and c.color=="BLACK":
#노드 c가 왼쪽 자식 노드일 때
if c.parent.left_child==c:
#s: sibling
s=c.parent.right_child
#case 1: s.color = RED
#case 2로 만든다
if s.color=="RED":
#c.parent와 s의 컬러를 바꾼다
c.parent.color, s.color=s.color, c.parent.color
#LEFT-ROTATE(c.parent)
self.__left_rotate(c.parent)
#case 2: s.color = BLACK
else:
#case 2-1: s.left and s.right --> BLACK
if s.left_child.color=="BLACK" and s.right_child.color=="BLACK":
#tack black from c, s
s.color="RED"
#give black to p
c=c.parent
#case 2-2: s.left --> RED
elif s.right_child.color=="BLACK":
s.color, s.left_child.color=s.left_child.color, s.color
self.__right_rotate(s)
#case 2-3: s.right --> RED
else:
s.color=c.parent.color
c.parent.color=s.right_child.color="BLACK"
self.__left_rotate(c.parent)
#while문을 빠져나간다
c=self.root
#노드 c가 오른쪽 자식일 때
else:
s=c.parent.left_child
if s.color=="RED":
c.parent.color, s.color=s.color, c.parent.color
self.__right_rotate(c.parent)
else:
if s.left_child.color=="BLACK" and s.right_child.color=="BLACK":
s.color="RED"
c=c.parent
elif s.left_child.color=="BLACK":
s.color, s.right_child.color=s.right_child, s.color
self.__left_rotate(s)
else:
s.color=c.parent.color
c.parent.color=s.left_child.color="BLACK"
self.__right_rotate(c.parent)
c=self.root
c.color="BLACK"
def remove(self, target):
self.root, removed_node=self.__remove_recursion(self.root, target)
#삭제된 노드가 블랙 노드인 경우
#삭제된 노드의 자식 노드를
#remove_fix의 인자로 전달
if removed_node and removed_node.color=="BLACK":
if removed_node.left_child:
rem_child=removed_node.left_child
elif removed_node.right_child:
rem_child=removed_node.right_child
else:
#삭제된 노드가 리프 노드라면
#삭제된 노드의 자식 노드는 외부 노드
rem_child=RBNode(None)
rem_child.parent=removed_node.parent
rem_child.color="BLACK"
self.__remove_fix(rem_child)
if removed_node:
removed_node.left=removed_node.right=removed_node.parent=None
return removed_node
def print_node(self, rbn):
if rbn:
print("node : {}, ".format(rbn.key), end="")
if rbn.color=="RED":
print("color : RED, ", end="")
else:
print("color : BLACK, ", end="")
if rbn.left_child:
print("left : {}, ".format(rbn.left_child.key), end="")
if rbn.right_child:
print("right : {}, ".format(rbn.right_child.key), end="")
if rbn.parent:
print("parent : {}".format(rbn.parent.key), end="")
print()
def color_changer(cur, *keys):
print(keys)
if cur.key in keys:
cur.color="RED"
else:
cur.color="BLACK"
rbt=RedBlackTree()
#insert
rbt.insert(20)
rbt.insert(10)
rbt.insert(22)
#LLr
rbt.insert(7)
rbt.preorder_traverse(rbt.get_root(), rbt.print_node)
node : 20, color : BLACK, left : 10, right : 22,
node : 10, color : BLACK, left : 7, parent : 20
node : 7, color : RED, parent : 10
node : 22, color : BLACK, parent : 20
rbt.insert(15)
#LRr
rbt.insert(8)
rbt.preorder_traverse(rbt.get_root(), rbt.print_node)
node : 20, color : BLACK, left : 10, right : 22,
node : 10, color : RED, left : 7, right : 15, parent : 20
node : 7, color : BLACK, right : 8, parent : 10
node : 8, color : RED, parent : 7
node : 15, color : BLACK, parent : 10
node : 22, color : BLACK, parent : 20
rbt.insert(13)
#LRb
rbt.insert(14)
rbt.preorder_traverse(rbt.get_root(), rbt.print_node)
node : 20, color : BLACK, left : 10, right : 22,
node : 10, color : RED, left : 7, right : 14, parent : 20
node : 7, color : BLACK, right : 8, parent : 10
node : 8, color : RED, parent : 7
node : 14, color : BLACK, left : 13, right : 15, parent : 10
node : 13, color : RED, parent : 14
node : 15, color : RED, parent : 14
node : 22, color : BLACK, parent : 20