U E D R , A S I H C RSS
ZeroWiki

몸짱프로젝트/Binary Search Tree

1. Python version

  • 개 :
  • TDD , . ...
  • 고 .

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. C++ version

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);
	}
}


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:29:28
Processing time 0.0147 sec