#10 레드블랙 트리(Red-Black Tree) 구현

#10 레드블랙 트리(Red-Black Tree) 구현

1. ADT 작성

RBTree: Datas: __root : 트리의 루트노드 __size : 트리의 크기 Operations: insert(key) : 키 값이 key인 노드를 트리에 삽입 delete(key) : 키 값이 key인 노드를 트리에서 제거. 성공할 경우 True, 실패할 경우 False 반환 get(key) : 키 값이 key 인 노드를 트리에서 탐색하여 해당 노드의 데이터를 반환. RBTree.__Node: Datas: key : 노드의 키 값 color : 노드의 색상 (0: 검은색, 1: 붉은색) parent : 부모노드 left : 좌측 자식노드 right : 우측 자식노드 IS_NIL : NIL 노드 여부 Operations: -

2. 구현

# 레드블랙 트리 클래스 class RBTree: # 노드 클래스 class __Node: # 노드 생성자 # 기본적으로 NIL 노드로 생성된다 def __init__(self, p=None): # 키값은 None, 색은 0(검은색) self.key = None self.color = 0 # 부모노드 self.parent = p # 좌측 자식노드, 우측 자식노드는 None self.left = None self.right = None # NIL 여부 True self.IS_NIL = True # 트리 생성자 def __init__(self): # 루트노드에 NIL 노드 세팅 self.__root = self.__Node() # 트리의 크기 0으로 초기화 self.__size = 0 # len 함수의 결과를 구현 def __len__(self): # 트리의 크기 반환 return self.__size # 데이터 삽입 함수 def insert(self, key): # 삽입할 위치 탐색 cursor = self.__root while not cursor.IS_NIL: # 현재 노드보다 키 값이 크다면 우측 자식노드로 이동 if cursor.key < key: cursor = cursor.right # 현재 노드보다 키 값이 작다면 좌측 자식노드로 이동 elif cursor.key > key: cursor = cursor.left # 이미 키 값이 존재할 경우 삽입 종료(삽입안함) else: return False # 삽입 위치의 NIL 노드에 key, color, 좌측 자식노드, 우측 자식노드를 세팅하고 NIL 여부를 False 로 한다 cursor.key = key cursor.color = 1 cursor.left = self.__Node(cursor) cursor.right = self.__Node(cursor) cursor.IS_NIL = False # 트리 크기 1 증가 self.__size += 1 # 루트노드의 색은 검은색 self.__root.color = 0 # insert_fix 를 수행하여 RB 트리의 규칙을 유지 self.__insert_fix(cursor) # 삽입 이후 규칙에 맞게 트리를 수정하는 함수 def __insert_fix(self, node): parent = node.parent # 부모노드가 존재하고 붉은색인 동안 반복 # 루트노드는 검은색이기 떄문에 부모노드가 붉은색이면 반드시 조부모 노드가 존재 while parent and parent.color == 1: # 조부모노드 grand_parent = parent.parent # 부모노드와 노드가 어느쪽 자식노드인지 확인 # True: 좌측 / False: 우측 parent_direction = (grand_parent.left == parent) node_direction = (parent.left == node) # 삼촌노드 uncle_node = grand_parent.right if parent_direction else grand_parent.left # 케이스 1. Recoloring # 삼촌 노드가 붉은색인 경우 if uncle_node.color == 1: # 삼촌노드와 부모노드를 모두 검은색으로 변경 uncle_node.color = parent.color = 0 # 조부모노드를 붉은색으로 변경 grand_parent.color = 1 # 조부모노드를 삽입노드로 하여 fix 를 다시 수행 node = grand_parent parent = node.parent continue # 케이스 2. Restructuring # 삼촌 노드가 검은색인 경우 else: # 부모노드와 노드가 서로 다른 방향의 자식노드인 경우(LR, RL 형태) if node_direction != parent_direction: # LR 형태인 경우 LL 형태로 변형 if parent_direction: self.__left_rotation(parent) # RL 형태인 경우 RR 형태로 변형 else: self.__right_rotation(parent) # 회전에 의해 parent 와 node 가 뒤바뀜 node, parent = parent, node # LL 형태인 경우 조부모노드에 대해 right_rotation if parent_direction: self.__right_rotation(grand_parent) # RR 형태인 경우 조부모노드에 대해 left_rotation else: self.__left_rotation(grand_parent) # 부모노드가 된 parent 노드의 색을 검은색으로, 나머지 두 노드는 붉은색으로 한다 parent.color = 0 grand_parent.color = 1 node.color = 1 # Restructuring 은 추가작업을 필요로하지 않음 break # 루트노드는 항상 검은색 self.__root.color = 0 # 좌측 회전 함수 def __left_rotation(self, node): if node.IS_NIL or node.right.IS_NIL: return parent = node.parent right_tmp = node.right node.right = right_tmp.left right_tmp.left.parent = node right_tmp.left = node node.parent = right_tmp right_tmp.parent = parent if parent: if node == parent.left: parent.left = right_tmp else: parent.right = right_tmp else: self.__root = right_tmp # 우측 회전 함수 def __right_rotation(self, node): if node.IS_NIL or node.left.IS_NIL: return parent = node.parent left_tmp = node.left node.left = left_tmp.right left_tmp.right.parent = node left_tmp.right = node node.parent = left_tmp left_tmp.parent = parent if parent: if node == parent.left: parent.left = left_tmp else: parent.right = left_tmp else: self.__root = left_tmp # 데이터 삭제 함수 def delete(self, key): # 삭제할 노드 탐색 target = self.__search(key) # 삭제할 노드를 찾지 못한 경우 if not target: return False # 삭제 후 fix 를 위한 변수 child, s_color = None, None # target 이 리프노드인 경우 if target.left.IS_NIL and target.right.IS_NIL: child, s_color = target, target.color target.key = None target.left = target.right = None target.IS_NIL = True target.color = 0 # 좌측 자식노드를 가진 경우 elif not target.left.IS_NIL: # 좌측 서브트리중 가장 오른쪽의 노드를 구한다 successor = target.left while not successor.right.IS_NIL: successor = successor.right # successor 의 좌측 자식노드와 색상 저장 child, s_color = successor.left, successor.color # 삭제할 노드의 키값을 successor 의 키값으로 변경 target.key = successor.key # successor 가 target 의 좌측 자식노드인 경우 if successor == target.left: # successor 의 부모노드의 좌측 자식노드를 successor 의 좌측 자식노드로 설정 successor.parent.left = successor.left # successor 가 target 의 좌측 자식노드가 아닌 경우 else: # successor 의 부모노드의 우측 자식노드를 successor 의 좌측 자식노드로 설정 successor.parent.right = successor.left # successor 의 좌측 자식노드의 부모노드를 successor 의 부모노드로 설정 successor.left.parent = successor.parent # 우측 자식노드만 가진 경우 else: # 우측 서브트리중 가장 왼쪽의 노드를 구한다 successor = target.right while not successor.left.IS_NIL: successor = successor.left # successor 의 우측 자식노드와 색상 저장 child, color = successor.right, successor.color # 삭제할 노드의 키값을 successor 의 키값으로 변경 target.key = successor.key # successor 가 target 의 우측 자식노드인 경우 if successor == target.right: # successor 의 부모노드의 우측 자식노드를 successor 의 우측 자식노드로 설정 successor.parent.right = successor.right # successor 가 target 의 우측 자식노드가 아닌 경우 else: # successor 의 부모노드의 좌측 자식노드를 successor 의 우측 자식노드로 설정 successor.parent.left = successor.right # successor 의 우측 자식노드의 부모노드를 successor 의 부모노드로 설정 successor.right.parent = successor.parent # 트리 크기 1 감소 self.__size -= 1 # 삭제이후 fix 과정 # 트리가 비어있지 않은 경우 if child.parent: # successor 가 검은색이었던 경우 if s_color == 0: # child 는 붉은색인 경우 if child.color == 1: child.color = 0 # child 도 검은색인 경우 else: self.__delete_fix(child) return True # 삭제 이후 규칙에 맞게 트리를 수정하는 함수 def __delete_fix(self, child): # child 의 부모 노드 parent = child.parent while parent: # True 일 경우 child 는 parent 의 좌측 자식노드 False 일 경우 우측 자식노드 child_direction = (child == parent.left) # 형제노드 sibling = parent.right if child_direction else parent.left # 조카노드 n1, n2 = sibling.left, sibling.right # parent 가 붉은색인 경우 if parent.color == 1: # 케이스 1. sibling, n1, n2 가 모두 검은색인 경우 if sibling.color == n1.color == n2.color == 0: # parent 와 sibling 의 색을 교환하고 종료 parent.color, sibling.color = sibling.color, parent.color break # parent 가 검은색인 경우 else: # 케이스 2. sibling, n1, n2도 모두 검은색인 경우 if sibling.color == n1.color == n2.color == 0: # sibling 의 색을 붉은색으로 바꾼 뒤 child 를 parent 로, # parent 를 parent 의 부모노드로 하여 continue sibling.color = 1 child, parent = parent, parent.parent continue # 케이스 3. sibling 은 붉은색, n1, n2는 검은색인 경우 elif sibling.color == 1 and n1.color == n2.color == 0: # parent 와 sibling 의 색을 교환 parent.color, sibling.color = sibling.color, parent.color # child 노드의 방향에 따라 회전 수행 if child_direction: self.__left_rotation(parent) else: self.__right_rotation(parent) continue # parent 의 색에 무관한 경우 # sibling 의 색이 검은색인 경우 if sibling.color == 0: # 가까운 조카노드가 n1, 먼 조카노드가 n2가 되도록 한다 if not child_direction: n1, n2 = n2, n1 # 케이스 4. 먼 조카노드 n2가 붉은색인 경우 if n2.color == 1: # parent 와 sibling 의 색을 교환하고 n2의 색을 검은색으로 변경 parent.color, sibling.color = sibling.color, parent.color n2.color = 0 # child 노드의 방향에 따라 회전 수행 if child_direction: self.__left_rotation(parent) else: self.__right_rotation(parent) break # 케이스 5. 가까운 조카노드 n1이 붉은색이고 먼 조카노드 n2가 검은색인 경우 if n1.color == 1 and n2.color == 0: # sibling 과 n1의 색을 교환 sibling.color, n1.color = n1.color, sibling.color # child 노드의 방향에 따라 회전 수행 if child_direction: self.__right_rotation(sibling) else: self.__left_rotation(sibling) continue # 루트노드의 색은 항상 검은색 self.__root.color = 0 # 키 값이 key 인 노드의 데이터를 반환하는 함수 # 여기서 노드에는 데이터 값이 따로 없기 때문에 키 값을 반환 # 노드를 찾을 수 없다면 None 반환 def get(self, key): target = self.__search(key) if target: return target.key else: return None # 키 값이 key인 노드를 반환하는 함수 def __search(self, key): # 루트 노드부터 탐색 시작 cursor = self.__root while not cursor.IS_NIL: # 현재 노드의 키값보다 key 가 더 크다면 우측 자식노드로 이동 if cursor.key < key: cursor = cursor.right # 현재 노드의 키값보다 key 가 더 작다면 좌측 자식노드로 이동 elif cursor.key > key: cursor = cursor.left # key 에 해당하는 노드를 찾았다면 노드반환 else: return cursor # 찾지 못했을 경우 None 반환 return None # 트리를 중위순회로 출력하는 함수. # 붉은 노드가 연속으로 붙어있지 않은지 체크 def in_order(self): self._dfs(self.__root, 0, 0) def __dfs(self, node, bcnt, pre): if node.color == 0: bcnt += 1 if not node.left.IS_NIL: self._dfs(node.left, bcnt, node.color) print(node.key, ':', bcnt, ':color=', node.color, "invalid" if pre == node.color == 1 else "valid") if not node.right.IS_NIL: self._dfs(node.right, bcnt, node.color)

최소한의 기능인 insert, delete, get 과 테스트용 inorder 함수만을 구현

그 외의 함수나 멤버변수는 사용자측에선 볼 수 없도록 private 로 선언

from http://scala0114.tistory.com/120 by ccl(A) rewrite - 2021-10-14 18:00:37