Balanced Binary Search Tree In Python - Unit Test Module

• Tweet
• 

"""
Unit test cases for balanced binary tree search
updated 01/06/11 with tests for deletion
"""

from bbst import *
import unittest
import random
class TestEmptyTreeFunctions(unittest.TestCase):
    def setUp(self):
        self.emptyTree = bbstree()
    # lookup in an empty tree returns None
    def test_lookup(self):
        self.assertEqual(None, self.emptyTree.lookup(1))
    # height of an empty tree is zero
    def test_height(self):
        self.assertEqual(0,self.emptyTree.height())
    # scan over empty tree returns nothing
    def test_scan_f(self):
        f = []
        for t in self.emptyTree.forward():
            f.append(t.key)
        self.assertEqual(f,[])
    def test_scan_b(self):
        f = []
        for t in self.emptyTree.reverse():
            f.append(t.key)
        self.assertEqual(f,[])
    # inserting into an empty tree returns no value but the lookup
    # should then work and height should be 1.
    def test_insert(self):
        self.emptyTree.insert(1,'waka')
        self.assertEqual(self.emptyTree.height(), 1)
        self.assertEqual(self.emptyTree.lookup(1).value, 'waka')

class TestTreeFunctions(unittest.TestCase):
    # setup: create a 15-item tree from [0..15]
    def setUp(self):
        self.Tree = bbstree()
        self.datalist = [x for x in range(15)]
        for x in self.datalist:
            self.Tree.insert(x,x*10)
    # make sure all the items can be found
    def test_lookup(self):
        for x in self.datalist:
            t = self.Tree.lookup(x)
            self.assertTrue(None != t)
            self.assertTrue(t.value == x*10)
    def test_scan(self):
        # make sure forward scan returns all but only the items that went in
        f = []
        for t in self.Tree.forward():
            f.append(t.key)
        self.assertEqual(self.datalist,f)
        # ditto reverse scan
        f = []
        for t in self.Tree.reverse():
            f.append(t.key)
        self.datalist.reverse()
        self.assertEqual(self.datalist,f)
        # check for proper balance
    def test_height(self):
        self.assertEqual(self.Tree.height(),4)
        self.Tree.insert(15,150)
        self.assertEqual(self.Tree.height(),4)
class TestDeleting(unittest.TestCase):
   # setup: create a 15-item tree from [0..15]
    def setUp(self):
        self.Tree = bbstree()
        self.datalist = [x for x in range(15)]
        for x in self.datalist:
            self.Tree.insert(x,x*10)

    def test_delete(self):
        for x in self.datalist:
            self.Tree.delete(x)
            t = self.Tree.lookup(x)
            self.assertTrue(t==None)
        self.assertEqual(self.Tree.height(),0)

class TestLoadingTree(unittest.TestCase):
    # for realistic loading use a shuffled list of 8192 ints
    def setUp(self):
        self.Tree = bbstree()
        self.datalist = [x for x in range(8192)]
        random.shuffle(self.datalist)
    def test_load(self):
        # load the tree, check for reasonable balance
        for x in range(len(self.datalist)):
            self.Tree.insert(self.datalist[x], x)
        self.assertTrue(self.Tree.height()<=11)
        # make sure all can still be found
        for x in range(len(self.datalist)):
            t = self.Tree.lookup(self.datalist[x])
            self.assertTrue(t != None)
    
if __name__ == '__main__':
    suite = unittest.TestLoader().loadTestsFromTestCase(TestEmptyTreeFunctions)
    unittest.TextTestRunner(verbosity=2).run(suite)
    suite = unittest.TestLoader().loadTestsFromTestCase(TestTreeFunctions)
    unittest.TextTestRunner(verbosity=2).run(suite)
    suite = unittest.TestLoader().loadTestsFromTestCase(TestDeleting)
    unittest.TextTestRunner(verbosity=2).run(suite)
    suite = unittest.TestLoader().loadTestsFromTestCase(TestLoadingTree)
    unittest.TextTestRunner(verbosity=2).run(suite)

Tags:
• balanced
• binary
• test
• Tree
• unit