트리 : [4] 이진탐색트리
이진탐색트리(Binary Search Tree)는 탐색작업을 효율적으로 수행하기 위해 만들어진 이진트리다.
ㄴ 임의의 노드 기준으로 노드의 값(Key, value)보다 (1) 작으면 왼쪽, (2) 크면 오른쪽에 저장한다.
ㄴ 결과적으로 가장 왼쪽 끝의 자식노드에는 가장 작은 값을, 가장 오른쪽 끝의 자식노드에는 가장 큰 값을 갖는다.
ㄴ 이진탐색트리를 중위순회하게되면, 오름차순으로 정렬된 배열을 출력한다.
이진탐색트리 연산
위에서 말한 바와 같이 이진탐색트리를 구현하기 위해선 (1) 삽입, (2) 삭제연산을 구현해야 한다.
(1) 삽입연산
이진탐색트리가 존재할 때, 새로운 값을 삽입하고자 할 때 사용하는 방법이다. 핵심은 새롭게 삽입하고자 하는 변수(key)와 트리 내 존재하는 노드의 값을 순차적으로 비교하여 새로운 변수의 위치를 결정하는데 있다. 이를 구현하기 위해 현재 노드를 나타내는 $c$와 그 노드의 부모를 가르키는 $p$ 두 가지의 변수를 사용한다.
# Node Version
class Node:
"""
Node라는 타입의 변수 선언이 필요하고,
각 노드는 독립된 메모리 공간에 할당되어야 하므로, 인스턴스 선언이 필요하다.
이를 위해 아래와 같이 초기화 진행
"""
def __init__(self, key=None, left=None, right=None):
self.key = key
self.left = left
self.right = right
def insertion_node(bsTree : Node, key : float):
"""
bsTree : binary search tree(bsTree)의 root 노드
class Node 타입
key : 새롭게 삽입하고자 하는 값 (실수)
"""
# initialize
c = bsTree # 맨처음 current(c)는 root 노드가 된다. (c -> root)
p = None # c의 부모노드 (루트노드에는 부모가 없으므로 None)
# STEP 1: 새롭게 삽입할 변수(key)의 위치 탐색
while c.key != None:
# 예외처리) 삽입하고자 하는 값이 이미 트리에 존재
if key == c.key:
print(f"{key}는 현재 노드에 존재함.")
return None # 삽입연산 종료
# 부모노드 위치 갱신
p = c # c의 위치를 갱신하기 전 부모에 위치를 물려준다.
# c의 위치 갱신 (=key의 위치찾기)
elif key < c.key: c = p.left # key값이 현재노드(c)보다 작음
else: c = p.right # key값이 현재노드(c)보다 큼
# STEP 2: 삽입할 노드 생성
n = Node(key=key) # n : new node
# STEP 3: 생성한 노드 삽입
if p==None: # 현재 이진탐색트리 empty
c = n
else:
if key < p.key: p.left = n
else: p.right = n
# 연산종료
return bsTree# Array version
class Array(list):
pass
def insertion_array(bsTree : Array, key : float):
# initialize
cIdx = 1 # 현재 노드의 인덱스(current index, cIdx)
c = bsTree[cIdx] # 배열로 구현된 이진트리에서는 index=1이 루트노드다.
p = None
# STEP 1 : key의 위치탐색
while c!=None:
# 예외처리) 삽입하고자 하는 값이 이미 트리에 존재
if key==c:
print(f"{key}는 현재 이진탐색트리에 존재")
return None # 연산 종료
# initialize
p = cIdx # 현재 인덱스를 부모노드에 갱신
# key의 삽입할 위치탐색
if key < c: cIdx = 2*cIdx # key가 현재노드보다 작은 경우 왼쪽 index
else: cIdx = 2*cIdx+1 # key가 현재노드보다 큰 경우 오른쪽 index
# 현재노드(c) 갱신
if cIdx > len(bsTree)-1: # cIdx가 현재 배열의 범위를 벗어남
raise IndexError("배열의 길이보다 삽입할 위치의 index가 큼 > 배열을 포화이진트리로 구성 필요")
else:
c = bsTree[cIdx]
# STEP 2 : key 삽입
bsTree[cIdx] = key
return bsTree
(2) 삭제연산
삭제연산은 이진탐색트리 내 특정 노드를 삭제하는 연산이다. 삭제연산의 포인트는, 삭제하고자 하는 노드의 부모와 자식을 연결시켜 주는데 있다. 이때 삭제하고자 하는 노드의 자식이 어떤 형태로 존재하는지에 따라 3가지 유형으로 구분하여 구현한다.
- CASE 1 : 서브트리가 없는 경우 (단말노드인 경우)
- CASE 2 : 한 개의 서브트리만 있는 경우
- CASE 3 : 두 개의 서브트리만 있는 경우
CASE 1 : 서브트리가 없는 경우 (단말노드인 경우)
삭제하고자 하는 노드의 자식노드(서브트리)가 없는 경우, 해당 노드의 부모노드는 자식으로 연결할 서브트리가 없다. 따라서 이 경우, 삭제하고자 하는 노드 자리를 NULL로 변경해주면 된다.
CASE 2 : 한 개의 서브트리만 있는 경우
삭제하고자 하는 노드에 서브트리가 1개만 존재하는 경우, 삭제하고자 하는 노드의 부모노드에 서브트리를 자식 노드로연결시켜 주면 된다. 노드 내에 저장된 값의 크기 비교는 이미 사전에 완료된 상태이므로, 크기에 대한 걱정 없이, 삭제하고자 하는 노드의 자식노드를 부모노드에 승계해주면 된다.
CASE 3 : 두 개의 서브트리 모두 있는 경우
두 개의 서브트리가 존재하는 경우, 삭제하고자 하는 노드를 자식 노드 중에서 이진탐색트리의 제약 조건을 만족하는 노드로 대체하면 된다. 다시 말해, 삭제하고자 하는 노드의 서브트리에 해당하는 값 중에서, 좌측 서브트리 내 값들 보다는 크고, 우측 서브트리 내 값들보다는 작은 값을 갖는 노드를 찾아야 한다. 이는 이진탐색트리의 구조를 생각했을 때, 좌측 서브트리 내에서는 가장 우측에 위치하는 노드 또는 우측 서브트리에서는 가장 좌측에 위치한 노드가 된다.
이를 각각 중위 선행자, 중위 후속자라 한다. 즉, 둘 중 한 노드를 삭제하고자 하는 노드로 대체하면 된다. 이때 중위 후속자는 스레드 이진트리 구현에서 등장했던 개념이다. 의미를 다시 설명하면, 중위순회를 수행했을 때, 해당 노드의 바로 앞에 나오는 노드(= 지우고자 하는 노드보다 작은 값 중에서 가장 큰 값)를 중위 선행자, 바로 뒤에 나오는 노드(= 지우고자 하는 노드보다 큰 값 중에서 가장 작은 값)를 중위 후속자라 한다.
위 세 가지 케이스의 노드 버전 구현은 다음과 같다.
# Node version
class Node:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def deletion_node(bsTree : Node, key : float):
"""
bsTree : binary search tree의 root 노드
class Node 타입
key : Node의 값
해당 삭제 연산의 경우, 중위 후속자를 사용하는 방식으로 구현
"""
# initialize
c = bsTree # current node(c)
p = None # current node의 부모노드
# 삭제할 대상 탐색
while c is not None and key != c.key:
# 부모노드에 현재 노드 인계
p = c
# 찾고자 하는 노드의 위치 탐색
if key < c.key: c = p.left
else: c = p.right
# 찾고자 하는 노드가 존재하지 않음
if c is None:
print(f"{key}는 이진트리내 존재하지 않음")
return None
# case 1 : 자식노드가 없는 경우
if c.left is None and c.right is None:
if p is None: # 삭제대상이 루트노드인 경우 > 부모노드(p)가 없음
bsTree = None
else:
if key < p.key: p.left is None
else: p.right = None
# case 2 : 자식노드가 1개만 존재하는 경우
elif c.left is None or c.right is None:
# 자식노드
if c.left is None: child = c.right
else: child = c.left
if p is None: # 삭제대상이 루트노드인 경우 > 부모노드(p)가 없음
bsTree = child
else:
if key < p.key: p.left = child
else: p.right = child
# case 3 : 자식노드가 2개 존재하는 경우
else:
# 중위 후속자 찾기
succ_p = c # 중위 후속자의 부모 (parent of successor)
succ = c.right # 후속자를 찾을 것이므로 오른쪽 서브트리로 이동
# 중위 후속자는 오른쪽 서브트리에서 가장 왼쪽에 존재한다.
while succ.left is not None:
succ_p = succ
succ = succ.left
# 후속자는 삭제하고자 하는 노드로 대체될 것이므로, 다음 후속자의 부모와 자식을 서로 연결해줘야 한다.
# 즉, 현재 위치에서 중위 후속자 삭제
# 아래 설명 참조
if succ_p.right = succ:
succ_p.right = succ.right
elif succ_p.left = succ:
succ_p.left = succ.right
# 삭제하고자 하는 노드의 값을 중위 후속자의 값으로 대체한다.
c.key = succ.key
c = succ
del c # current node 변수 삭제
위 코드 구현에서 # 아래 설명 참조 부분은, 찾은 중위 후속자를 현재 위치에서 삭제하고, 중위 후속자의 부모와 자식을 서로 연결시켜주는 부분이다. 이때, 중위 후속자의 부모와 자식은 두 가지 유형으로 존재할 수 있는데, (1) 삭제하고자 하는 노드의 오른쪽 서브트리의 루트노드가 중위후속자인 경우, (2) 오른쪽 서브트리의 루트노드가 중위 후속자가 아닌 경우다. 다시 말해 (1)의 경우는, 삭제하고자 하는 노드의 오른쪽 서브트리를 봤을 때, 해당 서브트리의 루트노드 왼쪽에 더 이상 값이 존재하지 않는 경우로, 루트노드가 중위 후속자가 된다. 이 경우, 중위 후속자의 부모노드 오른쪽에 중위 후속자의 자식노드가 위치하게 되므로, succ_p.right = succ.right로 상호 연결해주면 된다.
(2)의 경우는 오른쪽 서브트리의 노드가 중위 후속자가 아닌 경우로, 이 경우 중위 후속자 부모의 왼쪽에 중위 후속자의 자식 노드를 연결해주면 된다. 이때 중위 후속자는 해당 서브트리의 가장 왼쪽에 위치하기 때문에 왼족 자식노드를 가지고 있지 않다.
(2) 경우의 그림이 다소 (1) 경우의 그림보다 복잡하지만, "후속자의 부모와 후속자의 자식을 연결하고, 삭제하고자 하는 노드의 값을 후속자의 값으로 바꾼다."는 프로세스는 동일하다. 단지 위에서 말한 바와 같이 후속자의 부모와 자식 간 관계가 다른 것에 불과하다.