코드 9-5를 보면 BST의 insert 연산과 거의 같습니다. 다만 while 문 내에서 새로운 노드를 삽입하고 바로 끝내지 않고 while 문을 빠져나와 __insert_fix() 메서드를 호출하여 노드의 재배치를 수행합니다. 마지막으로 핵심 연산을 담당할 __insert_fix 메서드의 코드를 보겠습니다.
코드 9- 6
def __insert_fix(self, n):
pn = gn = un = None ➊
pn = n.parent
while pn != None and pn.color == "RED": ➋
gn = pn.parent ➌
if gn.left == pn: ➍
un = gn.right
if un.color == "RED": ➎
➏
gn.color = "RED"
pn.color = un.color = "BLACK"
n = gn ➐
pn = n.parent
else: ➑
if pn.right == n: ➒
self.__left_rotate(pn)
n, pn = pn, n
pn.color, gn.color = gn.color, pn.color ➓
self.__right_rotate(gn)
else: 11
un = gn.left 12
if un.color == "RED":
gn.color = "RED"
pn.color = un.color = "BLACK"
n = gn
pn = n.parent
else:
if pn.left == n:
self.__right_rotate(pn)
n, pn = pn, n
pn.color, gn.color = gn.color, pn.color
self.__left_rotate(gn)
self.__root.color = "BLACK" 13
➊ pn: n의 부모
gn: n의 조부모
un: pn의 형제
➋ n이 루트가 아니고 n.parent가 RED면 연속된 RED
➌ pn이 RED면 반드시 gn이 존재: 루트는 BLACK이므로 pn은 루트가 될 수 없습니다.
➍ pn이 gn의 왼쪽 자식일 때
➎ XYr: 부모 형제가 RED일 때
➏ 부모, 부모 형제와 조부모의 색을 변경
➐ gn을 새로운 n으로 만든 후 연속된 레드가 또 일어나는지 확인
➑ XYb: 부모 형제가 BLACK일 때
➒ LRb일 때
➓ LLb일 때 부모와 조부모의 색을 바꾸고
11 pn이 gn의 오른쪽 자식일 때
12 조부모의 왼쪽 자식이 외부 노드일 때 부모 형제를 en으로 대체
13 연속된 레드가 루트까지 올라왔을 때는 루트를 BLACK으로 만들어 주면 됩니다.