자료구조/트리
이진 탐색 트리
아몬드바
2023. 8. 14. 16:57
728x90
정의
딕셔너리, 세트의 추상 자료형을 구현할때 사용
속성
1. 이진 트리이면서 특정 노드의 데이터를 봤을때 왼쪽 부분 트리에 있는 모든 노드는 특정 노드의 데이터보다 작고
오른쪽 부분 트리에 있는 모든 노드는 특정 노드보다 커야한다.
ex) 특정노드가 8 이면 왼쪽에는 8보다 작은 숫자, 오른쪽에는 8보다 큰 숫자
2. 루트 노드뿐만 아니라 모든 노드에 적용되어야 한다.
구현(완전 이진 트리가 아니므로 배열이나 파이썬 리스트로 구현하지 않는다)
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.left_child = None
self.right_child = None
# 편하게 사용하기 위해 이진 탐색 트리를 클래스로 만든다. 15 ~ 23줄
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
# 비어 있는 이진 탐색 트리 생성
bst = BinarySearchTree()
# 노드 인스턴스 생성
# node_0 = Node(5)
# node_1= Node(3)
# node_2= Node(7)
# node_0.left_child = node_1
# node_0.right_child = node_2
# node_1.parent = node_0
# node_2.parent = node_0
이진 탐색 트리 삽입(* 시간 복잡도 : 트리의 높이는 h), O(h)
1. 새로운 노드 생성 - O(1)
2. root 노드부터 비교하면서 저장할 위치 찾음 - O(h)
3. 찾은 위치에 새롭게 만든 노드 연결 - O(1)
구현
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.right_child = None
self.left_child = None
def print_inorder(node):
"""주어진 노드를 in-order로 출력해주는 함수"""
if node is not None:
print_inorder(node.left_child)
print(node.data)
print_inorder(node.right_child)
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
def insert(self, data):
"""이진 탐색 트리 삽입 메소드"""
new_node = Node(data) # 삽입할 데이터를 갖는 노드 생성
# 트리가 비었으면 새로운 노드를 root 노드로 만든다
if self.root is None:
self.root = new_node
return
# 코드를 쓰세요
temp = self.root # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다
# 원하는 위치를 찾아간다
while temp is not None:
if data > temp.data: # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
# 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
if temp.right_child is None:
new_node.parent = temp
temp.right_child = new_node
return
# 오른쪽 자식이 있으면 오른쪽 자식으로 간다
else:
temp = temp.right_child
else: # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
# 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
if temp.left_child is None:
new_node.parent = temp
temp.left_child = new_node
return
# 왼쪽 자식이 있다면 왼쪽 자식으로 간다
else:
temp = temp.left_child
def print_sorted_tree(self):
"""이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
print_inorder(self.root) # root 노드를 in-order로 출력한다
# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()
# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)
# 이진 탐색 트리 출력
bst.print_sorted_tree()
이진 탐색 트리 탐색 - O(h)
1. 주어진 노드의 데이터와 탐색하려는 데이터 비교
2. 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로 간다.
3. 탐색하려는 데이터가 더 작으면 노드의 왼쪽 자식으로 간다.
4. 탐색하려는 노드를 찾으면 리턴한다.
구현
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.right_child = None
self.left_child = None
def print_inorder(node):
"""주어진 노드를 in-order로 출력해주는 함수"""
if node is not None:
print_inorder(node.left_child)
print(node.data)
print_inorder(node.right_child)
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
def search(self, data):
"""이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
# 코드를 쓰세요
temp = self.root
while temp is not None:
if data == temp.data:
return temp
if data > temp.data:
temp = temp.right_child
else:
temp = temp.left_child
return None
def insert(self, data):
"""이진 탐색 트리 삽입 메소드"""
new_node = Node(data) # 삽입할 데이터를 갖는 노드 생성
# 트리가 비었으면 새로운 노드를 root 노드로 만든다
if self.root is None:
self.root = new_node
return
# 여기에 코드를 작성하세요
temp = self.root # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다
# 원하는 위치를 찾아간다
while temp is not None:
if data > temp.data: # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
# 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
if temp.right_child is None:
new_node.parent = temp
temp.right_child = new_node
return
# 오른쪽 자식이 있으면 오른쪽 자식으로 간다
else:
temp = temp.right_child
else: # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
# 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
if temp.left_child is None:
new_node.parent = temp
temp.left_child = new_node
return
# 왼쪽 자식이 있다면 왼쪽 자식으로 간다
else:
temp = temp.left_child
def print_sorted_tree(self):
"""이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
print_inorder(self.root) # root 노드를 in-order로 출력한다
# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()
# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)
# 노드 탐색과 출력
print(bst.search(7).data)
print(bst.search(19).data)
print(bst.search(2).data)
print(bst.search(20))
정적메소드를 이용한 node를 뿌리로 갖는 부분 트리 안에서 가장 작은 노드를 리턴
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.right_child = None
self.left_child = None
def print_inorder(node):
"""주어진 노드를 in-order로 출력해주는 함수"""
if node is not None:
print_inorder(node.left_child)
print(node.data)
print_inorder(node.right_child)
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
@staticmethod
def find_min(node):
"""(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
temp = node # 도우미 변수. 파라미터 node로 초기화
# temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
while temp.left_child is not None:
temp = temp.left_child
return temp
def search(self, data):
"""이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
temp = self.root # 탐색용 변수, root 노드로 초기화
# 원하는 데이터를 갖는 노드를 찾을 때까지 돈다
while temp is not None:
# 원하는 데이터를 갖는 노드를 찾으면 리턴
if data == temp.data:
return temp
# 원하는 데이터가 노드의 데이터보다 크면 오른쪽 자식 노드로 간다
if data > temp.data:
temp = temp.right_child
# 원하는 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 간다
else:
temp = temp.left_child
return None # 원하는 데이터가 트리에 없으면 None 리턴
def insert(self, data):
"""이진 탐색 트리 삽입 메소드"""
new_node = Node(data) # 삽입할 데이터를 갖는 노드 생성
# 트리가 비었으면 새로운 노드를 root 노드로 만든다
if self.root is None:
self.root = new_node
return
temp = self.root # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다
# 원하는 위치를 찾아간다
while temp is not None:
if data > temp.data: # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
# 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
if temp.right_child is None:
new_node.parent = temp
temp.right_child = new_node
return
# 오른쪽 자식이 있으면 오른쪽 자식으로 간다
else:
temp = temp.right_child
else: # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
# 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
if temp.left_child is None:
new_node.parent = temp
temp.left_child = new_node
return
# 왼쪽 자식이 있다면 왼쪽 자식으로 간다
else:
temp = temp.left_child
def print_sorted_tree(self):
"""이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
print_inorder(self.root) # root 노드를 in-order로 출력한다
# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()
# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)
print(bst.find_min(bst.root).data) # 전체 이진 탐색 트리에서 가장 작은 노드
print(bst.find_min(bst.root.right_child).data) # root 노드의 오른쪽 부분 트리에서 가장 작은 노드
이진 탐색 트리 삭제
case 1. 삭제하려는 데이터가 leaf 노드의 데이터일 때
- 리프노드의 부모자식에 대해 왼쪽 or 오른쪽 자식의 레퍼런스를 None 으로 지정
case 2. 삭제하려는 데이터 노드가 하나의 자식 노드만 있을 때
- 자식 노드가 부모 노드의 자리를 차지하면 된다.
case 3. 삭제하려는 데이터의 노드가 두 개의 자식이 있을때
- 지우려는 노드의 오른쪽으로 가서 그 노드의 작은 데이터 노드를 찾는다.(successor를 find_min() 메소드를 활용하여
가져옴)
- 삭제하려는 노드 데이터에 successor 의 데이터를 저장한다.
- successor 노드를 삭제한다.
구현(case 1)
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.right_child = None
self.left_child = None
def print_inorder(node):
"""주어진 노드를 in-order로 출력해주는 함수"""
if node is not None:
print_inorder(node.left_child)
print(node.data)
print_inorder(node.right_child)
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
def delete(self, data):
"""이진 탐색 트리 삭제 메소드"""
node_to_delete = self.search(data) # 삭제할 노드를 가지고 온다
parent_node = node_to_delete.parent # 삭제할 노드의 부모 노드
# 경우 1: 지우려는 노드가 leaf 노드일 때
if node_to_delete.left_child is None and node_to_delete.right_child is None:
if self.root is node_to_delete:
self.root = None
else: # 일반적인 경우
if node_to_delete is parent_node.left_child:
parent_node.left_child = None
else:
parent_node.right_child = None
@staticmethod
def find_min(node):
"""(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
temp = node # 탐색용 변수, 파라미터 node로 초기화
# temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
while temp.left_child is not None:
temp = temp.left_child
return temp
def search(self, data):
"""이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
temp = self.root # 탐색용 변수, root 노드로 초기화
# 원하는 데이터를 갖는 노드를 찾을 때까지 돈다
while temp is not None:
# 원하는 데이터를 갖는 노드를 찾으면 리턴
if data == temp.data:
return temp
# 원하는 데이터가 노드의 데이터보다 크면 오른쪽 자식 노드로 간다
if data > temp.data:
temp = temp.right_child
# 원하는 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 간다
else:
temp = temp.left_child
return None # 원하는 데이터가 트리에 없으면 None 리턴
def insert(self, data):
"""이진 탐색 트리 삽입 메소드"""
new_node = Node(data) # 삽입할 데이터를 갖는 노드 생성
# 트리가 비었으면 새로운 노드를 root 노드로 만든다
if self.root is None:
self.root = new_node
return
# 여기에 코드를 작성하세요
temp = self.root # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다
# 원하는 위치를 찾아간다
while temp is not None:
if data > temp.data: # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
# 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
if temp.right_child is None:
new_node.parent = temp
temp.right_child = new_node
return
# 오른쪽 자식이 있으면 오른쪽 자식으로 간다
else:
temp = temp.right_child
else: # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
# 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
if temp.left_child is None:
new_node.parent = temp
temp.left_child = new_node
return
# 왼쪽 자식이 있다면 왼쪽 자식으로 간다
else:
temp = temp.left_child
def print_sorted_tree(self):
"""이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
print_inorder(self.root) # root 노드를 in-order로 출력한다
# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()
# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)
# leaf 노드 삭제
bst.delete(2)
bst.delete(4)
bst.print_sorted_tree()
구현(case 2)
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.right_child = None
self.left_child = None
def print_inorder(node):
"""주어진 노드를 in-order로 출력해주는 함수"""
if node is not None:
print_inorder(node.left_child)
print(node.data)
print_inorder(node.right_child)
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
def delete(self, data):
"""이진 탐색 트리 삭제 메소드"""
node_to_delete = self.search(data) # 삭제할 노드를 가지고 온다
parent_node = node_to_delete.parent # 삭제할 노드의 부모 노드
# 경우 1: 지우려는 노드가 leaf 노드일 때
if node_to_delete.left_child is None and node_to_delete.right_child is None:
if self.root is node_to_delete:
self.root = None
else: # 일반적인 경우
if node_to_delete is parent_node.left_child:
parent_node.left_child = None
else:
parent_node.right_child = None
# 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
elif node_to_delete.left_child is None: # 지우려는 노드가 오른쪽 자식만 있을 때:
# 지우려는 노드가 root 노드일 때
if node_to_delete is self.root:
self.root = node_to_delete.right_child
self.root.parent = None
# 지우려는 노드가 부모의 왼쪽 자식일 때
elif node_to_delete is parent_node.left_child:
parent_node.left_child = node_to_delete.right_child
node_to_delete.right_child.parent = parent_node
# 지우려는 노드가 부모의 오른쪽 자식일 때
else:
parent_node.right_child = node_to_delete.right_child
node_to_delete.right_child.parent = parent_node
elif node_to_delete.right_child is None: # 지우려는 노드가 왼쪽 자식만 있을 때:
# 지우려는 노드가 root 노드일 때
if node_to_delete is self.root:
self.root = node_to_delete.left_child
self.root.parent = None
# 지우려는 노드가 부모의 왼쪽 자식일 때
elif node_to_delete is parent_node.left_child:
parent_node.left_child = node_to_delete.left_child
node_to_delete.left_child.parent = parent_node
# 지우려는 노드가 부모의 오른쪽 자식일 때
else:
parent_node.right_child = node_to_delete.left_child
node_to_delete.left_child.parent = parent_node
@staticmethod
def find_min(node):
"""(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
# 여기에 코드를 작성하세요
temp = node # 탐색 변수. 파라미터 node로 초기화
# temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
while temp.left_child is not None:
temp = temp.left_child
return temp
def search(self, data):
"""이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
temp = self.root # 탐색 변수. root 노드로 초기화
# 원하는 데이터를 갖는 노드를 찾을 때까지 돈다
while temp is not None:
# 원하는 데이터를 갖는 노드를 찾으면 리턴
if data == temp.data:
return temp
# 원하는 데이터가 노드의 데이터보다 크면 오른쪽 자식 노드로 간다
if data > temp.data:
temp = temp.right_child
# 원하는 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 간다
else:
temp = temp.left_child
return None # 원하는 데이터가 트리에 없으면 None 리턴
def insert(self, data):
"""이진 탐색 트리 삽입 메소드"""
new_node = Node(data) # 삽입할 데이터를 갖는 노드 생성
# 트리가 비었으면 새로운 노드를 root 노드로 만든다
if self.root is None:
self.root = new_node
return
# 여기에 코드를 작성하세요
temp = self.root # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다
# 원하는 위치를 찾아간다
while temp is not None:
if data > temp.data: # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
# 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
if temp.right_child is None:
new_node.parent = temp
temp.right_child = new_node
return
# 오른쪽 자식이 있으면 오른쪽 자식으로 간다
else:
temp = temp.right_child
else: # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
# 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
if temp.left_child is None:
new_node.parent = temp
temp.left_child = new_node
return
# 왼쪽 자식이 있다면 왼쪽 자식으로 간다
else:
temp = temp.left_child
def print_sorted_tree(self):
"""이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
print_inorder(self.root) # root 노드를 in-order로 출력한다
# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()
# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)
# 자식이 하나만 있는 노드 삭제
bst.delete(5)
bst.delete(9)
bst.print_sorted_tree()
구현(case 3)
class Node:
"""이진 탐색 트리 노드 클래스"""
def __init__(self, data):
self.data = data
self.parent = None
self.right_child = None
self.left_child = None
def print_inorder(node):
"""주어진 노드를 in-order로 출력해주는 함수"""
if node is not None:
print_inorder(node.left_child)
print(node.data)
print_inorder(node.right_child)
class BinarySearchTree:
"""이진 탐색 트리 클래스"""
def __init__(self):
self.root = None
def delete(self, data):
"""이진 탐색 트리 삭제 메소드"""
node_to_delete = self.search(data) # 삭제할 노드를 가지고 온다
parent_node = node_to_delete.parent # 삭제할 노드의 부모 노드
# 경우 1: 지우려는 노드가 leaf 노드일 때
if node_to_delete.left_child is None and node_to_delete.right_child is None:
if self.root is node_to_delete:
self.root = None
else: # 일반적인 경우
if node_to_delete is parent_node.left_child:
parent_node.left_child = None
else:
parent_node.right_child = None
# 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
elif node_to_delete.left_child is None: # 지우려는 노드가 오른쪽 자식만 있을 때:
# 지우려는 노드가 root 노드일 때
if node_to_delete is self.root:
self.root = node_to_delete.right_child
self.root.parent = None
# 지우려는 노드가 부모의 왼쪽 자식일 때
elif node_to_delete is parent_node.left_child:
parent_node.left_child = node_to_delete.right_child
node_to_delete.right_child.parent = parent_node
# 지우려는 노드가 부모의 오른쪽 자식일 때
else:
parent_node.right_child = node_to_delete.right_child
node_to_delete.right_child.parent = parent_node
elif node_to_delete.right_child is None: # 지우려는 노드가 왼쪽 자식만 있을 때:
# 지우려는 노드가 root 노드일 때
if node_to_delete is self.root:
self.root = node_to_delete.left_child
self.root.parent = None
# 지우려는 노드가 부모의 왼쪽 자식일 때
elif node_to_delete is parent_node.left_child:
parent_node.left_child = node_to_delete.left_child
node_to_delete.left_child.parent = parent_node
# 지우려는 노드가 부모의 오른쪽 자식일 때
else:
parent_node.right_child = node_to_delete.left_child
node_to_delete.left_child.parent = parent_node
# 경우 3: 지우려는 노드가 2개의 자식이 있을 때
else:
successor = self.find_min(node_to_delete.right_child) # 삭제하려는 노드의 successor 노드 받아오기
node_to_delete.data = successor.data # 삭제하려는 노드의 데이터에 successor의 데이터 저장
# successor 노드 트리에서 삭제
if successor is successor.parent.left_child: # successor 노드가 오른쪽 자식일 때
successor.parent.left_child = successor.right_child
else: # successor 노드가 왼쪽 자식일 때
successor.parent.right_child = successor.right_child
if successor.right_child is not None: # successor 노드가 오른쪽 자식이 있을 떄
successor.right_child.parent = successor.parent
# else:
# min_node = self.find_min(node_to_delete.right_child)
# the_data = min_node.data
# self.delete(the_data)
# node_to_delete.data = the_data
@staticmethod
def find_min(node):
"""(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
# 여기에 코드를 작성하세요
temp = node # 탐색 변수. 파라미터 node로 초기화
# temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
while temp.left_child is not None:
temp = temp.left_child
return temp
def search(self, data):
"""이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
temp = self.root # 탐색 변수. root 노드로 초기화
# 원하는 데이터를 갖는 노드를 찾을 때까지 돈다
while temp is not None:
# 원하는 데이터를 갖는 노드를 찾으면 리턴
if data == temp.data:
return temp
# 원하는 데이터가 노드의 데이터보다 크면 오른쪽 자식 노드로 간다
if data > temp.data:
temp = temp.right_child
# 원하는 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 간다
else:
temp = temp.left_child
return None # 원하는 데이터가 트리에 없으면 None 리턴
def insert(self, data):
"""이진 탐색 트리 삽입 메소드"""
new_node = Node(data) # 삽입할 데이터를 갖는 노드 생성
# 트리가 비었으면 새로운 노드를 root 노드로 만든다
if self.root is None:
self.root = new_node
return
# 여기에 코드를 작성하세요
temp = self.root # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다
# 원하는 위치를 찾아간다
while temp is not None:
if data > temp.data: # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
# 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
if temp.right_child is None:
new_node.parent = temp
temp.right_child = new_node
return
# 오른쪽 자식이 있으면 오른쪽 자식으로 간다
else:
temp = temp.right_child
else: # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
# 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
if temp.left_child is None:
new_node.parent = temp
temp.left_child = new_node
return
# 왼쪽 자식이 있다면 왼쪽 자식으로 간다
else:
temp = temp.left_child
def print_sorted_tree(self):
"""이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
print_inorder(self.root) # root 노드를 in-order로 출력한다
# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()
# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)
# 자식이 두 개 다 있는 노드 삭제
bst.delete(7)
bst.delete(11)
bst.print_sorted_tree()728x90