개요
트리의 구조
- 트리: Node와 Branch를 이용해서 사이클을 이루지 안호록 구성한 데이터 구조
- 트리 중 이진 트리(Binary Tree) 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 자주 사용
용어
- Node: 트리에 데이터를 저장하는 기본 요소 (데이터, 연결된 다른 node에 대한 branch 정보 포함)
- Root node: 트리의 최상위 노드
- Level: Root node를 레벨 0으로 봤을 때 하위 node들의 깊이를 나타냄
- Parent node: 어떤 노드의 하위 레벨에 연결된 노드 (위쪽 노드)
- Child node: 어떤 노드의 상위 레벨에 연결된 노드 (아래쪽 노드)
- Leaf node: Child node가 없는 노드
- Depth: 트리에서 node가 가질 수 있는 최대 level
이진 트리와 이진 탐색 트리의 차이점
- 이진 트리(Binary Tree): 노드의 최대 Branch 개수가 2인 트리
- 이진 탐색 트리(Binary Search Tree): 이진 트리에서 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 같는다는 조건이 추가된 트리
장점
- 빠른 탐색 속도
- 글 하단의 배열과의 비교에서 알 수 있다.
단점
- 위와 같이 한 쪽으로만 node가 추가되는 트리에 링크드 리스트과 같은 탐색 속도를 가진다.
그림으로 보기
1) 이진탐색트리의 예시
2) 자료 탐색시 배열과의 비교
배열에서 13이라는 값을 찾기 위해서는 5번의 탐색이 필요하지만, 이진탐색트리에서는 3회의 값 비교를 통해 찾을 수 있다. 이러한 탐색 속도 차이는 자료구조의 크기가 커질 수록 비례해서 커진다.
3) Node 삭제시의 로직
3-1) Leaf node를 삭제할 경우
- 삭제할 node의 parent node의 branch를 None으로 대체한다.
3-2) Child node가 1개인 node를 삭제할 경우
- 삭제할 node의 parent node가 삭제할 node의 child node를 가리키게 한다.
3-2) Child node가 2개인 node를 삭제할 경우 -> 매우 복잡한 과정을 거친다.
삭제할 node의 오른쪽에 있는 tree에서 가장 작은 값을 가지는 node가 삭제할 node 자리를 대체해야 한다.
- 삭제할 node의 오른쪽 tree에서 가장 작은 값을 가지는 node(= 삭제할 node의 오른쪽 tree에서 계속 왼쪽으로 가면서 왼쪽 branch가 없는 node)를 찾는다. (이 node를 target node라고 부르기로 함)
- 삭제할 node의 parent node가 target node를 가리키게 한다.
- target node가 child node를 가지고 있었다면, target node의 parent node가 target node의 child node를 가리키게 만든다.
- 삭제할 node의 오른쪽 child node를 target node의 오른쪽 child node로 만든다.
- 삭제할 node의 왼쪽 child node를 target node의 왼쪽 child node로 만든다.
구현
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self, value):
self.head = Node(value)
def insert(self, value):
# root node를 현재 node로 두고
self.current = self.head
while True:
# 새로 넣을 값이 현재 node보다 작을 경우
if value < self.current.value:
# 현재 node의 왼쪽 branch에 이미 node가 있을 경우
if self.current.left:
# 현재 node의 왼쪽 node를 현재 node로 변경 후 재탐색
self.current = self.current.left
# 현재 node의 왼쪽 branch에 node가 없는 경우
else:
# node 인스턴스를 생성하고 현재 node의 왼쪽 branch로 지정
self.current.left = Node(value)
# while문 탈출
break
# 새로 넣을 값이 현재 node보다 크거나 같을 경우
else:
# 현재 node의 오른쪽 branch에 이미 node가 있을 경우
if self.current.right:
# 현재 node의 오른쪽 node를 현재 node로 변경 후 재탐색
self.current = self.current.right
# 현재 node의 오른쪽 branch에 node가 없는 경우
else:
# node 인스턴스를 생성하고 현재 node의 오른쪽 branch로 지정
self.current.right = Node(value)
# while문 탈출
break
def isExist(self, value):
# root node를 현재 node로 두고
self.current = self.head
# 현재 node가 존재할 때
while self.current:
# 찾는 값이 현재 node의 값과 같다면
if value == self.current.value:
# 찾는 값이 존재하므로 True 리턴
return True
# 찾는 값이 현재 node보다 작으면
elif value < self.current.value:
# 현재 node의 왼쪽 branch의 node를 현재 node로 재탐색
self.current = self.current.left
# 찾는 값이 현재 node보다 크면
else:
# 현재 node의 오른쪽 branch의 node를 현재 node로 재탐색
self.current = self.current.right
# 탐색을 하다 더이상 branch가 없어 while을 탈출하면 찾는 값이 없으므로 False 리턴
return False
def delete(self, value):
searched = False
self.current = self.head
self.parent = self.head
# while을 통해 지우고자 하는 node와 지우고자 하는 node의 parent node 탐색
while self.current:
if value == self.current.value:
searched = True
break
elif value < self.current.value:
self.parent = self.current
self.current = self.current.left
else:
self.parent = self.current
self.current = self.current.right
# 못 찾았으면 False 리턴
if not searched:
return False
# 지우고자 하는 node에 왼쪽 오른쪽 branch가 모두 있을 때
if self.current.left and self.current.right:
# 지우고자 하는 node의 값이 parent node보다 작을 때
if value < self.parent.value:
# 현재 node의 오른쪽 node를 타겟으로
self.target = self.current.right
self.target_parent = self.current.right
# 타겟 node의 왼쪽 node가 없을 때 까지
# (= 지우고자 하는 node의 tree에서 제일 값이 작은 node를 찾을 때 까지)
while target.left:
self.target_parent = self.target
self.target = self.target.left
# 타겟 node의 오른쪽 branch node가 있다면
if self.target.right:
# 타겟 node의 오른쪽 branch node를 타겟 node의 parent node의 왼쪽 node로 대체
self.target_parent.left = self.target.right
else:
# 없으면 타겟 node의 parent node의 왼쪽 node를 None으로
self.target_parent.left = None
# 현재 node의 parent node의 왼쪽 node를 타겟 node로
self.parent.left = self.target
# 아래 두 라인을 통해 current node를 타겟 노드로 대체
self.target.right = self.current.right
self.target.left = self.current.left
del self.current
# 지우고자 하는 node의 값이 parent node보다 클 때
else:
self.target = self.current.right
self.target_parent = self.current.right
while self.target.left:
self.target_parent = self.target
self.target = self.target.left
if self.target.right:
self.target_parent.left = self.target.right
else:
self.target_parent.left = None
self.parent.right = self.target
self.target.right = self.current.right
self.target.left = self.current.left
del self.current
# 지우고자 하는 node에 오른쪽 branch만 있을 때
elif not self.current.left and self.current.right:
if value < self.parent.value:
self.parent.left = self.current.right
else:
self.parent.right = self.current.right
# 지우려는 node 인스턴스 삭제
del self.current
# 지우고자 하는 node에 왼쪽 branch만 있을 때
elif self.current.left and not self.current.right:
if value < self.parent.value:
self.parent.left = self.current.left
else:
self.parent.right = self.current.left
# 지우려는 node 인스턴스 삭제
del self.current
# 지우고자 하는 node가 leaf node일 때
else:
# 지우려는 값이 parent node보다 작다면 (왼쪽 branch라면)
if value < self.parent.value:
# parent node의 왼쪽 branch를 None으로 대체
self.parent.left = None
# 지우려는 값이 parent node보다 크다면 (오른쪽 branch라면)
else:
# parent node의 오른쪽 branch를 None으로 대체
self.parent.right = None
# 지우려는 node 인스턴스 삭제
del self.current
def leftRight(self, value):
self.current = self.head
while self.current:
# 찾고자 하는 node의 값과 현재 node의 값이 같을 때
if value == self.current.value:
# 현재 노드의 왼쪽 branch node의 값, 현재 노드의 오른쪽 branch node의 값 출력
print(self.current.left.value, self.current.right.value)
# 리턴
return True
# 찾고자 하는 node의 값이 현재 node의 값보다 작을 때
elif value < self.current.value:
# 현재 node의 왼쪽 branch node를 현재 노드로 대체
self.current = self.current.left
# 찾고자 하는 node의 값이 현재 node의 값보다 클 때
else:
# 현재 node의 오른쪽 branch node를 현재 노드로 대체
self.current = self.current.right
return False
if __name__ == "__main__":
BST = BinarySearchTree(100)
BST.insert(200)
BST.insert(150)
BST.insert(140)
BST.insert(160)
BST.insert(300)
BST.delete(200)
BST.leftRight(150)'Computer Science > Data Structure & Algorithm' 카테고리의 다른 글
| 그래프 (0) | 2022.05.30 |
|---|---|
| 병합정렬 (Merge sort) (0) | 2022.04.17 |
| 퀵정렬 (Quick sort) (0) | 2022.04.17 |
| 동적계획법(Dynamic Programming)과 분할정복 (Divide and Conquer) (0) | 2022.04.10 |
| 힙 (Heap) (0) | 2022.03.27 |