2021. 2. 10. 22:07ㆍ알고리즘
1. 특징
앞에서의 이진 검색 트리는 평균은 Θ(logn)이지만 균형이 깨진다면 Θ(n)의 시간이 소요된다. 이를 극복하기 위해 레드 블랙트리를 사용한다. 레드 블랙 트리는 이진 검색트리의 노드에 레드 또는 블랙의 색을 칠하는데 그 조건은 아래와 같다.
1) 루트는 블랙이다.
2) 모든 리프(NIL)는 블랙이다
3) 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
4) 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
위의 예시는 아래와 같다.
맨 마지막 리프는 모두 NIL 노드로 다루는데 보통은 모든 리프에 각각 다른 NIL 노드를 달기 버거우니 그냥 하나의 NIL노드를 만들고 모든 리프를 이 노드에 연결시키는 방법을 사용한다.
2. 삽입
레드 블랙 트리에서 삽입은 항상 리프 노드의 NIL을 버리고 그 자리에 새로운 노드를 끼워 넣는데 이때 노드의 색은 레드로 통일한다. 그다음 조건을 맞추기 위해 트리를 조작하는 것이다. 이 새로운 노드를 x라고 하자. 그러면 아래와 같은 경우들이 생긴다.
1) x의 부모 노드 p가 블랙일때
이 경우에는 새로 단 노드가 레드이기 때문에 4번 조건에서 카운트가 되지 않아서 항상 조건을 만족하게 된다.
2) x의 부모 노드 p가 레드일때
우선 p가 레드이면 p의 부모인 pp는 반드시 블랙이어야 한다. 또한 p가 레드이기 때문에 3번조건에 의해 x의 형제 노드도 블랙이어야 한다. 또한 이때부터는 p의 형제 즉 x의 삼촌 노드인 s의 색을 따져야한다. s 노드는 레드, 블랙 모두 가능하다.
case 1: s가 레드일때
이때는 p와 s의 색상을 레드에서 블랙으로 바꾸고 pp의 색상을 블랙에서 레드로 바꾼다. 그리고 pp가 루트노드라면 다시 블랙으로 바꾼다음 종료한다.
하지만 여기서 pp의 부모를 따져야하는데 pp의 부모가 블랙이라면 조건을 만족하지만 레드라면 3번 조건에의해 pp가 블랙이 되어야 한다. 따라서 pp를 기준으로 잡고 재귀적으로 색을 바꾸어야 한다.
case2: s가 블랙일때
case 2-1) x가 p의 오른쪽 자식
이때는 p를 중심으로 왼쪽으로 회전한다.
하지만 여전히 조건 3번을 위반한다. 하지만 이것은 case 2-2를 만든 것이다.
case 2-2)x가 p의 왼쪽 자식
이때는 pp를 중심으로 오른쪽으로 회전하고 p와 pp의 색을 바꾼다.
위의 상황들을 재귀적으로 반복하여서 트리의 조건을 만족시키면 된다.
직접 구현한 코드는 아래와 같다.
def rotate_left(self, p):
x = p.right
#x의 왼쪽 서브트리를 p에 달아줌
p.right = x.left
if x.left != self.NIL:
x.left.parent = p
#옮겨진 x의 parent를 다시 복구
if x != self.NIL:
x.parent = p.parent
if p.parent is not None:
if p.parent.left == p:
p.parent.left = x
else:
p.parent.right = x
else:
self.root = x
#x와 p를 연결
x.left = p
if p != self.NIL:
p.parent = x
#p는 회전 축
def rotate_right(self, p):
x = p.left
#축이 오른쪽으로 이동
p.left = x.right
if x.right != self.NIL:
x.right.parent = p
#x의 부모 관계 형성
if x != self.NIL:
x.parent = p.parent
if p.parent is not None:
if p.parent.left == p:
p.parent.left = x
else:
p.parent.right = x
#p가 root였음
else:
self.root = x
#p와 x 관계형성
x.right = p
if x != self.NIL:
p.parent = x
def fix_insert(self, x):
#x의 부모가 black이면 그냥 삽입 끝 -> red일때가 문제
while x != self.root and x.parent.color == 'RED':
# p :부모 노드, pp : 조부모 노드, s : 삼촌 노드
pp = x.parent.parent
p = x.parent
if pp.left == p:
s = pp.right
else:
s = pp.left
#case 1
if s.color == 'RED':
p.color = 'BLACK'
pp.color = 'RED'
s.color = 'BLACK'
x = pp
#case2 -> 삼촌이 black
else:
#pp의 왼쪽 자식이 p
if pp.left == p:
#case 2-1
if p.right == x:
x = x.parent
self.rotate_left(x)
#case 2-2
#옮겨진 p와 pp의 색을 바꾼다.
x.parent.color = 'BLACK'
x.parent.parent.color = 'RED'
self.rotate_right(x.parent.parent)
#pp의 오른쪽 자식이 p
else:
#case 2-1
if p.left == x:
x = p
self.rotate_right(x)
x.parent.color = 'BLACK'
x.parent.parent.color = 'RED'
self.rotate_left(x.parent.parent)
self.root.color = 'BLACK'
def insert(self, key, value):
x = Node(key, value)
x.right = self.NIL
x.left = self.NIL
#들어갈 위치 찾기
cur = self.root
p = None
if self.root is None:
self.root = x
self.root.color = 'BLACK'
return x
else:
while cur != self.NIL:
if cur.key == key:
return False
else:
p = cur
if cur.key > key:
cur = cur.left
else:
cur = cur.right
x.parent = p
if p.key>x.key:
p.left = x
else:
p.right = x
#pp까지 있는지 확인
if x.parent.parent is None:
return x
else:
self.fix_insert(x)
return x우선 insert 함수로 자리만 잡는다. 그다음 fix 함수로 case를 따져가면서 트리를 변형시키는 것이다. 각각의 rotate함수에 들어가는 변수는 모두 회전축을 기준으로 잡았다.
3. 삭제
삭제 역시 기본적으로 이진 검색 트리의 삭제 방법을 따른 후에 색상을 맞추어 준다. 삭제할 노드 r의 바로 다음 크기의 원소(m)를 r자리에 두고 m자리를 삭제하는 것이다. 이때 어차피 m자리의 왼쪽 서브트리는 없음으로 우리가 생각할 경우는 자식이 없거나 자식이 하나인 경우만 따지면 된다.
노드 m의 자식을 x라고 하자. 원래는 m이 부모의 왼쪽 자식이냐 오른쪽 자식이냐도 따져야 하지만 어차피 대칭적임으로 왼쪽 자식이라고 둔다.
m이 레드라면 삭제되어도 4번의 특성을 깨지 않는다. 사라져도 리프노드까지의 블랙의 갯수는 같기 때문이다.
m과 x가 둘다 블랙이면 m이 사라지게 되면 리프노드까지의 블랙의 갯수가 하나 줄기 때문에 왼쪽, 오른쪽 회전과 색상 교체등으로 갯수를 맞추어야 한다.
우선 나올 수 있는 모든 경우의 수를 확인해보자. <s, l, r>로 표현을 할 것이다. 여기서 s는 삼촌, l,r은 s의 자식노드이다.
1) p가 레드일때
1-1 <블랙, 블랙, 블랙>
1-2 <블랙, 블랙, 레드> , <블랙, 레드, 레드> -> 처리방법이 같아서 하나로 묶는다. -> <블랙, *, 레드>
1-3 <블랙, 레드, 블랙>
2) p가 블랙일때
2-1 <블랙, 블랙, 블랙>
2-2 <블랙, 레드, 레드>, <블랙, 블랙, 레드> -> <블랙, *, 레드>
2-3 <블랙, 레드, 블랙>
2-4 <레드, 블랙, 블랙>
아래는 위의 모든 케이스에 대한 그림이다.
그리고 여기서 case 1-2, 2-2와 case 1-3, 2-3은 p의 색상 차이이다. 이 색상은 처리에 영향을 미치지 않음으로 아래처럼 하나로 통일한다.
각각의 삭제방법은 아래와 같다.
1) case 1-1
그냥 p와 s의 색을 바꾸어 준다. 이러면 x에서 모잘랐던 블랙하나가 p에서 충족이 된다.
2) case *-2
왼쪽으로 회전시킨 다음 p와 s의 색을 바꾼다.
3) case *-3
s를 중심으로 오른쪽으로 회전시킨다음 l과 s의 색을 바꾼다. 이는 case *-2가 된다.
4) case 2-1
s의 색을 레드로 바꾼다. 그러면 이제 p노드에서 리프노드까지의 블랙의 갯수가 하나가 줄게 된다. 그다음 p를 문제 노드로 삼고 다시 fix delete를 진행한다.
5) case 2-4
p를 중심으로 왼쪽으로 회전시키고 p와 s의 색을 바꾼다. 이때 x를 중심으로 보았을 때 p가 레드인 경우와 같다. 따라서 이 경우를 이용해 다시 fix delete한다.
아래는 직접 구현한 코드이다.
def fix_delete(self, x):
p = x.parent
while x != self.root and x.color == 'BLACK':
#x가 왼쪽 서브 트리일때
if p.left == x:
#삼촌과 삼촌 자식들을 구한다.
s = p.right
l = s.left
r = s.right
#case 1-1
if p.color == 'RED' and l.color == 'BLACK' and r.color == 'BLACK':
p.color = 'BLACK'
s.color = 'RED'
break
#case *-2
elif s.color == 'BLACK' and r.color == 'RED':
s.color = p.color
p.color = 'BLACK'
r.color = 'BLACK'
rotate_left(p)
break
#case *-3
elif s.color == 'BLACK' and l.color == 'RED' and r.color == 'BLACK':
l.color = 'BLACK'
s.color = 'RED'
rotate_right(s)
#case 2-1
elif s.color == 'BLACK' and l.color == 'BLACK' and r.color == 'BLACK':
s.color = 'RED'
x = p
#case 2-4
else:
p.color = 'RED'
s.color = 'BLACK'
rotate_left(p)
else:
#삼촌과 삼촌 자식들을 구한다.
s = p.right
l = s.left
r = s.right
#case 1-1
if p.color == 'RED' and l.color == 'BLACK' and r.color == 'BLACK':
p.color = 'BLACK'
s.color = 'RED'
break
#case *-2
elif s.color == 'BLACK' and l.color == 'RED':
s.color = p.color
p.color = 'BLACK'
rotate_right(p)
break
#case *-3
elif s.color == 'BLACK' and r.color == 'RED' and l.color == 'BLACK':
s.color = r.color
r.color = 'BLACK'
rotate_left(s)
#case 2-1
elif s.color == 'BLACK' and r.color == 'BLACK' and l.color == 'BLACK':
s.color = 'RED'
x = p
#case 2-4
else:
p.color = s.color
s.color = 'BLACK'
rotate_right(p)
x.color = 'BLACK'
def delete(self, key):
p = None
cur = self.root
cur_is_left = True
#삭제할 곳 찾기
while cur != self.NIL:
if cur.key == key:
break
else:
p = cur
if cur.key > key:
cur = cur.left
else:
cur = cur.right
if cur == self.NIL:
return False
#successor 찾기(m)
#만약 삭제할 노드의 오른쪽 또는 왼쪽이 NIL이면 그 다음 노드에 연결만 하면됨
if cur.left == self.NIL or cur.right == self.NIL:
m = cur
else:
#만약 삭제한 뒤에 채워 넣을 다음 노드를 찾는다
m = cur.right
while m.left != self.NIL:
m = m.left
#삭제할 노드의 다음 노드(m)의 다음 값을 찾는다
if m.left != self.NIL:
x = m.left
else:
x = m.right
#x와 m의 부모를 잇는다.
x.parent = m.parent
if m.parent is not None:
if m.parent.left == m:
m.parent.left = x
else:
m.parent.right = x
else:
self.root = x
#m과 cur이 같은 경우는 그냥 이으면 되는 것
if m != cur:
cur.key = m.key
cur.value = m.value
if m.color == 'RED':
return True
else:
self.fix_delete(x)
4. 시간 복잡도
키의 총수가 n개라고 하자. 즉 레드 블랙 트리의 노드의 수가 n개라는 것이다. 색상을 고려하지 않았을 때 꽉 채워진 트리의 깊이는 logn+1이다.(노드가 1개일때 깊이가 1임으로 1을 더해주었다.). 블랙노드의 갯수는 어느 경로에서나 같아야 함으로 블랙만 따졌을 때는 꽉채워진 노드의 갯수와 같다. 그러므로 블랙 노드의 갯수는 logn +1을 벗어날 수 없다. 게다가 레드 노드는 2개가 연속으로 존재할 수 없다. 그래서 루트에서 임의의 리프까지의 레드 노드의 갯수는 블랙 노드보다 많을 수 없다. 그러므로 아무리 많아도 logn개라고 생각할 수 있다. 즉 두개를 합치면 2logn + 1이 되고 이는 최대 가능한 깊이가 O(logn)이라는 것이다.
따라서 검색은 이 최대 가능한 깊이에 비례함으로 O(logn)이다.
삽입과 삭제 역시 검색후 상수배로 처리함으로 O(logn)이다. recursive한 경우도 있지만 이역시 다시 검색후에 상수배처리를 반복함으로 O(logn)을 벗어날 수 없다.
삭제역시 마찬가지이다.
5. 전체 코드
class Node:
def __init__(self, key, value, color = 'RED'):
self.key = key
self.value = value
self.color= color
self.left = self.right = self.parent = Noneclass RBT:
def __init__(self):
self.root = None
self.NIL = Node(None, None, 'BLACK')
def rotate_left(self, p):
x = p.right
#x의 왼쪽 서브트리를 p에 달아줌
p.right = x.left
if x.left != self.NIL:
x.left.parent = p
#옮겨진 x의 parent를 다시 복구
if x != self.NIL:
x.parent = p.parent
if p.parent is not None:
if p.parent.left == p:
p.parent.left = x
else:
p.parent.right = x
else:
self.root = x
#x와 p를 연결
x.left = p
if p != self.NIL:
p.parent = x
#p는 회전 축
def rotate_right(self, p):
x = p.left
#축이 오른쪽으로 이동
p.left = x.right
if x.right != self.NIL:
x.right.parent = p
#x의 부모 관계 형성
if x != self.NIL:
x.parent = p.parent
if p.parent is not None:
if p.parent.left == p:
p.parent.left = x
else:
p.parent.right = x
#p가 root였음
else:
self.root = x
#p와 x 관계형성
x.right = p
if x != self.NIL:
p.parent = x
def fix_insert(self, x):
#x의 부모가 black이면 그냥 삽입 끝 -> red일때가 문제
while x != self.root and x.parent.color == 'RED':
# p :부모 노드, pp : 조부모 노드, s : 삼촌 노드
pp = x.parent.parent
p = x.parent
if pp.left == p:
s = pp.right
else:
s = pp.left
#case 1
if s.color == 'RED':
p.color = 'BLACK'
pp.color = 'RED'
s.color = 'BLACK'
x = pp
#case2 -> 삼촌이 black
else:
#pp의 왼쪽 자식이 p
if pp.left == p:
#case 2-1
if p.right == x:
x = x.parent
self.rotate_left(x)
#case 2-2
#옮겨진 p와 pp의 색을 바꾼다.
x.parent.color = 'BLACK'
x.parent.parent.color = 'RED'
self.rotate_right(x.parent.parent)
#pp의 오른쪽 자식이 p
else:
#case 2-1
if p.left == x:
x = p
self.rotate_right(x)
x.parent.color = 'BLACK'
x.parent.parent.color = 'RED'
self.rotate_left(x.parent.parent)
self.root.color = 'BLACK'
def insert(self, key, value):
x = Node(key, value)
x.right = self.NIL
x.left = self.NIL
#들어갈 위치 찾기
cur = self.root
p = None
if self.root is None:
self.root = x
self.root.color = 'BLACK'
return x
else:
while cur != self.NIL:
if cur.key == key:
return False
else:
p = cur
if cur.key > key:
cur = cur.left
else:
cur = cur.right
x.parent = p
if p.key>x.key:
p.left = x
else:
p.right = x
#pp까지 있는지 확인
if x.parent.parent is None:
return x
else:
self.fix_insert(x)
return x
def fix_delete(self, x):
p = x.parent
while x != self.root and x.color == 'BLACK':
#x가 왼쪽 서브 트리일때
if p.left == x:
#삼촌과 삼촌 자식들을 구한다.
s = p.right
l = s.left
r = s.right
#case 1-1
if p.color == 'RED' and l.color == 'BLACK' and r.color == 'BLACK':
p.color = 'BLACK'
s.color = 'RED'
break
#case *-2
elif s.color == 'BLACK' and r.color == 'RED':
s.color = p.color
p.color = 'BLACK'
r.color = 'BLACK'
rotate_left(p)
break
#case *-3
elif s.color == 'BLACK' and l.color == 'RED' and r.color == 'BLACK':
l.color = 'BLACK'
s.color = 'RED'
rotate_right(s)
#case 2-1
elif s.color == 'BLACK' and l.color == 'BLACK' and r.color == 'BLACK':
s.color = 'RED'
x = p
#case 2-4
else:
p.color = 'RED'
s.color = 'BLACK'
rotate_left(p)
else:
#삼촌과 삼촌 자식들을 구한다.
s = p.right
l = s.left
r = s.right
#case 1-1
if p.color == 'RED' and l.color == 'BLACK' and r.color == 'BLACK':
p.color = 'BLACK'
s.color = 'RED'
break
#case *-2
elif s.color == 'BLACK' and l.color == 'RED':
s.color = p.color
p.color = 'BLACK'
rotate_right(p)
break
#case *-3
elif s.color == 'BLACK' and r.color == 'RED' and l.color == 'BLACK':
s.color = r.color
r.color = 'BLACK'
rotate_left(s)
#case 2-1
elif s.color == 'BLACK' and r.color == 'BLACK' and l.color == 'BLACK':
s.color = 'RED'
x = p
#case 2-4
else:
p.color = s.color
s.color = 'BLACK'
rotate_right(p)
x.color = 'BLACK'
def delete(self, key):
p = None
cur = self.root
cur_is_left = True
#삭제할 곳 찾기
while cur != self.NIL:
if cur.key == key:
break
else:
p = cur
if cur.key > key:
cur = cur.left
else:
cur = cur.right
if cur == self.NIL:
return False
#successor 찾기(m)
#만약 삭제할 노드의 오른쪽 또는 왼쪽이 NIL이면 그 다음 노드에 연결만 하면됨
if cur.left == self.NIL or cur.right == self.NIL:
m = cur
else:
#만약 삭제한 뒤에 채워 넣을 다음 노드를 찾는다
m = cur.right
while m.left != self.NIL:
m = m.left
#삭제할 노드의 다음 노드(m)의 다음 값을 찾는다
if m.left != self.NIL:
x = m.left
else:
x = m.right
#x와 m의 부모를 잇는다.
x.parent = m.parent
if m.parent is not None:
if m.parent.left == m:
m.parent.left = x
else:
m.parent.right = x
else:
self.root = x
#m과 cur이 같은 경우는 그냥 이으면 되는 것
if m != cur:
cur.key = m.key
cur.value = m.value
if m.color == 'RED':
return True
else:
self.fix_delete(x)
사진 출처는 쉽게배우는 알고리즘 ppt에서 가져왔습니다