이진탐색트리(Binary search tree) - 파이썬, 자료구조

위의 움짤을 참고하면 이해하기 쉽다.

맨처음 root노드가 등장한다. 추가된 노드는 root노드와 대소 비교를 통해 왼쪽서브트리로 빠지거나 오른쪽 서브트리로 빠진다.

이후 추가된 노드들도 대소비교를 거쳐 왼쪽, 오른쪽 서브트리로 빠진다.

​

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 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195

#노드 클래스 만들기 class Node: def __init__(self,item): self.val = item self.right = None self.left = None #Binary Search Tree class BinarySearchTree: def __init__(self): self.head = None self.preorder_list = [] self.inorder_list = [] self.postorder_list = [] #추가메서드1 def add(self, item): #루트노드가 존재하는 경우와 존재하지 않는 경우 if self.head is None: self.head = Node(item) else: self._add(self.head, item) #추가메서드2 def _add(self, cur, item): #cur.val과 item값의 대소비교 후 방향정하기 #cur.val(기준)값이 item 보다 크다면 : 왼쪽으로 if cur.val >= item: #또 cur.left에 노드가 존재하냐 안하냐로 갈림 if cur.left is None: cur.left = Node(item) else: self._add(cur.left, item) #cur.val(기준)값이 item보다 작다면 : 오른쪽으로 else: #또 cur.right에 노드가 존재하냐 안하냐로 갈림 if cur.right is None: cur.right = Node(item) else: self._add(cur.right, item) #탐색메서드1 def search(self, item): #self.head.val값d의 존재여부 if self.head.val is None: return False else: return self._search(self.head, item) #탐색메서드2 def _search(self, cur, item): #cur.val값이 item값과 일치할 경우와 아닐경우. if cur.val == item: return True #cur.val값과 item값을 대소비교 후 방향 정하기 else: #cur.val값이 item값보다 큰 경우 : 왼쪽으로 if cur.val >= item: #cur.left이 존재하는지 아닌지 따져줘야함. if cur.left is None: return False else: return self._search(cur.left, item) else: #cur.right이 존재하는지 아닌지 따져줘야함. if cur.right is None: return False else: return self._search(cur.right, item) #삭제메서드1(루트노드 체크하고 넘어가기) def remove(self, item): #루트노드의 존재 여부 확인 if self.head is None: print("no item") #self.head.val값과 item값이 일치하는지 확인 if self.head.val == item: # 1) 노드의 자식이 없는 경우. if self.head.left is None and self.head.right is None: self.head = None # 2) 노드의 자식이 하나인 경우 elif self.head.left is not None and self.head.right is None: self.head = self.head.left elif self.head.left is None and self.head.right is not None: self.head = self.head.right # 3) 노드의 자식이 둘인 경우 elif self.head.left is not None and self.head.right is not None: self.head.val = self.most_left_val_from_right_tree(self.head.right).val self.remove_most_left_val(self.head, self.head.right, self.head.val) else: #self.head.val(기준)값과 item값의 대소비교가 필요. if self.head.val >= item: self._remove(self.head, self.head.left, item) else: self._remove(self.head, self.head.right, item) #삭제메서드2(루트노드 이후) def _remove(self, parent, cur, item): #cur.val(기준)값과 item값이 일치하는 경우, 일치하지않는 경우 if cur.val == item: # 1) 노드의 자식이 없는 경우 if cur.left is None and cur.right is None: if parent.left == cur: parent.left = None else: parent.right = None # 2) 노드의 자식이 하나인 경우 elif cur.left is not None and cur.right is None: if parent.left == cur: parent.left = cur.left else: parent.right = cur.left elif cur.left is None and cur.right is not None: if parent.left == cur: parent.left = cur.right else: parent.right = cur.right # 3) 노드의 자식이 둘인 경우 elif cur.left is not None and cur.right is not None: cur.val = self.most_left_val_from_right_tree(cur.right).val self.remove_most_left_val(cur, cur.right, cur.val) else: if cur.val >= item: self._remove(cur, cur.left, item) else: self._remove(cur, cur.right, item) #삭제메서드3(오른쪽 서브트리에서 제일 왼쪽의 리프노드를 찾는 메서드) def most_left_val_from_right_tree(self, cur): #cur.left가 존재하냐 안하냐에 따름. if cur.left is None: return cur else: return self.most_left_val_from_right_tree(cur.left) #삭제메서드4(찾은 제일 왼쪽의 리프노드를 제거하는 메서드) def remove_most_left_val(self, parent, cur, item): #cur.val값과 item값이 일치하냐 안하냐로 갈림 if cur.val == item: #parent노드의 오른쪽 왼쪽 중에서 어디에 cur노드가 속하느냐 따라에 갈림 if parent.left == cur: parent.left = None else: parent.right = None else: #cur.val(기준)값과 item값의 대소비교 필요 if cur.val >= item: self.remove_most_left_val(cur, cur.left, item) else: self.remove_most_left_val(cur, cur.right, item) def Pre_order_traversal(self): #루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 if self.head is not None: self._preorder(self.head) def _preorder(self, cur): self.preorder_list.append(cur.val) print(cur.val) if cur.left is not None: self._preorder(cur.left) if cur.right is not None: self._preorder(cur.right) def In_order_traversal(self): #왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리 if self.head is not None: self._Inorder(self.head) def _Inorder(self, cur): if cur.left is not None: self._Inorder(cur.left) self.preorder_list.append(cur.val) print(cur.val) if cur.right is not None: self._Inorder(cur.right) def Post_order_traversal(self): #왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트노드 if self.head is not None: self._Postorder(self.head) def _Postorder(self, cur): if cur.left is not None: self._Postorder(cur.left) if cur.right is not None: self._Postorder(cur.right) self.postorder_list.append(cur.val) print(cur.val) Colored by Color Scripter