이진 트리 구조에서의 스택프레임 이진트리의 규칙 노드는 왼쪽부터 오른쪽의 순으로, 상위 노드부터 하위 노드의 순으로 생성이 된다 노드에 도착만 하다: 하위 트리를 순회 노드에 방문한다: 해당 노드를 출력(print) 전위 순회 (preorder) 중위 순회 (inorder) 후위 순회 (postorder) 순회 순서 NLR 순으로 노드 방문 (노드 -> 왼쪽 -> 오른쪽) LNR 순으로 노드 방문 (왼쪽 -> 노드 -> 오른쪽) LRN 순으로 노드 방문 (왼쪽 -> 오른쪽 -> 노드) 특징 >> print(n.item) >> if n.left >> if n.right >> if n.left >> print(n.item) >> if n.right >> if n.left >> print(n.item) 적용 디렉토리의 하위 디렉토리를 포함한 파일 복사 계산기 이진 트리 구조의 형태 특징: 노드의 생성은 왼쪽에서 오른쪽으로, 부모노드에서 자식노드로의 순서를 가지게 된다. [완전 이진 트리 구조] # 전위 순회 코드
def preorder(self, n): if n != None: print(str(n.item), ' ', end-='') if n.left: self.preorder(n.left) if n.right: self.preorder(n.right) t.preorder(t.root)
>> if n.right
cs
가장 헷갈렸던 것이 재귀함수에 대한 정확한 이해가 안됐었는지,
Node D 까지 방문을 한 이후 -> 다시 부모노드인 B Node 로 어떻게 올라가는지가 혼동스러웠다.
결론적으로는 스택프레임의 가장 상위에 push 된 Node D 함수를 순회 방문하며 pop 이 된 이후 스택에 남아있는 Node B 의 함수 처리를 진행하는 것이었다.
(즉, 맨 마지막 D 노드의 방문이 끝나면 preorder(B) 의 함수가 실행되어 self.preorder(n.right) 가 실행)
대표적인 데이터 구조7: 트리
1. 트리 (Tree) 구조
2. 알아둘 용어
이진 트리(binary tree)의 특징
- 1) level i에서 최대 노드 수 : $2^{i-1}$
- 2) 높이가 h인 이진 트리의 최대 노드 수 : $2^{h}-1$
- 3) 높이가 h인 이진 트리의 최소 노드의 개수 : h
- 이진 트리(binary tree)의 종류
이진 트리는 말 그대로 부모노드가 가질수 있는 자식노드가 최대 2개라는 의미이다. 그러한 이진 트리의 데이터를 탐색하는 방법을 설명하면 다음과 같은 방법들이 있다.
전위 순회(preorder traversal)
- 현재 노드가 처음 그리고 왼쪽 자식 노드 다음 오른쪽 자식노드를 탐색하게 하는 방식으로 노드에 값이 존재하지 않을 때까지 순회(재귀)하도록하는 탐색방식이다.
- 중위 순회(inorder traversal)
- 현재 노드의 왼쪽 자식노드부터 시작해서 현재 노드 그리고 마지막으로 오른쪽 자식 노드를 순회하는 방법이다.
- 후위 순회(postorder traversal)
- 현재 노드의 왼쪽 자식노드부터 시작해서 현재 노드의 오른쪽 자식노드 그리고 마지막으로 현재노드를 순회하는 방법이다.
- 레벨 순회(level traversal)
- level(depth)순으로 위에서 아래로 그리고 왼쪽부터 오른쪽으로 순회하는 방법이다.
- 위의 이진 트리의 순회를 반복적으로 하기 위해서 이전에 배웠던 자료구조인 스택과 큐를 활용할 것이다. 활용하기 위해서 다시 한번 기억을 떠올리며 만들어 본다.
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 | class Node: def __init__(self, data=None): self.__data=data self.__next=None @property def data(self): return self.__data @data.setter def data(self, data): self.__data=data @property def next(self): return self.__next @next.setter def next(self, target): self.__next=target class My_Queue: def __init__(self, head=None, tail=None): self.head=head self.tail=tail def is_empty(self): if self.head == None: return True def enqueue(self, data): new_node=Node(data) if self.is_empty(): self.head=new_node self.tail=new_node else: self.tail.next=new_node self.tail=new_node def dequeue(self): if self.is_empty(): print("현재 Queue에 노드가 존재하지 않습니다.") else: pop_data=self.head self.head=self.head.next return pop_data.data class My_stack: def __init__(self, head=None, tail=None): self.head=head self.tail=tail def is_empty(self): if self.head: return False else: return True def push(self, data): new_node=Node(data) if self.is_empty(): self.head=new_node self.tail=new_node else: new_node.next=self.head self.head=new_node def pop(self): if self.is_empty(): return None pop_node=self.head self.head=self.head.next pop_node.next=None return pop_node.data |
정상적으로 작동하는지 확인하기 위해 테스트를 해본다.
Queue 테스트
1 2 3 4 5 6 7 8 9 | q = My_Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) while not q.is_empty(): print(q.dequeue(), end=' ') |
1 | 1 2 3 4 5 |
- Stack 테스트
1 2 3 4 5 6 7 8 9 10 | s = My_stack() s.push(1) s.push(2) s.push(3) s.push(4) s.push(5) while not s.is_empty(): print(s.pop(), end=" ") |
#
1 | 5 4 3 2 1 |
스택, 큐는 순회를 구현할때 사용
- 위의 파일을 스택과 큐를 나누어서 각각 queue1, stack1이라는 python 파일로 저장하였다.
큐 : 레벨 순서 순회시 필요
스택 : 전위, 중위, 후위 순회를 반복문으로 구현할때 필요
1 2 | from queue1 import My_Queue from stack1 import My_Stack |
- 기본적으로 Tree의 노드를 먼저 만들어 본다.
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 | class TreeNode: def __init__(self, data=None): self.__data=data self.__left=None self.__right=None def __del__(self): print('data {} is deleted'.format(self.__data)) @property def data(self): return self.__data @data.setter def data(self, data): self.__data=data @property def left(self): return self.__left @left.setter def left(self, left): self.__left=left @property def right(self): return self.__right @right.setter def right(self, right): self.__right=right |
순회(traversal)
순회(traversal)를 하는 코드를 작성하는 방법은 크게 2가지를 생각해 볼 수 있다.
재귀 : 성능은 떨어지지만, 가독성이 높다.
반복문 : 성능은 높지만, 가독성이 떨어진다.(실제로는 성능이 최우선이므로 반복문을 사용할 수 있다면, 반복문을 사용하는 것이 좋다.)
재귀함수를 통한 순회 코드 작성
- 전위, 순위, 후위는 현재 노드의 데이터를 프린트해주는 순서에 의해서 결정될 것이다. 각 함수는공통된 코드를 갖으며, 우선 현재 노드의 왼쪽노드, 오른쪽 노드 순으로 각 함수를 재귀적으로 동작한다.
preorder(전위)
1 2 3 4 5 6 7 8 9 10 | def preorder(cur): if not cur: return print(cur.data, end = " ") preorder(cur.left) preorder(cur.right) |
inorder(중위)
1 2 3 4 5 6 7 8 9 10 | def inorder(cur): if not cur: return inorder(cur.left) print(cur.data, end = " ") inorder(cur.right) |
postorder(후위)
1 2 3 4 5 6 7 8 9 10 | def postorder(cur): if not cur: return postorder(cur.left) postorder(cur.right) print(cur.data, end = " ") |
반복문을 통한 순회 코드 작성
- 1) 스택(Stack) : 재귀함수로 전위, 중위, 후위를 구현한다는 것은 각 함수가 계속쌓이는 것과 동일하므로 스택을 사용한 것이라고 할 수 있음.
- 2) 큐(Queue) :
iter_preorder
1 2 3 4 5 6 7 8 9 10 11 12 | def iter_preorder(cur): s=My_stack() while True: while cur: print(cur.data, end = " ") s.push(cur) cur = cur.left cur=s.pop() if not cur: break cur=cur.right |
iter_inorder
- 2가지 방식으로 구현해보았다.
1 2 3 4 5 6 7 8 9 10 11 12 | def iter_inorder(cur): s=My_stack() while True: while cur: s.push(cur) cur = cur.left cur=s.pop() if not cur: break print(cur.data, end = " ") cur=cur.right |
1 2 3 4 5 6 7 8 9 10 11 12 | def iter_inorder(cur): stack_ls=My_stack() while True: while cur.left: stack_ls.push(cur) cur=cur.left print(cur.data, end = " ") if stack_ls.is_empty(): break cur=stack_ls.pop() print(cur.data, end = " ") cur=cur.right |
iter_postorder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def iter_postorder(cur): s1=My_stack() s2=My_stack() s1.push(cur) while s1.is_empty(): cur=s1.pop() if not cur.left: s1.push(cur.left) if not cur.right: s1.push(cur.right) s2.push(cur) while not s2.is_empty(): cur=s2.pop() print(cur.data, end=" ") |
levelorder
1 2 3 4 5 6 7 8 9 10 11 | def levelorder(cur): q = My_Queue() q.enqueue(cur) while not q.is_empty(): cur = q.dequeue() print(cur.data, end= " ") if cur.left : q.enqueue(cur.left) if cur.right : q.enqueue(cur.right) |
1 2 3 4 5 6 7 8 9 10 11 | n1=TreeNode(1) n2=TreeNode(2) n3=TreeNode(3) n4=TreeNode(4) n5=TreeNode(5) n6=TreeNode(6) n7=TreeNode(7) n1.left=n2; n1.right=n3 n2.left=n4; n2.right=n5 n3.left=n6; n3.right=n7 |
1 | preorder(n1) |
1 | 1 2 4 5 3 6 7 |
1 | inorder(n1) |
1 | 4 2 5 1 6 3 7 |
1 | postorder(n1) |
1 | 4 5 2 6 7 3 1 |
1 | iter_preorder(n1) |
1 | 1 2 4 5 3 6 7 |
1 | iter_inorder(n1) |
1 | 4 2 5 1 6 3 7 |
1 | iter_postorder(n1) |
1 | 4 5 2 6 7 3 1 |
1 | levelorder(n1) |
1 | 1 2 3 4 5 6 7 |
4. 자료 구조 이진 탐색 트리의 장점과 주요 용도
- 주요 용도: 데이터 검색(탐색)
- 장점: 탐색 속도를 개선할 수 있음
단점은 이진 탐색 트리 알고리즘 이해 후에 살펴보기로 함
- 아래 이미에서 볼 수 있듯이 이진 탐색 트리 알고리즘은 3 step안에 27이라는 숫자를 찾아내지만, 배열(array)에서는 하나씩 비교하면 찾기 때문에 훨씬 많은 step을 거쳐야 한다.
- 이와 같이 검색하기 위한 데이터를 저장해 놓을 때 이진 탐색 트리를 많이 사용한다.
이진트리와 정렬된 배열간의 탐색 비교
(출처: //www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
5. 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기
5.1. 노드 클래스 만들기
1 2 3 4 5 | class Node: def __init__(self, value): self.value = value self.left = None self.right = None |
5.2. 이진 탐색 트리에 데이터 넣기
- 이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함
- 값이 같거나 크면 오른쪽에 위치하도록하고, 작으면 왼쪽에 위치하도록 코드를 작성함.
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 | 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, target): self.current_node = self.head while self.current_node: if self.currnet_node.value == target: return self.current_node elif self.current_node.value > target: self.current_node=self.current_node.left else: self.current_node=self.current_node.right return False |
1 2 3 4 5 6 7 8 | head = Node(1) BST = NodeMgmt(head) BST.insert(2) BST.insert(3) BST.insert(0) BST.insert(4) BST.insert(8) BST.search(-1) |
1 | False |
5.4. 이진 탐색 트리 삭제
- 매우 복잡함. 경우를 나누어서 이해하는 것이 좋음
5.4.1. Leaf Node 삭제
- Leaf Node: Child Node 가 없는 Node
- 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.
5.4.2. Child Node 가 하나인 Node 삭제
- 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.
5.4.3. Child Node 가 두 개인 Node 삭제
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 삭제할 Node의 오른쪽 자식 선택
- 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
- 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
- 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
- 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
- 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함
5.5. 이진 탐색 트리 삭제 코드 구현과 분석
5.5.1 삭제할 Node 탐색
- 삭제할 Node가 없는 경우도 처리해야 함
- 이를 위해 삭제할 Node가 없는 경우는 False를 리턴하고, 함수를 종료 시킴
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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 |
5.5.2. Case1: 삭제할 Node가 Leaf Node인 경우
1 2 3 4 5 6 7 | 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 del self.current_node |
5.5.2. Case2: 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
1 2 3 4 5 6 7 8 9 10 | if 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 |
5.5.3. Case3-1: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 왼쪽에 있을 때)
- 기본 사용 가능 전략
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
- 경우의 수가 또다시 두가지가 있음
- Case3-1-1: 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- Case3-1-2: 삭제할 Node가 Parent Node의 왼쪽에
있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
- 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 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: 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.current_node.left |
5.5.4. Case3-2: 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽에 있을 때)
- 기본 사용 가능 전략
- 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
- 기본 사용 가능 전략 중, 1번 전략을 사용하여 코드를 구현하기로 함
- 경우의 수가 또다시 두가지가 있음
- Case3-2-1: 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 Child Node가 없을 때
- Case3-2-2: 삭제할 Node가 Parent
Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
- 가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 왜냐하면 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 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 |
5.5.5. 파이썬 전체 코드 구현
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 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 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 elif self.current_node.left != None and self.current_node.right != None: 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.current_node.left 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 |
참고: //ejklike.github.io/2018/01/09/traversing-a-binary-tree-1.html
5.5.6. 파이썬 전체 코드 테스트
- random 라이브러리 활용
- random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴
- 예: random.randint(0, 99): 0에서 99까지 숫자중 특정 숫자를 랜덤하게 선택해서 리턴해줌
- random.randint(첫번째 숫자, 마지막 숫자): 첫번째 숫자부터 마지막 숫자 사이에 있는 숫자를 랜덤하게 선택해서 리턴
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 | import random bst_nums = set() while len(bst_nums) != 100: bst_nums.add(random.randint(0, 999)) head = Node(500) binary_tree = NodeMgmt(head) for num in bst_nums: binary_tree.insert(num) for num in bst_nums: if binary_tree.search(num) == False: print ('search failed', num) delete_nums = set() bst_nums = list(bst_nums) while len(delete_nums) != 10: delete_nums.add(bst_nums[random.randint(0, 99)]) for del_num in delete_nums: if binary_tree.delete(del_num) == False: print('delete failed', del_num) |
- 위와 같은 방법과 다르게 아래 그림과 같은 BST를 구현해보고자 한다.
Binary Search Tree
- 모든 원소는 서로 다은 key를 가진다.
- 왼쪽 서브 트리에 있는 모든 키값들은 루트의 키값보다 작다.
- 오른쪽 서브 트리에 있는 모든 키값들은 루트의 키값보다 크다.
- 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.
- binary_tree.py 파일
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 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 | from queue1 import My_Queue from stack1 import MY_stack class TreeNode: def __init__(self, data=None): self.__data=data self.__left=None self.__right=None def __del__(self): print('data {} is deleted'.format(self.__data)) @property def data(self): return self.__data @data.setter def data(self, data): self.__data=data @property def left(self): return self.__left @left.setter def left(self, left): self.__left=left @property def right(self): return self.__right @right.setter def right(self, right): self.__right=right def preorder(cur): if not cur: return print(cur.data, end=' ') preorder(cur.left) preorder(cur.right) def inorder(cur): if not cur: return inorder(cur.left) print(cur.data, end=' ') inorder(cur.right) def postorder(cur): if not cur: return postorder(cur.left) postorder(cur.right) print(cur.data, end=' ') def iter_preorder(cur): s=Stack() while True: while cur: print(cur.data, end=' ') s.push(cur) cur=cur.left cur=s.pop() if not cur: break cur=cur.right def iter_inorder(cur): s=Stack() while True: while cur: s.push(cur) cur=cur.left cur=s.pop() if not cur: break print(cur.data, end=' ') cur=cur.right def iter_postorder(cur): s1=Stack() s2=Stack() s1.push(cur) while not s1.empty(): cur=s1.pop() s2.push(cur) if cur.left: s1.push(cur.left) if cur.right: s1.push(cur.right) while not s2.empty(): cur=s2.pop() print(cur.data, end=' ') def levelorder(cur): q=Queue() q.enqueue(cur) while not q.empty(): cur=q.dequeue() print(cur.data, end=' ') if cur.left: q.enqueue(cur.left) if cur.right: q.enqueue(cur.right) if __name__=="__main__": n1=TreeNode(1) n2=TreeNode(2) n3=TreeNode(3) n4=TreeNode(4) n5=TreeNode(5) n6=TreeNode(6) n7=TreeNode(7) n1.left=n2; n1.right=n3 n2.left=n4; n2.right=n5 n3.left=n6; n3.right=n7 iter_preorder(n1) print() iter_inorder(n1) print() iter_postorder(n1) print() levelorder(n1) print() |
- 앞의 파일의 class를 활용하여 BST를 구현해 볼 것이다. 우선 각 기능을 분할하여 설명할 것이다.
- 앞서 배웠던 순회의 개념 중 preorder 방식으로 노드가 갖고 있는 키값을 확인할 수 있도록 재귀(recursion)를 활용한 함수를 만든다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | from binary_tree import TreeNode class BST: def __init__(self): self.root=None def get_root(self): return self.root def preorder_traverse(self, cur, func, *args, **kwargs): if not cur: return func(cur, *args, **kwargs) self.preorder_traverse(cur.left, func, *args, **kwargs) self.preorder_traverse(cur.right, func, *args, **kwargs) |
- insert 함수는 새로운 키값을 추가해주기 위한 함수로서 현재노드와 크기를 비교하여 작은 값은 왼쪽으로 큰 값은 오른쪽으로 이동하면서 빈 자리에 노드를 추가해 주면된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | def insert(self, data): new_node=TreeNode(data) cur=self.root if not cur: self.root=new_node return while True: parent=cur if data < cur.data: cur=cur.left if not cur: parent.left=new_node return else: cur=cur.right if not cur: parent.right=new_node return |
- 키값을 받아 현재 BST에 있는 노드들의 값과 일치하는 노드를 return한다.
1 2 3 4 5 6 7 8 9 10 | def search(self, target): cur=self.root while cur: if cur.data==target: return cur elif cur.data > target: cur=cur.left elif cur.data < target: cur=cur.right return cur |
- target값과 동일한 키값을 갖는 노드를 현재 BST 노드에서 제거하는 함수이다. 위에서 if-else 구문을 통해서 만든 BST와 동일한 기능을 하며, 위에서 만든 방식은 제거할 노드의 자식 노드가 2개인 경우 제거할 노드의 오른쪽 노드 서브트리에서 제일 작은 값으로 바꿔주었지만, 아래의 코드는 제거할 노드의 왼쪽 노드 서브트리 중에 가장 큰 값으로 바꿔주는 방법만 다르다.
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 | def __remove_recursion(self, cur, target): if not cur: return None, None elif target < cur.data: cur.left, rem_node=self.__remove_recursion(cur.left, target) elif target > cur.data: cur.right, rem_node=self.__remove_recursion(cur.right, target) else: if not cur.left and not cur.right: rem_node=cur cur=None elif not cur.right: rem_node=cur cur=cur.left elif not cur.left: rem_node=cur cur=cur.right else: replace=cur.left while replace.right: replace=replace.right cur.data, replace.data=replace.data, cur.data cur.left, rem_node=self.__remove_recursion(cur.left, replace.data) return cur, rem_node def remove(self, target): self.root, removed_node=self.__remove_recursion(self.root, target) if removed_node: removed_node.left=removed_node.right=None return removed_node |
테스트
1 | bst=BST() |
1 2 3 4 5 6 7 8 9 | bst.insert(6) bst.insert(3) bst.insert(2) bst.insert(4) bst.insert(5) bst.insert(8) bst.insert(10) bst.insert(9) bst.insert(11) |
1 2 | f=lambda x: print(x.data, end=' ') bst.preorder_traverse(bst.get_root(), f) |
1 | 6 3 2 4 5 8 10 9 11 |
1 2 3 4 5 | res=bst.search(8) if res: print('searched data : {}'.format(res.data)) else: print('search failed') |
1 | searched data : 8 |
1 2 3 4 5 6 7 | bst.remove(6) bst.preorder_traverse(bst.get_root(), f) |
1 2 | data 6 is deleted 5 3 2 4 8 10 9 11 |
6. 이진 탐색 트리의 시간 복잡도와 단점
6.1. 시간 복잡도 (탐색시)
- depth (트리의 높이) 를 h라고 표기한다면, O(h)
- n개의 노드를 가진다면, $h = log_2{n} $ 에 가까우므로, 시간 복잡도는 $ O(log{n}) $
- 참고: 빅오 표기법에서 $log{n}$ 에서의 log의 밑은 10이 아니라, 2입니다.
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을
의미함
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을
의미함
- 참고: 빅오 표기법에서 $log{n}$ 에서의 log의 밑은 10이 아니라, 2입니다.
(출처: //www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)
6.2. 이진 탐색 트리 단점
- 평균 시간 복잡도는 $ O(log{n}) $ 이지만,
- 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
- 다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( $O(n)$ )