1.1. Before Refactoring ¶
~cpp class BinartSearchTree: def __init__(self): self.root = Node() def makeChildren(self, aRoot): aRoot.left = Node() aRoot.right = Node() def setNode(self, aNode, aKey): aNode.setKey(aKey) def getNode(self, aNode, aKey): if aNode.key == aKey or aNode.key == -1: return aNode elif aNode.key > aKey: return self.getNode( aNode.left, aKey ) else: return self.getNode( aNode.right, aKey ) def search(self, aRoot, aKey): if aRoot == None or aRoot.key == -1: return False elif aRoot.key == aKey: return True elif aRoot.key > aKey: return self.search( aRoot.left, aKey ) else: return self.search( aRoot.right, aKey ) def insert(self, aRoot, aKey): if self.search( aRoot, aKey ) == False: node = self.getNode(aRoot, aKey) self.setNode( node, aKey ) self.makeChildren( node ) return True return False def delete(self, aRoot, aKey): if self.search( aRoot, aKey ) == True: node = self.getNode(aRoot, aKey) ## if self.getNumofChildren( node ) == 0: ## self.setNode(node, -1) ## elif self.getNumofChildren( node ) == 1: ## child = self.getSingleChild(node) ## self.replace(node, child) if node.numofChildren() == 0: self.setNode(node, -1) elif node.numofChildren() == 1: child = self.getSingleChild(node) self.replace(node, child) else: largest = self.getLargest( node.left ) child = self.getSingleChild( largest ) self.setNode( node, largest.key ) self.replace( largest, child ) return True return False def getNumofChildren( self, aNode ): count = 0 if aNode.left.key != -1: count += 1 if aNode.right.key != -1: count += 1 return count def getSingleChild( self, aNode ): if aNode.left.key != -1 and aNode.right.key != -1: return None elif aNode.left.key != -1: return aNode.left else: return aNode.right def replace( self, aRoot, aChild ): aRoot.key = aChild.key aRoot.left = aChild.left aRoot.right = aChild.right def getLargest( self, aRoot ): node = aRoot while ( aRoot.right.key != -1 ): node = aRoot.right aRoot = aRoot.right return node class Node: def __init__(self, aKey = -1): self.setKey(aKey) self.left = None self.right = None def setKey(self, aKey): self.key = aKey def numofChildren(self): count = 0 if self.left.key != -1: count += 1 if self.right.key != -1: count += 1 return count ######################################################################### import unittest class BinartSearchTreeTestCase(unittest.TestCase): def testMakeChildren(self): bst = BinartSearchTree() self.assertEquals(bst.root.left, None) self.assertEquals(bst.root.right, None) bst.makeChildren(bst.root) self.assertNotEquals(bst.root.left, None) self.assertNotEquals(bst.root.right, None) def testSearch(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.setNode(bst.root, 2) bst.setNode(bst.root.left, 1) bst.setNode(bst.root.right, 3) self.assertEquals(bst.search(bst.root, 1), True) self.assertEquals(bst.search(bst.root, 5), False) def testInsert(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.setNode(bst.root, 2) bst.insert(bst.root, 1) self.assertEquals(bst.search(bst.root, 1), True) self.assertEquals(bst.insert(bst.root, 1), False) bst.insert(bst.root, 5) self.assertEquals(bst.search(bst.root, 5), True) ## def testGetNumofChildren(self): ## bst = BinartSearchTree() ## bst.makeChildren(bst.root) ## bst.setNode(bst.root, 20) ## ## bst.insert(bst.root, 10) ## bst.insert(bst.root, 5) ## bst.insert(bst.root, 25) ## bst.insert(bst.root, 22) ## ## self.assertEquals(bst.getNumofChildren( bst.root ), 2 ) def testGetSingleChild(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.setNode(bst.root, 20) bst.insert(bst.root, 10) bst.insert(bst.root, 5) bst.insert(bst.root, 25) self.assertEquals(bst.getSingleChild( bst.root), None) self.assertEquals(bst.getSingleChild( bst.root.left).key, 5) def testReplace(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.setNode(bst.root, 20) bst.insert(bst.root, 10) root = bst.root child = bst.getSingleChild( bst.root ) bst.replace( root, child ) self.assertEquals( bst.root.key , 10 ) self.assertEquals( bst.root.left.key , -1 ) self.assertEquals( bst.root.left.left , None ) def testGetLargest(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.setNode(bst.root, 20) bst.insert(bst.root, 22) bst.insert(bst.root, 21) bst.insert(bst.root, 25) self.assertEquals( bst.getLargest( bst.root ).key, 25 ) def testDelete(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.setNode(bst.root, 20) bst.insert(bst.root, 10) bst.insert(bst.root, 5) bst.insert(bst.root, 25) bst.insert(bst.root, 22) self.assertEquals(bst.delete(bst.root, 11), False) self.assertEquals(bst.delete(bst.root, 5), True) self.assertEquals(bst.search(bst.root, 5), False) #################################################################### self.assertEquals(bst.delete(bst.root, 25), True) self.assertEquals(bst.search(bst.root, 25), False) self.assertEquals( bst.root.key , 20 ) self.assertEquals( bst.root.left.key , 10 ) self.assertEquals( bst.root.right.key , 22) #################################################################### self.assertEquals( bst.delete( bst.root, 20 ), True ) self.assertEquals( bst.search( bst.root, 20 ), False ) self.assertEquals( bst.root.key, 10) self.assertEquals( bst.root.right.key, 22) self.assertEquals( bst.root.left.key, -1) if __name__ == '__main__': unittest.main()
1.2. After Rafactoring ¶
~cpp class BinartSearchTree: def __init__(self): self.root = Node() def makeChildren(self, aRoot): aRoot.left = Node() aRoot.right = Node() def getNode(self, aNode, aKey): if aNode.key == aKey or aNode.key == -1: return aNode elif aNode.key > aKey: return self.getNode( aNode.left, aKey ) else: return self.getNode( aNode.right, aKey ) def search(self, aRoot, aKey): if aRoot == None or aRoot.key == -1: return False elif aRoot.key == aKey: return True elif aRoot.key > aKey: return self.search( aRoot.left, aKey ) else: return self.search( aRoot.right, aKey ) def insert(self, aRoot, aKey): if self.search( aRoot, aKey ) == False: node = self.getNode(aRoot, aKey) node.setNode( aKey ) self.makeChildren( node ) return True return False def delete(self, aRoot, aKey): if self.search( aRoot, aKey ) == True: node = self.getNode(aRoot, aKey) if node.numofChildren() == 0: node.setNode( -1 ) elif node.numofChildren() == 1: child = node.getSingleChild() node.replace( child ) else: largest = node.left.getLargest() child = largest.getSingleChild() node.setNode( largest.key ) largest.replace( child ) return True return False class Node: def __init__(self, aKey = -1): self.setNode(aKey) self.left = None self.right = None def setNode(self, aKey): self.key = aKey def numofChildren(self): count = 0 if self.left.key != -1: count += 1 if self.right.key != -1: count += 1 return count def getSingleChild(self): if self.left.key != -1 and self.right.key != -1: return None elif self.left.key != -1: return self.left else: return self.right def replace(self, aNode): self.key = aNode.key self.left = aNode.left self.right = aNode.right def getLargest( self ): node = self right = self.right while ( right.key != -1 ): node = self.right right = right.right return node ######################################################################### import unittest class BinartSearchTreeTestCase(unittest.TestCase): def testMakeChildren(self): bst = BinartSearchTree() self.assertEquals(bst.root.left, None) self.assertEquals(bst.root.right, None) bst.makeChildren(bst.root) self.assertNotEquals(bst.root.left, None) self.assertNotEquals(bst.root.right, None) def testSearch(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.root.setNode( 2 ) bst.root.left.setNode( 1 ) bst.root.right.setNode( 3 ) self.assertEquals(bst.search(bst.root, 1), True) self.assertEquals(bst.search(bst.root, 5), False) def testInsert(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.root.setNode( 2 ) bst.insert(bst.root, 1) self.assertEquals(bst.search(bst.root, 1), True) self.assertEquals(bst.insert(bst.root, 1), False) bst.insert(bst.root, 5) self.assertEquals(bst.search(bst.root, 5), True) def testDelete(self): bst = BinartSearchTree() bst.makeChildren(bst.root) bst.root.setNode( 20 ) bst.insert(bst.root, 10) bst.insert(bst.root, 5) bst.insert(bst.root, 25) bst.insert(bst.root, 22) self.assertEquals(bst.delete(bst.root, 11), False) self.assertEquals(bst.delete(bst.root, 5), True) self.assertEquals(bst.search(bst.root, 5), False) #################################################################### self.assertEquals(bst.delete(bst.root, 25), True) self.assertEquals(bst.search(bst.root, 25), False) self.assertEquals( bst.root.key , 20 ) self.assertEquals( bst.root.left.key , 10 ) self.assertEquals( bst.root.right.key , 22) #################################################################### self.assertEquals( bst.delete( bst.root, 20 ), True ) self.assertEquals( bst.search( bst.root, 20 ), False ) self.assertEquals( bst.root.key, 10) self.assertEquals( bst.root.right.key, 22) self.assertEquals( bst.root.left.key, -1) if __name__ == '__main__': unittest.main()
2.1. 황재선 ¶
- 뭔가 이상하게 동작하는 듯...
- 오류 있으면 적어주세요~
- 노드 모두 삭제하면 에러.
- 할일 : Delete 함수 리펙토링하기, parent 포인터 없애기
~cpp #include <iostream> using namespace std; struct Node { Node * left; int key; Node * right; Node * parent; }; void initNode(Node * aRoot); Node * setNode(Node * p, int aNum); void Insert(Node * aRoot, int aNum); void Delete(Node * aRoot, int aNum); Node * Search(Node * aRoot, int aNum); void DeleteAllNode(Node * aRoot); void printKeys(Node * aRoot); int main() { Node * root = new Node(); initNode(root); root->key = -1; int number; int choice; while(true) { cout << "1. Insert " << endl; cout << "2. Delete " << endl; cout << "3. Search " << endl; cout << "4. Quit " << endl; cin >> choice; if (choice == 4) { DeleteAllNode(root); return 0; } cout << "숫자 입력" << endl; cin >> number; switch(choice) { case 1: Insert(root, number); break; case 2: Delete(root, number); break; case 3: Search(root, number); break; } printKeys(root); cout << "\n"; } } void initNode(Node * aRoot) { aRoot->left = NULL; aRoot->key = 0; aRoot->right = NULL; aRoot->parent = NULL; } Node * setNode(Node * p, int aNum) { Node * newNode = new Node(); initNode(newNode); newNode->key = aNum; newNode->parent = p; return newNode; } void Insert(Node * aRoot, int aNum) { Node * ptr = Search(aRoot, aNum); if (ptr->key == -1) { ptr->key = aNum; cout << aNum << "을 Tree에 추가" << endl; return ; } if (ptr->key == aNum) cout << "Error" << endl; else { if (ptr->key > aNum) ptr->left = setNode(ptr, aNum); else if (ptr->key < aNum) ptr->right = setNode(ptr, aNum); cout << aNum << "을 Tree에 추가" << endl; } } Node * Search(Node * aRoot, int aNum) { while (true) { if (aRoot->key == aNum) { cout << aNum << "은 Tree에 있습니다." << endl; return aRoot; } else if (aRoot->key > aNum) { if (aRoot->left != NULL) aRoot = aRoot->left; else break; } else if (aRoot->key < aNum) { if (aRoot->right != NULL) aRoot = aRoot->right; else break; } } cout << aNum << "은 Tree에 없습니다." << endl; return aRoot; } void Delete(Node * aRoot, int aNum) { Node * ptr = Search(aRoot, aNum); Node * parent = ptr->parent; if (ptr->key != aNum) cout << "Error" << endl; else { cout << aNum << "삭제" << endl; if (ptr->left == NULL && ptr->right == NULL) // leaf node { if (ptr->parent == NULL) { delete ptr; return ; } if (parent->left == ptr) { parent->left = NULL; } else if (parent->right == ptr) { parent->right = NULL; } } else if (ptr->left != NULL && ptr->right == NULL) // single left child { if (ptr->parent == NULL) { ptr->key = ptr->left->key; delete ptr->left; ptr->left = NULL; return ; } if (parent->left == ptr) parent->left = ptr->left; else if (parent->right == ptr) parent->right = ptr->left; ptr->left->parent = parent; } else if (ptr->left == NULL && ptr->right != NULL) // single right child { if (ptr->parent == NULL) { ptr->key = ptr->right->key; delete ptr->right; ptr->right = NULL; return ; } if (parent->left == ptr) parent->left = ptr->right; else if (parent->right == ptr) parent->right = ptr->right; ptr->right->parent = parent; } else if (ptr->left != NULL && ptr->right != NULL) // two child { Node * temp = ptr; ptr = ptr->right; int count = 0; while(ptr->left != NULL) { count++; ptr = ptr->left; } temp->key = ptr->key; if (count == 0) temp->right = NULL; else ptr->parent->left = NULL; } delete ptr; } } void DeleteAllNode(Node * aRoot) { if (aRoot) { DeleteAllNode(aRoot->left); DeleteAllNode(aRoot->right); delete aRoot; } } void printKeys(Node * aRoot) { if (aRoot) { printKeys(aRoot->left); cout << "* "; cout << aRoot->key; printKeys(aRoot->right); } }