데이터를 다룬다면 반드시 이해해야 하는 이진탐색트리 ! https://www.kmib.co.kr/article/view.asp?arcid=0924162199
1. 트리(Tree) 기본 개념 : 계층 구조를 표현하는 용도. ex) 데이터 베이스, 인공지능 의사 결정 트리
2. 구성요소: -> 루트 노드(root node, 가장위의 값), 노드(node, 트리 구성 각 요소), 간선(Edge, 노드를 연결하는 선)
3. 노드간 관계: -> 부모 노드(parent, 위에 있는)-자식 노드(child, 아래있는) -> 형제 노드(Sibling, 같은 부모), 리프 노드(Leaf, 자식 없는)
2. 이진 트리(Binary Tree) : 노드 하나가 최대 2개의 자식 노드를 가짐 -> 루트 노드 : 배열 인덱스 1번 -> 왼쪽 자식 : 배열 인덱스 = 부모 노드 * 2 (+ 1)* -> 오른 쪽 자식: 배열 인덱스 = 부모 노드 * 2 + 1 (+ 1)* * 루트 노드가 0으로 시작하면 배열 인덱스 규칙에 +1
## 이진 트리 순회 ## 기본 전제 조건 - 현재 노드를 부모 노드로 생각했을 때 1. 현재 노드 부터 방문 후 자식 노드 방문 - 전회 순회(preorder) : 부모 노드 -> 왼쪽 자식 -> 오른쪽 자식 2. 현재 노드 방문 하지 않고 왼쪽 자식부터 방문 - 중위 순회(inorder) : 왼쪽 자식 -> 부모 노드 -> 오른쪽 자식 - 후위 순회(postorder) : 왼쪽 자식 -> 오른쪽 자식 -> 부모 노드
이진 트리 함수 구현: 재귀 호출(함수 내에서 스스로를 실행)을 이용하여 노드 방문
** ret = str(nodes[idx])가 현재 노드를 방문한다는 것.
https://blog.naver.com/occidere/220899936160
def preorder(nodes, idx):
if idx < len(nodes):
ret = str(nodes[idx]) + " " # 현재 노드부터 우선 방문 후 다음 탐색
ret += preorder(nodes, idx * 2 +1)
ret += preorder(nodes, idx * 2 +2)
return ret
else:
return ""
def inorder(nodes, idx):
if idx < len(nodes):
ret = inorder(nodes, idx * 2 + 1) # 왼쪽 자식 노드가 없는 데 까지 내려가서 추가
ret += str(nodes[idx]) + " " # 부모 노드값 추가
ret += inorder(nodes, idx * 2 + 2) # 오른쪽 자식 노드 없는 데 까지 내려가서 추가
return ret
else:
return ""
def postorder(nodes, idx):
if idx < len(nodes):
ret = postorder(nodes, idx*2+1) # 왼쪽 자식
ret += postorder(nodes, idx*2+2) # 오른쪽 자식
ret += str(nodes[idx]) + " " # 부모
return ret
else:
return ""
def solution(nodes):
return [
preorder(nodes,0)[:-1],
inorder(nodes, 0)[:-1],
postorder(nodes, 0)[:-1]
] # [:-1]하여 값의 마지막 공백 제거
nodes = [1,2,3,4,5,6,7]
solution(nodes)
## 이진 탐색 트리 구현 ## 1. 노드 클래스 정의 Class Node - 생성자 : 이진 탐색 트리에서 사용할 노드 생성 및 값 초기화
2. 이진 탐색 트리 클래스 정의 Class BST - 생성자 함수: 루트 노트 초기화 - 새로운 노드 추가 함수: 규칙에 따라 노드 추가(규칙: 루트 노드 있는지, 노드의 값, 좌 우 자식 노드 있는지 등) - 노드 탐색 함수: 노드를 이동하면서 값을 찾음(루트 -> 좌 -> 우)
3. solution 함수 정의 - 클래스 인스턴스 생성, 이진트리 탐색 결과 리턴
## 정답
# 노드 클래스 정의
class Node:
# 노드 클래스 생성자
def __init__(self,key):
self.left = None
self.right = None
self.val = key
# 이진 탐색 트리 클래스
class BST: # Binary Search Tree
# 초기에 아무 노드도 없는 상태
def __init__(self):
self.root = None
# 루트 노드부터 시작해서 이진 탐색 트리 규칙에 맞는 위치에 새 노드 삽입
def insert(self, key):
# 루트 노드가 없는 경우 새로운 노드를 루트 노트로 추가
if not self.root:
self.root = Node(key)
else:
curr = self.root
while True:
# 삽입하려는 값이 현재 노드보다 작은 경우 왼쪽 자식 노드로 이동
if key < curr.val:
if curr.left:
curr = curr.left
else:
# 현재 노드의 왼쪽 자식 노드가 없는 경우 새로운 노드 추가
curr.left = Node(key)
break
else:
# 삽입하려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
if curr.right:
curr = curr.right
else:
# 현재 노드의 오른쪽 자식 노드가 없는 경우 새로운 노드 추가
curr.right = Node(key)
break
# 이진 탐색 규칙에 따라 특정값이 있는 지 확인(루트 노드부터 시작)
def search(self, key):
curr = self.root
# 현재 노드가 존재하고, 찾으려는 값과 현재 노드의 값이 같지 않은 경우 반복
while curr and curr.val != key:
# 찾으려는 값이 현재 노드의 값보다 작은 경우 왼쪽 자식 노드로 이동
if key < curr.val:
curr = curr.left
else:
# 찾으려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
curr = curr.right
return curr
# lst에 있는 데이터를 활용해서 이진 탐색 트리 생성, search_lst 원소 탐색
def solution(lst, search_lst):
bst = BST()
# 리스트의 각 요소를 이용하여 이진 탐색 트리 생성
for key in lst:
bst.insert(key)
result = []
# 검색 리스트의 각 요소를 이진 탐색 트리에서 검색하고, 검색 결과를 리스트에 추가
for search_val in search_lst:
if bst.search(search_val):
result.append(True)
else:
result.append(False)
return result
lst = [5,3,8,4,2,1,7,10]
search_lst = [1,2,5,6]
print(solution(lst,search_lst))
