레드 블랙 트리 파이썬 구현 핸드북
핵심 요약 파이썬으로 구현된 레드 블랙 트리는 이진 탐색 트리(BST)에 색 정보(빨강/검정)를 추가하여 삽입·삭제 시 자가 균형을 유지한다. 모든 연산이 최악 시간에 수행되며, 색 재배치와 회전 연산을 통해 **검정 높이(equal black-height)**를 보장한다.
1. 클래스 및 노드 구조
class RBNode:
def __init__(self, value, color='red'):
self.value = value # 노드 값
self.color = color # 'red' 또는 'black'
self.left = None # 왼쪽 자식
self.right = None # 오른쪽 자식
self.parent = None # 부모 노드
def grandparent(self):
if self.parent is None:
return None
return self.parent.parent
def sibling(self):
if self.parent is None:
return None
return self.parent.right if self == self.parent.left else self.parent.left
def uncle(self):
gp = self.grandparent()
if gp is None:
return None
return gp.right if self.parent == gp.left else gp.left- RBNode: 값, 색, 부모·자식 포인터를 가짐.
- grandparent(), sibling(), uncle(): 삽입/삭제 균형 복구 시 색·회전 대상을 판별.
2. 트리 클래스 및 탐색
class RedBlackTree:
def __init__(self):
self.root = None
def search(self, value):
node = self.root
while node:
if value == node.value:
return node
node = node.left if value < node.value else node.right
return None- search(value): 일반 BST 방식으로 값 탐색, 없으면
None반환.
3. 삽입 연산
3.1 BST 삽입
def insert(self, value):
new_node = RBNode(value)
if self.root is None:
self.root = new_node
else:
curr = self.root
while True:
if value < curr.value:
if curr.left is None:
curr.left = new_node
new_node.parent = curr
break
curr = curr.left
else:
if curr.right is None:
curr.right = new_node
new_node.parent = curr
break
curr = curr.right
self.insert_fix(new_node)- 새 노드를 빨강으로 추가 후,
insert_fix호출.
3.2 삽입 후 균형 복구
def insert_fix(self, node):
while node.parent and node.parent.color == 'red':
gp = node.grandparent()
if node.parent == gp.left:
uncle = gp.right
if uncle and uncle.color == 'red':
# Case 1: 부모·삼촌이 빨강
node.parent.color = uncle.color = 'black'
gp.color = 'red'
node = gp
else:
if node == node.parent.right:
# Case 2: LR 회전 전 단계
node = node.parent
self.rotate_left(node)
# Case 3: LL
node.parent.color = 'black'
gp.color = 'red'
self.rotate_right(gp)
else:
uncle = gp.left
if uncle and uncle.color == 'red':
node.parent.color = uncle.color = 'black'
gp.color = 'red'
node = gp
else:
if node == node.parent.left:
node = node.parent
self.rotate_right(node)
node.parent.color = 'black'
gp.color = 'red'
self.rotate_left(gp)
self.root.color = 'black'- Case 1: 부모·삼촌 빨강 → 색 재배치.
- Case 2: 삽입 노드가 반대쪽 자식 → 단일 회전.
- Case 3: 같은쪽 자식 → 회전 후 색 교환.
4. 회전 연산
def rotate_left(self, node):
right = node.right
node.right = right.left
if right.left: right.left.parent = node
right.parent = node.parent
if node.parent is None:
self.root = right
elif node == node.parent.left:
node.parent.left = right
else:
node.parent.right = right
right.left = node
node.parent = right
def rotate_right(self, node):
left = node.left
node.left = left.right
if left.right: left.right.parent = node
left.parent = node.parent
if node.parent is None:
self.root = left
elif node == node.parent.right:
node.parent.right = left
else:
node.parent.left = left
left.right = node
node.parent = left- rotate_left/node: 오른쪽 자식을 올림.
- rotate_right/node: 왼쪽 자식을 올림.
5. 삭제 연산
5.1 BST 삭제 및 대체
def delete(self, value):
node = self.search(value)
if node is None:
return
# 자식 1개 이하
if node.left is None or node.right is None:
self._replace_node(node, node.left or node.right)
else:
succ = self._find_min(node.right)
node.value = succ.value
self._replace_node(succ, succ.right)
self.delete_fix(node)- _replace_node(old, new): 부모 연결 재설정.
def _replace_node(self, old, new):
if old.parent is None:
self.root = new
elif old == old.parent.left:
old.parent.left = new
else:
old.parent.right = new
if new:
new.parent = old.parent
def _find_min(self, node):
while node.left:
node = node.left
return node5.2 삭제 후 균형 복구
def delete_fix(self, x):
while x != self.root and x.color == 'black':
if x == x.parent.left:
sibling = x.sibling()
if sibling.color == 'red':
sibling.color = 'black'
x.parent.color = 'red'
self.rotate_left(x.parent)
sibling = x.sibling()
if (not sibling.left or sibling.left.color=='black') and \
(not sibling.right or sibling.right.color=='black'):
sibling.color = 'red'
x = x.parent
else:
if not sibling.right or sibling.right.color=='black':
sibling.left.color = 'black'
sibling.color = 'red'
self.rotate_right(sibling)
sibling = x.sibling()
sibling.color = x.parent.color
x.parent.color = 'black'
if sibling.right:
sibling.right.color = 'black'
self.rotate_left(x.parent)
x = self.root
else:
# mirror of above for 오른쪽 자식일 때
sibling = x.sibling()
if sibling.color == 'red':
sibling.color = 'black'
x.parent.color = 'red'
self.rotate_right(x.parent)
sibling = x.sibling()
if (not sibling.left or sibling.left.color=='black') and \
(not sibling.right or sibling.right.color=='black'):
sibling.color = 'red'
x = x.parent
else:
if not sibling.left or sibling.left.color=='black':
sibling.right.color = 'black'
sibling.color = 'red'
self.rotate_left(sibling)
sibling = x.sibling()
sibling.color = x.parent.color
x.parent.color = 'black'
if sibling.left:
sibling.left.color = 'black'
self.rotate_right(x.parent)
x = self.root
x.color = 'black'- 형제가 빨강 → 회전 및 색 교환.
- 형제·자식 모두 검정 → 형제 빨강, 더블 블랙 상향.
- 형제 검정·자식 중 빨강 존재 → 적절 회전 및 색 교환.
6. 사용 예시 및 테스트
if __name__ == "__main__":
tree = RedBlackTree()
for v in [10, 20, 30, 40, 50, 25]:
tree.insert(v)
print("중위 순회:", end=" ")
tree._inorder_traversal(tree.root) # 10 20 25 30 40 50
tree.delete(20)
print("\n삭제 후 중위 순회:", end=" ")
tree._inorder_traversal(tree.root) # 10 25 30 40 50- 삽입·삭제 후 중위 순회를 통해 BST 정렬 속성 유지 확인.
7. 결론 및 활용
- 기초 자료구조 수업, 면접 과제, 라이브러리 내부 구현 학습용으로 적합.
- C++ STL
map/set, JavaTreeMap등의 내부 구조와 동일한 논리. - 동적 데이터 삽입·삭제가 빈번한 시스템(운영체제 스케줄러, 데이터베이스 인덱스)에 응용 가능.
참고: 본 구현은 GeeksforGeeks 예시를 기반으로 상세 설명 및 주석을 추가하여 완전한 동작을 보장합니다1.
⁂