1. 트리(Tree)의 구조
2. 이진 트리와 이진 탐색 트리
3. 트리의 구현 - 코딩 클래스 높이기
4. 트리 Class의 전체 구현 코드
1. 트리(Tree)의 구조
(1) 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조를 말합니다.
실제로 이런 트리 데이터 구조는 이진 트리(Binary Tree) 형태로 탐색 알고리즘 구현을 위해 많이 사용됩니다.
(2) 트린 관련 용어 총 정리 - 이미지와 함께 보시면 이해가 빨라요!!
1) Node: 트리에서 데이터를 저장하는 기본 요소
2) Root Node: 트리 맨 위에 있는 노드
3) Level: 최상위 노드를 Lvl0으로 했을 때, 하위 Branch로 연결된 노드의 깊이
4) Parent Node: 어떤 노드의 상위 레벨에 노드
5) Child Node: 어떤 노드의 하위 레벨에 연결된 노드
6) Leaf Node(Terminal Node): Child 노드가 한 개도 없는 노드
7) Sibling Node(Brother Node): 동일한 Parent Node를 가진 노드
8) Depth: 트리에서 Node가 가질 수 있는 최대 Level
(출처: www.fun-coding.org/)
2. 이진 트리와 이진 탐색 트리(Binary Search Tree)
(1) 이진 트리: 노드의 최대 Branch가 2개인 트리를 의미합니다.
(2) 이진 탐색 트리 (Binary Search Tree, BST)
1) 개념: 이진 트리에 조건이 있는 트리입니다. 노드의 왼쪽에는 Root Node보다 작은 값들을, 오른쪽에는 큰 값들을
갖고 있는 구조의 트리입니다. (이미지 참조 - 출처: www.penjee.com)
이러한 이진 탐색 트리는 일반적인 정렬 탐색보다 더 효율적인 코딩 결과를 보여줄 수 있죠. 이것이 바로 트리 구조의 핵심적인 장점이라고 할 수 있습니다.
3. 트리의 구현 - 코딩 클래스를 높이기
트리 구조를 구현하기 위해서 객체 지향 프로그래밍을 사용해서 한 번 구현보도록 하겠습니다.
참고로 파이썬에서는 Anytree라는 패키지를 통해서 트리를 손쉽게 쓸 수 있습니다. 하지만 코딩하는 사람이라면 트리구조를 한 번 쯤은 구현하는 방법을 실행해보면 정말 실력 발달에 좋습니다.
그리고 아직 객체 지향 프로그래밍이 무엇인지 잘 모르시는 분들이라면, 간단한 기본정도 공부를 하시고 다시 오시는 것을 추천 드립니다. (객체 지향 프로그래밍이란?)
(1) 노드 클래스 만들기
|
1
2
3
4
5
|
class Node:
def __init__(self, value):
self.value = value ##노드의 값을 지정
self.right = None ## 왼쪽 공간을 만들어주는 것
self.left = None ## 오른쪽 공간을 만들어주는 것
|
cs |
Node에 값을 넣은 결과 value는 역시 1이고, 좌우 값은 비어있는 것을 볼 수 있네요.
(2) 이진 탐색 트리에 데이터 넣기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class NodeMgmt: ##Mgmt는 Management를 의미합니다. 즉 노드를 관리하겠다는 의미입니다.
def __init__(self, head):
self.head = head ## Root Node를 지정해주는 칸입니다.
def insert(self, value): ## 이제 값을 추가해주는 논리를 구성합니다.
self.current_node = self.head ## 시작 값은 Root Node입니다.
while True:
if value < self.current_node.value: ## 만약 현재 노드 값보다 value가 작다면
if self.current_node.left != None: ## 그리고 만약 왼쪽 노드 값이 null이 아니라면
self.current_node = self.current_node.left ## 왼쪽으로 이동한다.
else: ## 만약 비어있다면
self.current_node.left = Node(value) ## 노드로서 값을 지정해준다.
break ## 삽입이 끝났으니 Loop를 종료한다.
else: ## 만약 현재 노드 값보다 Value가 크다면
if self.current_node.right != None: ## 그리고 만약 오른쪽 노드 값이 Null이 아니라면
self.current_node = self.current_node.right ## 오른쪽으로 이동한다.
else: ## 만약 오른쪽 값이 비어있다면
self.current_node.right = Node(value) ## 노드로서 값을 지정해준다.
break
|
cs |
트리에서 구조를 삽입한 결과를 보여줍니다. 예상대로 Root Node는 1이고, 오른쪽에는 2라는 노드가 들어가 있고, 왼쪽에는 아직 아무 데이터가 없는 것을 확인할 수 있죠.
(3) 이진 트린 탐색에서 탐색 기능 구현하기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
def search(self, value):
self.current_node = self.head ## 우선 탐색을 시작할 value를 지정한다.
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 ##그래서 기준이 되는 current node를 왼쪽의 "노드"로 이동한 것. 그냥 값이 아니라
else: ## 만약 지금 노드값이 검색값보다 작다면, 오른쪽으로 이동
self.current_node = self.current_node.right ## 여기서도 기준이되는 current node를 오른쪽의 "노드"로 이동한 것.
return False ## 값이 없다면, False를 댈꼬와라
|
cs |
위의 코드 밑에다가 그대로 삽입해주시면 됩니다.
여기서 핵심은 이동할 때 그냥 값으로 이동하는게 아니라, 왼쪽 혹은 오른쪽의 "노드"로 위치를 이동한다는 것입니다.
코드 중에서 [ self.current_node = self.current_node.left ]로 작성을 했죠. 만약 단순 값만 찾는 거였다면 self.current_node.left.value로 코드를 작성했을 것입니다.
하지만 제가 작성한 코드는 "노드" 그 자체로 이동하는 것이라는 것을 기억해주셔야 해요!!
위의 트리에서는 -1은 없으니 False값을, 5는 존재하는 값이니 True를 반환했습니다.
(4) 이진 트리에서 삭제 기능 구현하기 - 가장 핵심 파트
<이론적인 이해>
이 파트는 경우의 수가 굉장히 많고, 그 경우의 수에 따라 다른 코딩이 들어가야 합니다.
그래서 단계적으로 이해하고, 구현하면서 코딩 실력을 높일 수 있는 가장 좋은 기회입니다.(가장 스트레스 받는 다는 소리...)
처음에는 많이 화가 나시더라도, 참으면서 천천히 해보면 다 할 수 있어요!! (내가 화가 났다는 소리)
1) Leaf Node의 삭제
- Leaf Node의 개념: Child 노드가 없는 Node
즉 이 경우 삭제할 NOde의 Parent Node가 삭제할 Node를 지칭하지 않도록 주의해야 합니다.
한번 아래의 사진을 보시죠.
19의 경우 아래의 child가 없는 Leaf Node입니다. 이것을 삭제한 이후에는 오른쪽처럼 15까지 없어지지 않도록 굉장히 유의 해야 합니다.
2) Child Node가 하나인 Node를 삭제
삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 코드를 구성해야 합니다.
15는 19라는 Child Node를 하나 가지고 있었죠. 근데 이것을 삭제하고, 10과 19를 다시 붙여주는 작업을 반드시 해야만 합니다.
3) Child Node가 두 개인 Node를 삭제하는 경우
트리 구조상 하나의 노드는 최대 2개의 Child Node를 가질 수 있습니다. 이 경우 오른쪽에 있는 Child Node를 다시 Parent Node로 지정해야 하는 작업을 반드시 거쳐야 합니다.
3) - 1. 삭제할 Node의 오른쪽 Child 중에서 가장 작은 값을 삭제할 Node의 Parent Node가 되게 하는 경우
3) - 2. 삭제할 Node의 왼쪽 Child 중에서 가장 큰 값을 삭제할 Node의 Parent Node가 되게 하는 경우
삭제하는 경우는 굉장히 경우의 수가 많으므로 반드시 하나하나 이론적인 이해를 거치신 뒤에 코드 구현으로 넘어가셔야 해요.
예를 들어, 위의 경우는 5가 삭제될 노드입니다. 이 경우 6이 Parent 노드는 경우는 3) - 1번의 경우에 해당 되겠죠.
만약에 6대신에 3을 Parent Node가 되게 하는 경우는 3) - 2번에 해당 될 것입니다.
<코드의 구현>
1) 삭제할 Node가 없는 경우 - False를 리턴하고, 함수를 종료합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def delete(self, value):
search = False ## 우선 변수를 설정
self.current_node = self.head ##Root를 기준으로 시작
self.parent = self.head ## Root의 Parent는 Root
while self.current_node:
if self.current_node.value == value: ## 만약 value가 존재하면, True를 반환
searched = True
break
elif value < self.current_node.value: ##찾는 값이 현재 값보다 작은 값
self.parent = self.current_node
self.current_node = self.current_node.left ## 왼쪽으로 이동한다.
else:
self.parent = self.current_node ## 찾는 값이 현재 값보다 큰 값
self.current_node = self.current_node.right ## 오른쪽으로 이동
##여기까지는 While문에서 Current Node가 존재하는 한 루프가 계속 돌기 때문에 찾는다면 True값 / 못 찾으면 False로 유지
## While문이 Break 했음에도 불구하고, searched가 False라면 없는 것
if searched == False:
return False
##여기까지가 가장 기본적인 단계입니다. 즉 삭제하고자 하는 값을 찾은 상태
|
cs |
2) Case1: 삭제할 Node가 Leaf Node인 경우는?
|
1
2
3
4
5
6
|
# self.current_node 가 삭제할 Node, self.parent는 삭제할 Node의 Parent Node인 상태
if self.current_node.left == None and self.current_node.right == None: ## 즉 좌우 Child 아무것도 없음
if value < self.parent.value:
self.parent.left = None ## value가 작으면 왼쪽을 삭제
else:
self.parent.right = None ## Value가 크면 오른쪽을 삭제
|
cs |
3) Case2: 삭제할 Node가 Child를 한 개 가지는 경우
|
1
2
3
4
5
6
7
8
9
10
11
|
p if self.current_node.left != None and self.current_node.right == None: ## 즉 왼쪽에 Child를 가지는 경우
if value < self.parent.value:
self.parent.left = self.current_node.left
else:
self.parent.right = self.current_node.left
elif self.current_node.left == None and self.current_node.right != None: ## 즉 오른쪽에 Child를 가지는 경우
if value < self.parent.value:
self.parent.left = self.current_node.right
else:
self.parent.right = self.current_node.right
|
cs |
3) Case3-1. 삭제할 Node가 Child가 두 개인데, Parent의 왼쪽에 있는 경우
이러한 경우 다음과 같은 전략이 필요합니다.
첫 번째. 삭제할 Node의 오른쪽 자식중에서 가장 작은 값을 삭제할 Node의 Parent Node가 되게하는 것입니다.
두 번째. 삭제할 Node의 왼쪽 자식 중에서 가장 큰 값을 삭제할 Node의 Parent Node가 되도록 한다.
우선 첫 번째 방법을 통해 구현한다고 가정합니다. 이 경우에도 세부 케이스가 나누어집니다.
Case3-1-1
: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
Case3-1-2
: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
네 이 부분을 바로 코드로 구현해보도록 하겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
if self.current_node.left != None and self.current_node.right != None: # case3
if value < self.parent.value: # case3-1
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
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
|
cs |
3) - 2 삭제할 Node가 Child를 두 개 갖고 있고, Parent의 오른쪽에 있을 경우
동일하게 이 경우에도 두 가지 전략이 존재합니다.
첫 번째. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 하는 것입니다.
두 번째. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
Case 3-2-1
: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
Case3-2-2
: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
else:
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
self.parent.right = self.change_node
self.change_node.left = self.current_node.left
self.change_node.right = self.current_node.right
|
cs |
4. 트리 전체 구현 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class NodeMgmt:
def __init__(self, head):
self.head = head
def insert(self, value):
self.current_node = self.head
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
def search(self, value):
self.current_node = self.head
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
def delete(self, value):
# 삭제할 노드 탐색
searched = False
self.current_node = self.head
self.parent = self.head
while self.current_node:
if self.current_node.value == value:
searched = True
break
elif value < self.current_node.value:
self.parent = self.current_node
self.current_node = self.current_node.left
else:
self.parent = self.current_node
self.current_node = self.current_node.right
if searched == False:
return False
# case1
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
# case2
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
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
# case 3
elif self.current_node.left != None and self.current_node.right != None:
# case3-1
if value < self.parent.value:
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
self.parent.left = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.change_node.left
# case 3-2
else:
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
self.parent.right = self.change_node
self.change_node.right = self.current_node.right
self.change_node.left = self.current_node.left
return True
|
cs |
여기까지 정말 긴 여정이었습니다. 한 번에 다 하실 수 있을거라 생각하지 않습니다. 저도 이 코드를 솔직히 남이 알려주고, 강의를 듣고, 혼자서 20번 넘게 코드를 외울 정도로 구현해봤던 것 같습니다.
여러분들도 할 수 있습니다.
'Python > 데이터 구조' 카테고리의 다른 글
| 데이터 구조 4. Set(집합)의 이해 및 활용 방법 (0) | 2020.11.18 |
|---|---|
| 데이터 구조3. 스택(Stack) 파이썬에서 구현하기 (0) | 2020.11.11 |
| 데이터 구조2. 큐(Queue) - 파이썬에서 구현하기 (0) | 2020.11.05 |
