Una banale implementazione di un Albero Binario di Ricerca con Test TDD

ABR.py

# -*- coding: utf-8 -*-

class Nodi(object):
    """Implementazione dei nodi per un ABR"""
    def __init__(self, value, father):
        super(Nodi, self).__init__()
        self.value = value
        self.father = father
        self.DX = None
        self.SX = None

    def __str__(self):
        return str(self.value)

class Albero(object):
    """Implementazione di un ABR"""
    def __init__(self):
        super(Albero, self).__init__()      #Un po inutile...
        self.__leaves_tot = 1                 #Contando la radice

    def __len__(self):
        return self.__leaves_tot

    def new_node(self, value, radice):
        if radice == value:     #Se il valore è gia nell' albero 
            return False        #non lo inserisco

        if value > radice.value:    #Funzione ricorsiva per inserire i nodi necessari
            if radice.DX:
                return self.new_node(value, radice.DX)
            else:
                radice.DX = Nodi(value, radice)
                self.__leaves_tot += 1
                return radice.DX

        if value < radice.value:
            if radice.SX:
                return self.new_node(value, radice.SX)
            else:
                radice.SX = Nodi(value, radice)
                self.__leaves_tot += 1
                return radice.SX

    def find_value(self, value, radice):
        """
        Funzione ricorsiva per verificare la presenza di un valore nel albero
        Forse sarebbe meglio una funzione iterattiva...
        """
        if value == radice.value:
            return radice

        if value > radice.value:
            if radice.DX:
                return self.find_value(value, radice.DX)
            else:
                return False

        if value < radice.value:
            if radice.SX:
                return self.find_value(value, radice.SX)
            else:
                return False


    def visite(self, radice):
        """
        Non testato
        """
        if radice != None:
            self.visite(radice.SX)
            self.visite(radice.DX)

    def find_maximun(self, radice):
        while radice.DX:
            radice = radice.DX
        return radice

    def find_minimun(self, radice):
        while radice.SX:
            radice = radice.SX
        return radice

    def cut(self, leaves, radice):
        leaves = self.find_value(leaves, radice)
        if leaves:
            if not leaves.DX and not leaves.SX:
                if leaves.father.value > leaves.value:
                    leaves.father.SX = None
                else:
                    leaves.father.DX = None
            
            elif not leaves.DX or not leaves.SX:
                if leaves.DX:
                    if leaves.value > leaves.father.value:
                        leaves.father.DX = leaves.DX
                    else:
                        leaves.father.SX = leaves.DX
                else:
                    if leaves.value > leaves.father.value:
                        leaves.father.DX = leaves.SX
                    else:
                        leaves.father.SX = leaves.SX

            else:
                successore = self.find_minimun(leaves)
                leaves, successore = successore, leaves
                self.cut(successore, leaves)
                


if  __name__ == '__main__':
    pass

test_Albero_Binario.py

import unittest
import random

from ABR import Albero, Nodi

class TestAlberoBinario(unittest.TestCase):
    rastrello = list()
    radice = Nodi(5, None)
    Tree = Albero()
    primo_destro = Tree.new_node(8, radice)
    
    for i in xrange(100):
        germoglio = random.randint(20, 100)
        foglia = Tree.new_node(random.randint(3, 100), radice)
        if foglia:
            rastrello.append(germoglio)

    def setUp(self):
        self.marcatore = 120
        self.Tree.new_node(self.marcatore, self.radice)

        self.DX_marcatore = 130
        self.Tree.new_node(self.DX_marcatore, self.radice)
        
        self.MAX_DX = 1000
        self.Tree.new_node(self.MAX_DX, self.radice)
        
        self.MIN_SX = 1
        self.Tree.new_node(self.MIN_SX, self.radice)
        
        self.TO_CUT = 125
        self.Tree.new_node(self.TO_CUT, self.radice)
        
        self.nodi = len(self.rastrello) + 7

    def test_find_value(self):
        self.assertTrue(self.Tree.find_value(self.marcatore, self.radice))

    def test_no_same_value(self):
        self.assertFalse(self.Tree.new_node(self.marcatore, self.radice))

    def test_minus_left(self):
        self.assertTrue(self.radice.value > self.radice.SX.value)

    def test_plus_right(self):
        self.assertTrue(self.radice.value < self.radice.DX.value)

    def test_count_leaves(self):
        self.assertEqual(len(self.Tree), self.nodi)

    def test_find_maximun(self):
        self.assertEqual(self.Tree.find_maximun(self.radice).value, self.MAX_DX)

    def test_find_minimun(self):
        self.assertEqual(self.Tree.find_minimun(self.radice).value, self.MIN_SX)

    def test_cut_no_child_leaves(self):
        self.Tree.cut(self.marcatore, self.radice)
        self.assertFalse(self.Tree.find_value(self.marcatore, self.radice))

    def test_cut_one_child_leaves(self):
        self.Tree.cut(self.marcatore, self.radice)
        self.assertFalse(self.Tree.find_value(self.marcatore, self.radice))
        self.assertTrue(self.Tree.find_value(self.DX_marcatore, self.radice))

    def test_cut_two_child_leaves(self):
        self.Tree.cut(self.TO_CUT, self.radice)
        self.assertFalse(self.Tree.find_value(self.TO_CUT, self.radice))
        self.assertTrue(self.Tree.find_value(self.DX_marcatore, self.radice))
        self.assertTrue(self.Tree.find_value(self.MAX_DX, self.radice))


if __name__ == '__main__':
    unittest.main()