[자료구조] 트리
1. 트리 (Tree) 구조
- 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
- 실제로 어디에 많이 사용되나?
- 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
2. 알아둘 용어
- Node
- 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) - Root Node
- 트리 맨 위에 있는 노드 - Level
- 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 - Parent Node
- 어떤 노드의 다음 레벨에 연결된 노드 - Child Node
- 어떤 노드의 상위 레벨에 연결된 노드 - Leaf Node (Terminal Node)
- Child Node가 하나도 없는 노드 - Sibling (Brother Node)
- 동일한 Parent Node를 가진 노드 - Depth
- 트리에서 Node가 가질 수 있는 최대 Level
3. 이진 트리와 이진 탐색 트리 (Binary Search Tree)
- 이진 트리: 노드의 최대 Branch가 2인 트리
- 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
- 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!
4. 자료 구조 이진 탐색 트리의 장점과 주요 용도
- 주요 용도: 데이터 검색(탐색)
- 장점: 탐색 속도를 개선할 수 있음
단점은 이진 탐색 트리 알고리즘 이해 후에 살펴보기로 함
이진트리와 정렬된 배열간의 탐색 비교
위의 두 사진을 비교해보자.
이진트리에서 27을 찾으려면, step 0 ~ step 3 를 거치면 찾을 수 있다.
반면, 정렬된 배열에서 27을 찾기 위해서는, step 0 ~ step 10 을 거쳐야 찾을 수 있다.
이처럼 데이터 검색 시에 이진트리를 사용하면 혁신적으로 시간을 줄일 수 있다👍
따라서 검색이 필요한 데이터를 저장할 때에는 이진트리를 많이 사용한다.
5. 프로그래밍 연습
1) 노드 삽입
테스트
2) 노드 탐색
이전에 만든 NodeMgmt 클래스 안에 추가한다.
테스트
해당 이진 탐색 트리 안에 2는 들어있으니 True를 반환하고,
5는 없으니 False를 반환하는 것을 확인할 수 있다.
3) 노드 삭제
매우 복잡하니 경우를 나누어서 이해하는 것이 좋다.
Leaf Node 삭제 (child가 0개인 노드 삭제)
- Leaf Node: Child Node 가 없는 Node
- 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
child가 1개인 노드 삭제
- 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
child가 2개인 노드 삭제
삭제할 노드 자리로 올릴 노드를 선택하는 2가지 전략 🌟
아래 두 가지 전략 중 하나를 선택한다.
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 선택한다.
- 삭제할 노드의 오른쪽 자식의 왼쪽을 따라가며 제일 마지막 노드를 선택한다. - 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 선택한다.
- 삭제할 노드의 왼쪽 자식의 오른쪽을 따라가며 제일 마지막 노드를 선택한다.
위 전략으로 노드를 선택했으면, 삭제할 노드의 parent 노드가 선택한 노드를 가리키도록 한다.
(= 선택한 노드를 삭제할 노드 자리로 올린다.)
둘 중, 첫 번째 전략을 더 자세히 보자
- 삭제할 노드의 오른쪽 자식 선택 (삭제할 노드는
currentNode) - 오른쪽 자식의 왼쪽을 따라가며 제일 마지막 노드 선택 (이후부터 이때 선택된 노드를
changeNode로 명명) - 삭제할 노드의 parent의 left를
changeNode로 변경 changeNode의 left를 삭제할 노드의 left로 변경changeNode의 right를 삭제할 노드의 right로 변경changeNode는 (당연히) left는 없을텐데, right는 있을 수 있음- 만약 right를 가지고 있었다면,
changeNode의 parent의 left에 그 right 대입 - right를 가지고 있지 않다면,
changeNode의 parent의 left에 None 대입
위에서 left는 왼쪽 자식 노드를 의미하며,
right는 오른쪽 자식 노드를 의미한다.
또한 parent는 부모 노드를 의미한다.
구현
이전에 만든 NodeMgmt 클래스 안에 추가한다.
- currentNode: 삭제할 노드
- changeNode: (삭제할 노드 자리로 올릴) 선택된 노드
- changeNodeParent: 선택된 노드의 부모 노드
-
삭제할 노드가 있는지 탐색
-
삭제할 노드의 자식이 0개인 경우
-
삭제할 노드의 자식이 1개인 경우
-
삭제할 노드의 자식이 2개인 경우
- 필기
- 전체 코드
# 노드 클래스 만들기
class Node:
def __init__(self,value): # 자식 노드가 없을 수도 있기 때문에 노드 생성시부터 left, right 주소를 설정하지 않아도 됨
self.value = value
self.left = None
self.right = None
# 이진 탐색 트리에 데이터 넣기
class NodeMgmt:
def __init__(self,head):
self.head = head # head는 루트노드
# 새로운 노드 삽입
def insert(self, value): # value는 새로 집어넣을 값
self.currentNode = self.head # 순회의 시작은 루트노드부터
while True:
if value < self.currentNode.value: # value가 currentNode보다 작다면
if self.currentNode.left != None: # currentNode의 왼쪽에 이미 값이 있다면
self.currentNode = self.currentNode.left # 비교할(순회할) 대상을 바꾸기
else: # 값이 없다면
self.currentNode.left = Node(value) # 새로운 노드 연결
break
else: # value가 currentNode보다 크거나 같다면
if self.currentNode.right != None: # currentNode의 오른쪽에 이미 값이 있다면
self.currentNode = self.currentNode.right # 비교할(순회할) 대상을 바꾸기
else: # 값이 없다면
self.currentNode.right = Node(value) # 새로운 노드 연결
break
# 이진 탐색 트리 탐색 (특정 데이터를 저장하고 있는 노드가 있는지 없는지 확인)
def search(self,value):
self.currentNode = self.head # 순회의 시작은 루트노드부터
while self.currentNode: # self.currentNode가 있는 동안
if self.currentNode.value == value:
return True
# 이제부터 순회
elif value < self.currentNode.value:
self.currentNode = self.currentNode.left # 비교할 대상을 왼쪽 노드로 바꾸기
else:
self.currentNode = self.currentNode.right # 비교할 대상을 오른쪽 노드로 바꾸기
return False # 이진 탐색 트리에 해당 데이터를 가진 노드가 없음
def delete(self,value): # 값이 value인 노드 삭제
# 삭제할 노드가 있는지 탐색
isExisted = False # isExisted가 True이면 삭제할 노드가 트리 안에 있는 것
self.currentNode = self.head
self.parent = self.head
while self.currentNode:
if self.currentNode.value == value:
isExised = True
break
elif value < self.currentNode.value:
self.parent = self.currentNode # parent 노드도 변경!
self.currentNode = self.currentNode.left
else :
self.parent = self.currentNode
self.currentNode = self.currentNode.right
if isExisted == False:
return False # 삭제 실패
# 이후부터 case를 나눠서 삭제 (self.currentNode가 삭제할 노드)
# case 1️⃣ : 삭제할 노드가 leaf node 인 경우 (자식이 0개)
if self.currentNode.left == None and self.currentNode.right == None:
# 삭제할 노드가 부모 노드의 왼쪽 자식이었는지 오른쪽 자식이었는지
if value < self.parent.value:
self.parent.left = None
else:
self.parent.right = None
del self.currentNode # 노드 삭제 (del: 객체 삭제)
# case 2️⃣: 삭제할 노드의 child가 1개인 경우
# 2-1: 삭제할 노드의 child가 left child인 경우
if self.currentNode.left != None and self.currentNode.right == None:
# 삭제할 노드가 부모 노드의 왼쪽 자식이었는지 오른쪽 자식이었는지
if value < self.parent.value: # 2-1-1: 왼쪽 자식이었던 경우
self.parent.left = self.currentNode.left # 부모의 left와 삭제할 노드의 left 연결
else: # 2-1-2: 오른쪽 자식이었던 경우
self.parent.right = self.currentNode.left # 부모의 right와 삭제할 노드의 left 연결
# 2-2: 삭제할 노드의 child가 right child인 경우
elif self.currentNode.left == None and self.currentNode.right != None:
# 삭제할 노드가 부모 노드의 왼쪽 자식이었는지 오른쪽 자식이었는지
if value < self.parent.value: # 2-2-1: 왼쪽 자식이었던 경우
self.parent.left = self.currentNode.right # 부모의 left와 삭제할 노드의 right 연결
else: # 2-2-2: 오른쪽 자식이었던 경우
self.parent.right = self.currentNode.right # 부모의 right와 삭제할 노드의 right 연결
# case 3️⃣: 삭제할 노드의 child가 2개인 경우
if self.currentNode.left != None and self.currentNode.right != None:
# 삭제할 노드가 부모 노드의 왼쪽 자식이었는지 오른쪽 자식이었는지
if value < self.parent.value: # 3-1: 왼쪽 자식이었던 경우
# 전략: 삭제할 노드(currentNode)의 오른쪽 자식의 왼쪽 끝을 따라가서 선택
self.changeNodeParent = self.currentNode.right # 삭제할 노드의 오른쪽 자식을 parent에 담아두고
# 이제부터 왼쪽 끝을 따라가기 (순회)
self.changeNode = self.currentNode.right
while self.changeNode.left:
self.changeNode.parent = self.changeNode
self.changeNode = self.changeNode.left
# 3-1-1: 선택된 노드의 right child가 존재한다면
if self.changeNode.right:
self.changeNode.parent.left = self.changeNode.right # 그 right를 parent의 left에 붙이기
else: # 3-1-2: 존재하지 않는다면
self.changeNode.parent.left = None # 선택된 노드(changeNode)를 삭제할 노드 자리로 올려야 하니까 parent와의 연결 끊기
# 이제 선택된 노드를 위로 올리기
self.parent.left = self.changeNode # 삭제할 노드가 parent의 left child 였기 때문에 선택된 노드를 left에 붙인다
self.changeNode.left = self.currentNode.left # 삭제할 노드의 양쪽 자식을 선택된 노드 밑에 붙여주기
self.changeNode.right = self.currentNode.right # 삭제할 노드의 양쪽 자식을 선택된 노드 밑에 붙여주기
else: # 3-2: 오른쪽 자식이었던 경우
# 전략: 삭제할 노드(currentNode)의 오른쪽 자식의 왼쪽 끝을 따라가서 선택
self.changeNodeParent = self.currentNode.right
# 이제부터 왼쪽 끝을 따라가기 (순회)
self.changeNode = self.currentNode.right
while self.changeNode.left:
self.changeNode.parent = self.changeNode
self.changeNode = self.changeNode.left
# 3-2-1: 선택된 노드의 right child가 존재한다면
if self.changeNode.right:
self.changeNode.parent.left = self.changeNode.right
else: # 3-2-2: 존재하지 않는다면
self.changeNode.parent.left = None
# 이제 선택된 노드를 위로 올리기
self.parent.right = self.changeNode # 삭제할 노드가 parent의 right child 였기 때문에 선택된 노드를 right에 붙인다 (삭제할 노드가 부모노드의 왼쪽 자식이었을 때와 여기만 다름!!🌟)
self.changeNode.left = self.currentNode.left
self.changeNode.right = self.currentNode.right
return True # 삭제 성공
전체 테스트
6. 이진 탐색 트리의 시간 복잡도와 단점
시간 복잡도 (탐색시)
- depth (트리의 높이) 를 h라고 표기한다면, O(h)
- n개의 노드를 가진다면, $h = log_{2}{n}$ 에 가까우므로, 시간 복잡도는 $O(log{n})$
- 참고: 빅오 표기법에서 $log{n}$ 에서의 log의 밑은 10이 아니라, 2이다.
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함
이진 탐색 트리 단점
- 평균 시간 복잡도는 $O(log{n})$ 이지만, 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
- 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( $O(n)$ )
💛 개인 공부 기록용 블로그입니다. 👻