이진 검색 트리, 만들다보니 코드가 길어져서... insert나 traverse는 다다닥 만드는데 delete 만들면서 좀 생각해야했던.
삭제 시 이진 트리에서는 3가지 경우를 고려해야합니다.
자식 노드가 없거나, 1개 있거나, 두 개 다 있거나 한 경우인데요. 저는 case 1을 구현하려고 prev 변수를 만들어서 객체 생성 시 자신의 parent node를 저장했고, 이후 prev 노드가 변경될 때 이를 수정해주며 case 1의 삭제를 구현했습니다.
case 3에서 자식 노드가 두 개 다 있을 경우에는 타겟 노드의 자식들 중에서 successor나 predecessor를 추출한 다음 해당 노드를 제거하고, 이어서 타겟 노드의 값을 successor나 predecessor로 변경하면 정상적으로 삭제가 가능합니다. 이 과정에선 값만 덮어씌우는 것이기 때문에 prev값을 따로 변경할 필요 없습니다.
case 2에선 prev 노드의 right 또는 left 노드를 타켓의 right 또는 left 노드로 바꾸기에 타겟 값을 제거할 수 있습니다. 이 과정에서 타겟의 right 또는 left 노드의 prev 값을 적절한 값으로 수정한 후 prev의 right 또는 left로 옮겨야 합니다. 그렇지 않다면 노드가 삭제가 되지 않는 상황이 발생할 수 있습니다.
delete
1. 자식 노드가 없는 경우
2. 자식 노드가 하나인 경우
3. 자식 노드가 둘인 경우
*생각대로 작성한 것이라 버그가 있을 수도 있습니다~
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 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 | class Node: def __init__(self, val, prev): self.val = val self.left = None self.right = None self.prev = prev class binarySearchTree: def __init__(self): self.root = None self.pre_order = [] self.in_order = [] self.post_order = [] self.successor = None self.predecessor = None def insert(self, val): if self.root == None: self.root = Node(val, None) else: if val > self.root.val: if self.root.right == None: self.root.right = Node(val, self.root) elif self.root.right != None: self._insert(self.root.right, val) elif val <= self.root.val: if self.root.left == None: self.root.left = Node(val,self.root) elif self.root.left != None: self._insert(self.root.left, val) def _insert(self, node, val): if val > node.val: if node.right == None: node.right = Node(val, node) elif node.right != None: self._insert(node.right, val) elif val <= node.val: if node.left == None: node.left = Node(val, node) elif node.left != None: self._insert(node.left, val) def in_order_traversal(self): self.in_order = [] if self.root == None: print self.in_order else: self._in_order_traversal(self.root) print "in_order traversal : ", self.in_order def _in_order_traversal(self, node): if node.left != None: self._in_order_traversal(node.left) self.in_order.append(node.val) if node.right != None: self._in_order_traversal(node.right) def pre_order_traversal(self): self.pre_order = [] if self.root == None: print self.pre_order else: self._pre_order_traversal(self.root) print "pre_order traversal : ", self.pre_order def _pre_order_traversal(self, node): self.pre_order.append(node.val) if node.left != None: self._pre_order_traversal(node.left) if node.right != None: self._pre_order_traversal(node.right) def post_order_traversal(self): self.post_order = [] if self.root == None: print self.post_order else: self._post_order_traversal(self.root) print "post_order traversal : ", self.post_order def _post_order_traversal(self, node): if node.left != None: self._post_order_traversal(node.left) if node.right != None: self._post_order_traversal(node.right) self.post_order.append(node.val) def extractRelativeMaximum(self, node): if node == None: print "Root not Found" return else: if node.right != None: self._extractSuccessor(node.right) return self.successor elif node.left != None: self._extractPredecessor(node.left) return self.predecessor def _extractSuccessor(self, node): if node.left != None: self._extractSuccessor(node.left) elif node.left == None: self.successor = node.val def _extractPredecessor(self, node): if node.right != None: self._extractSuccessor(node.right) elif node.right == None: self.predecessor = node.val def delete(self, val): # case 1 : no child node # case 2 : 1 child node # case 3 : 2 child node if self.root == None: print "Root not Found." return else: self._delete(self.root, val) def _delete(self, node, val): if node.val == val: if node.left == None and node.right == None: # case 1 if node.prev == None: # root node self.root = None elif node.prev !=None: if node.prev.right != None: if node.prev.right.val == node.val: node.prev.right = None if node.prev.left != None: if node.prev.left.val == node.val: node.prev.left = None elif node.left != None and node.right != None: # case 3 relativeMax=self.extractRelativeMaximum(node) self.delete(relativeMax) # this node don't have two child node.val = relativeMax return elif node.right != None and node.left == None: # case 2 : right if node.prev != None: if node.prev.right != None: if node.prev.right.val == node.val: node.right.prev = node.prev.right.prev node.prev.right = node.right if node.prev.left != None: if node.prev.left.val == node.val: node.right.prev = node.prev.left.prev node.prev.left = node.right elif node.prev == None: node.right.prev = None self.root = node.right return elif node.left != None and node.right == None: # case 2 : left if node.prev != None: if node.prev.right != None: if node.prev.right.val == node.val: node.left.prev = node.prev.right.prev node.prev.right = node.left if node.prev.left != None: node.left.prev = node.prev.left.prev if node.prev.left.val == node.val: node.prev.left = node.left elif node.prev == None: node.left.prev = None self.root = node.left return elif node.val > val: if node.left == None: print "Target not Found" else: self._delete(node.left, val) elif node.val < val: if node.right == None: print "Target not Found" else: self._delete(node.right, val) if __name__ == "__main__": bst = binarySearchTree() abc = ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H'] for el in abc: bst.insert(el) for el in abc: bst.in_order_traversal() bst.pre_order_traversal() bst.post_order_traversal() bst.delete(el) print "deleted alphabet : ", el bst.delete('Q') for el in abc: bst.insert(el) bst.in_order_traversal() bst.pre_order_traversal() bst.post_order_traversal() bst.delete('Q') bst.in_order_traversal() bst.pre_order_traversal() bst.post_order_traversal() | cs |
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 | C:\Python27\python.exe C:/Users/user/PycharmProjects/untitled/binarySearchTree.py in_order traversal : ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] pre_order traversal : ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H'] post_order traversal : ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'] deleted alphabet : F in_order traversal : ['A', 'B', 'C', 'D', 'E', 'G', 'H', 'I'] pre_order traversal : ['G', 'B', 'A', 'D', 'C', 'E', 'I', 'H'] post_order traversal : ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G'] deleted alphabet : B in_order traversal : ['A', 'C', 'D', 'E', 'G', 'H', 'I'] pre_order traversal : ['G', 'C', 'A', 'D', 'E', 'I', 'H'] post_order traversal : ['A', 'E', 'D', 'C', 'H', 'I', 'G'] deleted alphabet : A in_order traversal : ['C', 'D', 'E', 'G', 'H', 'I'] pre_order traversal : ['G', 'C', 'D', 'E', 'I', 'H'] post_order traversal : ['E', 'D', 'C', 'H', 'I', 'G'] deleted alphabet : D in_order traversal : ['C', 'E', 'G', 'H', 'I'] pre_order traversal : ['G', 'C', 'E', 'I', 'H'] post_order traversal : ['E', 'C', 'H', 'I', 'G'] deleted alphabet : C in_order traversal : ['E', 'G', 'H', 'I'] pre_order traversal : ['G', 'E', 'I', 'H'] post_order traversal : ['E', 'H', 'I', 'G'] deleted alphabet : E in_order traversal : ['G', 'H', 'I'] pre_order traversal : ['G', 'I', 'H'] post_order traversal : ['H', 'I', 'G'] deleted alphabet : G in_order traversal : ['H', 'I'] pre_order traversal : ['I', 'H'] post_order traversal : ['H', 'I'] deleted alphabet : I in_order traversal : ['H'] pre_order traversal : ['H'] post_order traversal : ['H'] deleted alphabet : H Root not Found. in_order traversal : ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] pre_order traversal : ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H'] post_order traversal : ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'] Target not Found in_order traversal : ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'] pre_order traversal : ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H'] post_order traversal : ['A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'] | cs |
red black tree
binary search tree의 최악의 경우를 방지하기 위해서 red, black이란 색깔을 더하여 최악의 경우를 방지하는 방법입니다.
red black tree의 특성은 다음과 같습니다.
1. 각 노드는 red 혹은 black이고,
2. 루트 노드는 black이고,
3. 모든 리프노드 (즉, NIL 노드)는 black이고,
4. red 노드의 자식노드들은 전부 black이고(즉, red 노드는 연속되어 등장하지 않는다.)
5. 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 갯수의 black 노드가 존재한다.
색깔 추가 후 delete 시 고려해야할 부분이 하나 추가된 정도라 따로 구현하진 않겠습니다. (사실 귀찮음...)
ref
'* Computer Science > Algorithm' 카테고리의 다른 글
| unit 5. dfs/bfs (0) | 2017.03.07 |
|---|---|
| unit 4. hashing (0) | 2017.03.03 |
| Unit 3. heap sort (0) | 2017.02.09 |
| Unit 2. powerset (0) | 2017.02.07 |
| Unit 3. 들어가기 앞서 (0) | 2017.01.29 |