③ 이동한 왼쪽 서브 트리의 휘인 데이터를 먼저 처리하고, 다시 왼쪽 서브 트리를 처리하려고 하나, 왼쪽 서브 트리가 없어 오른쪽 서브 트리를 처리하려고 한다. 그런데 오른쪽 서브 트리도 없으므로 휘인 노드는 처리가 완료되었다.
④ 현재 노드(휘인 노드)는 더 이상 처리할 것이 없으므로 앞 노드로 올라가서 처리하지 않았던 오른쪽 서브 트리로 내려간다.
⑤ 이동한 오른쪽 서브 트리의 쯔위 데이터를 먼저 처리하고, 왼쪽 서브 트리를 처리하려고 하나 왼쪽 서브 트리가 없어 오른쪽 서브 트리를 처리하려고 한다. 그런데 오른쪽 서브 트리도 없으므로 쯔위 노드는 처리가 완료되었다.
⑥ 현재 노드(쯔위 노드)는 더 이상 처리할 것이 없으므로 앞 노드(솔라 노드)로 올라간다. 앞 노드도 처리가 완료되었으므로 다시 앞 노드(화사 노드)로 올라가 오른쪽 서브 트리로 이동한다.
⑦ 이동한 오른쪽 서브 트리의 문별 데이터를 먼저 처리하고 다시 왼쪽 서브 트리로 이동한다.
⑧ 이동한 왼쪽 서브 트리의 선미 데이터를 먼저 처리하고, 다시 왼쪽 서브 트리를 처리하려고 하나 왼쪽 서브 트리가 없어 오른쪽 서브 트리를 처리하려고 한다. 그런데 오른쪽 서브 트리도 없으므로 선미 노드는 처리가 완료되었다. 그리고 트리의 모든 노드 순회가 완료되었다.
①~⑧에서 출력된 데이터를 확인하면 화사, 솔라, 휘인, 쯔위, 문별, 선미 순이다.
전위 순회인 현재 데이터 → 왼쪽 서브 트리 → 오른쪽 서브 트리 순서대로 출력된 것을 확인할 수 있다.
node = TreeNode() # 노드 생성
node.data = nameAry[0] # 데이터 입력
root = node # 첫 번째 노드를 루트 노드로 지정
memory.append(node) # 생성한 노드를 메모리에 저장
다음 두 번째 이후 데이터를 삽입할 때는 이진 탐색 트리의 특징을 고려해야 한다.
루트 노드보다 입력할 데이터가 작으면왼쪽에 삽입하고, 크면오른쪽에 삽입하도록 코드를 작성해야 한다.
name = '레드벨벳' # 두 번째 데이터
node = TreeNode() # 새 노드 생성
node.data = name # 새 노드에 데이터 입력
current = root # 현재 작업 노드를 루트 노드로 지정
if name < current.data : # 입력할 값을 현재 작업 노드의 값과 비교
current.left = node # 작으면 새 노드를 왼쪽 링크로 연결
else :
current.right = node # 크면 새 노드를 오른쪽 링크로 연결
memory.append(node) # 새 노드를 메모리에 저장
이진 탐색 트리에서 데이터를 삽입하는 일반적인 형태는 다음과 같다.
name = 6 # 위치를 찾을 새 데이터
node = TreeNode() # 새 노드 생성
node.data = name
current = root # 루트부터 시작
while True : # 무한 반복
if name < current.data : # 1단계
if current.left == None : # 4단계
current.left = node # 4단계
break
current = current.left # 2~3단계
else :
if current.right == None : # 4단계
current.right = node # 4단계
break
current = current.right
구현 : 이진 탐색 트리에서의 삽입
class TreeNode() :
def __init__ (self) :
self.left = None
self.data = None
self.right = None
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스' ]
node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)
for name in nameAry[1:] :
node = TreeNode()
node.data = name
current = root
while True :
if name < current.data :
if current.left == None :
current.left = node
break
current = current.left
else :
if current.right == None :
current.right = node
break
current = current.right
memory.append(node)
print("이진 탐색 트리 구성 완료!")
현재 노드가 부모 노드의 왼쪽 링크인지, 오른쪽 링크인지 구분하고자 코드 형태로 구현하면 다음과 같다.
if parent.left == current : # 부모 노드 왼쪽 링크와 삭제할 노드가 같으면
parent.left = None # 부모 노드 왼쪽에 None 대입
else : # 부모 노드 오른쪽 링크와 삭제할 노드가 같으면
parent.right = None # 부모 노드 오른쪽에 None 대입
del(current) # 노드 삭제
자식 노드가 하나인 노드를 삭제하는 경우
자식 노드가 하나인 노드를 삭제할 때는 삭제할 노드를 가리키는 부모 노드의 링크를 자식 노드로 먼저 변경한 후 해당 노드를 삭제해야 한다.
그런데 코드를 구현할 때는 왼쪽 자식 노드가 있는 경우와 오른쪽 자식 노드가 있는 경우로 나누어 생각해야 한다.
왼쪽 자식 노드가 있는 경우
if parent.left == current : # 부모 노드 왼쪽 링크와 삭제할 노드가 같으면
parent.left = current.left # 부모 노드의 왼쪽 링크에 왼쪽 자식 노드 대입
else : # 부모 노드 오른쪽 링크와 삭제할 노드가 같으면
parent.right = current.left # 부모 노드의 오른쪽 링크에 왼쪽 자식 노드 대입
del(current) # 노드 삭제
오른쪽 자식 노드가 있는 경우
if parent.left == current : # 부모 노드 왼쪽 링크와 삭제할 노드가 같으면
parent.left = current.right # 부모 노드의 왼쪽 링크에 오른쪽 자식 노드 대입
else : # 부모 노드 오른쪽 링크와 삭제할 노드가 같으면
parent.right = current.right # 부모 노드의 오른쪽 링크에 오른쪽 자식 노드 대입
del(current) # 노드 삭제
자식 노드가 둘 있는 노드를 삭제하는 경우
자식 노드가 둘 있는 노드를 삭제할 때는 재귀를 사용해야 편리하다.
① 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색한다. (또는 삭제할 노드의 오른쪽 서브 트리에서 키 값이 가장 작은 노드를 검색한다.) ② 검색한 노드를 삭제할 노드의 위치로 옮긴다. ③ 옮긴 노드를 삭제한다. 삭제 시, 자식 노드의 개수에 따라 데이터가 조정된다. ▶ 옮긴 노드에 자식이 없을 경우 : 옮긴 노드의 부모는 자식으로 None을 가진다. ▶ 옮긴 노드에 자식이 1개 있을 경우 : 옮긴 노드의 부모는 그 자식으로 옮긴 노드의 자식을 가진다.
6 삭제 : 옮길 노드에 자식이 없는 경우
5 삭제 : 옮길 노드에 자식이 1개 있는 경우
8 삭제
7 삭제
구현 : 이진 탐색 트리에서의 삭제
class TreeNode() :
def __init__ (self) :
self.left = None
self.data = None
self.right = None
memory = []
root = None
nameAry = ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스' ]
node = TreeNode()
node.data = nameAry[0]
root = node
memory.append(node)
for name in nameAry[1:] :
node = TreeNode()
node.data = name
current = root
while True :
if name < current.data :
if current.left == None :
current.left = node
break
current = current.left
else :
if current.right == None :
current.right = node
break
current = current.right
memory.append(node)
deleteName = '마마무'
current = root
parent = None
while True:
if deleteName == current.data :
if current.left == None and current.right == None :
if parent.left == current :
parent.left = None
else :
parent.right = None
del(current)
elif current.left != None and current.right == None :
if parent.left == current :
parent.left = current.left
else :
parent.right = current.left
del(current)
elif current.left == None and current.right != None :
if parent.left == current:
parent.left = current.right
else:
parent.right = current.right
del(current)
print(deleteName, '이(가) 삭제됨.')
break
elif deleteName < current.data :
if current.left == None :
print(deleteName, '이(가) 트리에 없음')
break
parent = current
current = current.left
else:
if current.right == None :
print(deleteName, '이(가) 트리에 없음')
break
parent = current
current = current.right
