imported>Unknown at 05:29, 7 February 2021

2021-02-07T05:29:28Z

New page

{| class="wikitable"
|-
| __TOC__
|}
== Python version ==
* 개발자 : 나휘동
* TDD를 쓰긴 썼는데, 테스트가 영 마음에 들지 않는다. 후...
* 다 만들고서 리펙토링을 했다.
=== Before Refactoring ===
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()
=== After Rafactoring ===
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()
== C++ version ==
=== [[황재선]] ===
* 뭔가 이상하게 동작하는 듯...
* 오류 있으면 적어주세요~
* 노드 모두 삭제하면 에러.
* 할일 : Delete 함수 리펙토링하기, parent 포인터 없애기
#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);
}
}

----
[[몸짱프로젝트]]

몸짱프로젝트/BinarySearchTree - Revision history

imported>Unknown at 05:29, 7 February 2021