트리 구조
- 루트 노드(A)를 시작으로 줄기를 뻗어 나가듯 원소를 추가해 나가는 비선형 구조
- 계층 구조로 방향이 있다.
루트노드 : 가장 꼭대기의 노드
트리는 루트노드가 1개이다.
자식 노드 : 노드의 바로 하위에 인접한 노드 (간선으로 연결된)
부모 노드 : 노드의 바로 상위에 인접한 노드
모든 자식의 부모는 단 하나이다.
자손 노드 : 노드로부터 단말노드까지 하위로 이어지는 모든 노드의 집합
조상 노드 : 노드로부터 루트 노드까지 상위로 이어지는 모든 노드의 집합
단말노드(leaf node, 잎사귀 노드) : 자식이 없는 노드 (I, J, K, L, G, M, N)
서브 트리 : 자식과의 간선을 끊었을 때 생길 하위트리
자식노드의 개수와 서브트리의 개수는 동일하다.
차수(degree) : 노드의 하위 간선의 개수 ( 자식의 개수, 서브트리의 개수)
트리 전체의 차수는 노드 중 최대 차수로 표현한다.
깊이, 레벨(depth, level) : 루트에서 어떤 노드까지의 경로 길이
루트노드를 레벨 0으로 하고 아래로 하나씩 늘어난다. 루트노드를 레벨 1로 보기도 한다.
높이 (height) :트리의 깊이 중 제일 큰 깊이
이진탐색트리(BST : Binary Search Tree)
트리의 차수가 2인 트리, 모든 노드의 자식이 최대 2개인 트리
- 완전 이진 트리 : 끝부분 (마지막레벨)을 제외하고 모든 노드가 채워진 이진트리
- 포화 이진 트리 : 모든 단말 노드의 깊이가 같은 완전이진트리
- 균형 이진 트리 : 좌우의 높이차가 같거나 최대 1인 트리
1. 이진탐색트리의 삽입
- 루트부터 삽입을 시작
- 부모 노드보다 작을 경우 왼쪽, 클 경우 오른쪽에 추가
- 중복된 원소는 삽입하지 않음
단순구현방법으로 이진탐색트리를 구현해본다.
from mimetypes import init
class Node: #노드 생성
def __init__(self,value):
self.value=value
self.right = None
self.left = None
class Tree: #이진탐색트리 노드삽입
def __init__(self,root):
self.root=root #루트노드
def insert(self,value):
self.current_node = self.root #현재노드
while True:
if value < self.current_node.value:
if self.current_node.left !=None:
self.current_node = self.current_node.left
else:
self.current_node.left=Node(value)
break
else:
if self.current_node.right !=None:
self.current_node=self.current_node.right
else:
self.current_node.right = Node(value)
break
값이 현재노드의 값보다 작으면 왼쪽자식을 확인한다.
왼쪽자식의 값이 있으면 왼쪽자식을 현재노드로 하여, 반복문을 다시 돌린다.
왼쪽자식의 값이 없으면 그 값을 왼쪽자식에 넣는다.
값이 현재노드보다 크면 오른쪽자식을 확인한다.
오른쪽자식의 값이 있으면 오른쪽자식을 현재노드로 하여, 반복문을 돌린다.
오른쪽자식의 값이 없으면 그 값을 오른쪽 자식에 넣는다.
2. 이진탐색트리 조회
def search(self,value): #노드에 입력한 값이 있으면 True, 없으면 False
self.current_node=self.root
while self.current_node:
if self.current_node.value==value:
return True
elif value < self.current_node.value:
self.current_node = self.current_node.left
else:
self.current_node = self.current_node.right
return False
해당 트리구조에 입력한 값이 존재하면 True, 존재하지 않으면 False를 출력하도록 하는 메서드이다.
찾는 값이 현재노드의 값보다 작으면 현재노드의 왼쪽자식을 현재노드로 변경하여 반복문을 돌리고,
찾는 값이 현재노드의 값보다 크면 현재노드의 오른쪽 자식을 현재노드로 변경하여 반복문을 돌린다.
3. 이진탐색트리 삭제
def delete(self,value):
self.current_node = self.root
self.parent = self.root
if self.search(self,value) == False:
return False
#1. 삭제할 노드가 leaf node
if self.current_node.left==None and self.current_node.right==None:
if value<self.parent.value:
self.parent.left=None
else:
self.parent.right=None
#2. 삭제할 노드가 왼쪽자식노드만 가지고 있음
elif self.current_node.left!=None and self.current_node.right ==None:
if value < self.parent.value:
self.parent.left=self.current_node.left
else:
self.parent.right = self.current_node.left
#3. 오른쪽자식노드만 가지고 있음
elif self.current_node.left == None and self.current_node.right != None:
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
#4. 자식 노드를 두 개 가지고 있을 때
if self.current_node.left != None and self.current_node.right != None:
self.change_node = self.current_node.right
self.change_node_parent = self.current_node.right
while self.change_node.left != None:
self.change_node_parent = self.change_node
self.change_node = self.change_node.left
if self.change_node.right != None:
self.change_node_parent.left = self.change_node.right
else:
self.change_node_parent.left = None
if value < self.parent.value:
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.current_node.left
else:
self.parent.right = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
return True
노드 제거 함수는 위와 같이 작성할 수 있다.
root = Node(3)
bst = BST(root)
bst.insert(1)
bst.insert(3)
bst.insert(7)
print(bst.search(1)) # True
print(bst.search(7)) # True
print(bst.search(4)) # False
print(bst.delete(0)) # False
print(bst.delete(7)) # True
print(bst.search(7)) # False
이진탐색트리가 잘 구현된 것을 확인하였다.
4. 재귀로 이진탐색트리 생성, 조회, 삭제 구현
# 노드 생성과 삽입
class Node:
def __init__(self,data):
self.left = None
self.right = None
self.data = data
class BinarySearchTree(Node):
def insert(self, data):
self.root = self._insert_value(self.root, data)
return self.root is not None
def _insert_value(self, node, data):
if node is None:
node = Node(data)
else:
if data <= node.data:
node.left = self._insert_value(node.left, data)
else:
node.right = self._insert_value(node.right, data)
return node
# 노드 탐색
def find(self, key):
return self._find_value(self.root, key)
def _find_value(self, root, key):
if root is None or root.data == key:
return root is not None
elif key < root.data:
return self._find_value(root.left, key)
else:
return self._find_value(root.right, key)
def delete(self, key):
self.root, deleted = self._delete_value(self.root, key)
return deleted
def _delete_value(self, node, key):
if node is None:
return node, False
deleted = False
# 해당 노드가 삭제할 노드일 경우
if key == node.data:
deleted = True
# 삭제할 노드가 자식이 두개일 경우
if node.left and node.right:
# 오른쪽 서브 트리에서 가장 왼쪽에 있는 노드를 찾고 교체
parent, child = node, node.right
while child.left is not None:
parent, child = child, child.left
child.left = node.left
if parent != node:
parent.left = child.right
child.right = node.right
node = child
# 자식 노드가 하나일 경우 해당 노드와 교체
elif node.left or node.right:
node = node.left or node.right
# 자식 노드가 없을 경우 그냥 삭제
else:
node = None
elif key < node.data:
node.left, deleted = self._delete_value(node.left, key)
else:
node.right, deleted = self._delete_value(node.right, key)
return node, deleted
'Language > Python' 카테고리의 다른 글
파이썬 객체지향 - 추상화, 상속, 다형성, 캡슐화 (0) | 2022.07.28 |
---|---|
파이썬 - 클래스변수, 인스턴스변수, 클래스메서드, 인스턴스메서드, 스태틱메서드 (0) | 2022.07.28 |
파이썬 immutable / mutable (0) | 2022.07.27 |
딕셔너리 메서드 - get, setdefault, pop, update (0) | 2022.07.26 |
셋(set) 메서드 - add, update, remove, discard (0) | 2022.07.26 |