이진트리는 다음과 같은 조건을 지님
NULL
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
먼저 Node
에 대한 클래스를 만들어 줌
class BinaryTree:
def __init__(self, root):
self.root = root
def insert(self, data):
self.curr_node = self.root
while True:
if self.curr_node.data < data:
if self.curr_node.right != None:
self.curr_node = self.curr_node.right
else:
self.curr_node.right = Node(data)
break
else:
if self.curr_node.left != None:
self.curr_node = self.curr_node.left
else:
self.curr_node.left = Node(data)
break
그 다음 비어있는 트리를 포함해서, 삽입하는 메소드까지 넣어줌
이어서, 탐색 -> 삭제 순으로 작성하는데, 이후에는 코드가 길어지므로 들여쓰기를 좀 하겠음
실제론 BinaryTree
클래스 안에 들어있으므로 그 점 유의
def search(self, data):
self.curr_node = self.root
while self.curr_node:
if self.curr_node.data == data:
print(data)
return True
elif self.curr_node.data > data:
print(self.curr_node.data)
self.curr_node = self.curr_node.left
else:
print(self.curr_node.data)
self.curr_node = self.curr_node.right
return False
찾고자 하는 값이 현재 노드의 값보다 크냐 작으냐의 비교를 지속적으로 해서, 작으면 왼쪽, 크면 오른쪽으로 재귀호출대신에 반복문을 사용 이렇게 하기 때문에 시간복잡도가 순차탐색보다 더 낮은 로그가 나오게 됨
다음은 제일 고난이도이자 머리가 아픈 delete
삭제를 하기 위해선 크게 세가지를 생각해야함
def delete(self, data):
self.curr_node = self.root
self.parent = self.curr_node
searched = False
while self.curr_node: # 값을 찾기위한 여정
if self.curr_node.data == data:
searched = True
break
elif self.curr_node.data > data:
self.parent = self.curr_node
self.curr_node = self.curr_node.left
else:
self.parent = self.curr_node
self.curr_node = self.curr_node.right
if searched == False: # 만약 True가 아니면 값을 찾지 못했단 증거
return False
# 일단 여기까지 왔다는 건 값을 찾긴 찾았다는 의미
# 그럼 이제 리프노드에서 삭제, 즉 자식 노드가 1개도 없는지
# 트리 한가운데에서 삭제인데, 자식노드가 1개인지
# 트리 한가운데에서 삭제인데, 자식노드가 2개인지를 구별해 코드를 짜야 함
if self.curr_node.left == None and self.curr_node.right == None:
if self.parent.data > data: # 지우고자 하는 리프노드가 부모노드 왼쪽?
self.parent.left = None
else: #아니면 오른쪽?
self.parent.right = None
elif self.curr_node.left != None and self.curr_node.right == None:
#왼쪽에만 자식이 한 개 있는 경우
if data < self.parent.data: #현재 노드 자식과 부모 비교
self.parent.left = self.curr_node.left
else: # 크면 부모의 오른쪽, 작으면 부모의 왼쪽에 배치
self.parent.right = self.curr_node.left
elif self.curr_node.left == None and self.curr_node.right != None:
if data < self.parent.data:
self.parent.left = self.curr_node.right
else:
self.parent.right = self.curr_node.left
else: # 두 개의 자식이 있는 경우
# 방법은 두 가지가 있는데, 하나만 써도 상관없기 때문에 1개만 씀
# 1.오른쪽 자식 노드로 가서, 가장 값이 작은 노드가 나올때까지 반복문 실시
# 2.삭제할 값의 노드를 지우면 까다로우므로, 그냥 작은 노드의 value 삽입
# 3.그 노드가 오른쪽 자식이 있으면, 그 노드의 자리에 자식이 대신함
change = self.curr_node
self.parent = self.curr_node
self.curr_node = self.curr_node.right
while self.curr_node.left: # 1번 파트
self.parent = self.curr_node
self.curr_node = self.curr_node.left
# 이렇게 하면 오른쪽 자식 중에 가장 작은 값이 self.curr_node
change.data = self.curr_node.data # 2번 파트
if self.curr_node.right != None: # 3번 파트
self.parent.left = self.curr_node.right
else:
self.parent.left = None
del self.curr_node
return True