Python beginner's tree with unit tests

Question

I have implemented a tree in Python. However, due to my lack of experience with Python, I am not able to judge the overall quality of my code.

import unittest
from datetime import *
from gc import *

RET_NO = 0
RET_YES = 1
RET_MAYBE = 0.5 # haha :)


class Tree(object):
    """
    Mutable abstract data type for arbitrary data with O(N) access on elements.
    """
    def __init__(self):
        super(Tree, self).__init__()
        self.root = None

    def insert(self, element):

        if self.root:
            self.root.insert(element)
        else:
            self.root = Node(element)

    def contains(self, element):
        if self.root is None:
            print 'WARN: Contains() called before elements were inserted!!'
            raise Exception()

        return self.root.contains(element) if self.root else RET_NO

    def size(self):
        return self.root.size() if self.root else 0

    def bulk_insert(self, elements=[]):
        while len(elements):
            self.insert(element[0])
            elements = elements[1:]

class Node(object):
    """
    Node class to be used in Tree instances.
    """
    def __init__(self, element):
        super(Node, self).__init__()
        self.element = element
        self.left = None
        self.right = None

    def insert(self, element):
        if self.element == element:
            return
        if element < self.element:
            if self.left:
                self.left.insert(element)
            else:
                self.left = Node(element)
        else:
            if self.right:
                self.right.insert(element)
            else:
                self.right = Node(element)
        raise Exception('Should never reach this line!')

    def contains(self, element):
        if self.element == element:
            return RET_YES
        if element < self.element:
            if self.left:
                return self.left.contains(element)
            else:
                return RET_NO
        else:
            if self.right:
                return self.right.contains(element)
            else:
                return RET_NO
        raise Exception('Should never reach this line!')

    def size(self):
        """
        Return size
        """
        left_size = self.left.size() if self.left else 0
        right_size = self.right.size() if self.right else 0
        return left_size + right_size + 1

class TreeTest(unittest.TestCase):

    def setUp(self):
        # no setup required yet
        pass

    def tearDown(self):
        # leave memory in a clean state
        gc.collect()


    def test_1(self):
        #tree = Tree()
        #self.assertEqual(tree.size(), 0)
        #tree.insert(10)
        #self.assertEqual(tree.size(), 10)
        self.assertTrue(True)

    def test_2(self):
        start = datetime.now()

        elements = []
        for i in range(1000000):
            elements += [i]

        tree = Tree()
        # tree should be empty
        for i in elements:
            self.assertEqual(tree.contains(i), RET_NO)
        # fill tree
        for i in elements:
            tree.insert(i)
        # tree should be full
        for i in elements:
            self.assertEqual(tree.contains(i), RET_YES)

        end = datetime.now()
        elapsed = end - start
        # must not take longer than a minute
        self.assertTrue(elasped.total_seconds() < 60)

    def test_3(self):
        tree = Tree()
        try:
            tree.contains(1)
            # should have thrown an exception -> test failed
            self.assertTrue(False)
        except Exception, ValueError:
            # expected to raise an Exception -> test should pass
            self.assertTrue(True)

kyrill · Accepted Answer · 2017-04-09 15:40:38Z

Don't do from something import *.

Either import what you need:
```
from datetime import datetime
```
Or import the entire module and use qualified names:
```
import datetime
...
    start = datetime.datetime.now()
```
Importing everything is dangerous because it can shadow already existing names. One such example:
```
import datetime
from datetime import *
# `datetime` as a class shadows `datetime` as a module
```
You might want to do a little reading on the subject.

This whole thing makes no sense:
```
RET_NO = 0
RET_YES = 1
RET_MAYBE = 0.5 # haha :)
```
Instead of RET_YES / RET_NO you sould use True and False.

You don't have to call super(...).__init__ if the class only inherits from object.

Why do you print something to stdout and then raise an empty exception?

Instead of

print 'WARN: Contains() called before elements were inserted!!'
raise Exception()

you should do

raise Exception('contains() called on empty tree')

In the method Tree.contains, you already checked if self.root is None, so this
```
return self.root.contains(element) if self.root else RET_NO
```
can be simplified to this
```
return self.root.contains(element)
```

Instead of contains you can define the __contains__ method. Then you can use the in keyword:
```
return element in self.root
```
Although in this particular case it's less readable, so it's probably better to just stick with contains.

Method Tree.bulk_insert is just wrong. There's no point in having an empty list for a default argument. In the for loop you modify the list while iterating over it, and on each iteration you call the len function. Why? Even the C-style
```
for i in range(len(elements)):
    self.insert(elements[i])
```
would have been better.

This is the way to do it in Python:
```
def bulk_insert(self, elements):
    for element in elements:
        self.insert(element)
```
That way elements doesn't have to be a list, it can be any iterable.

Does your tree have a special requirement that it cannot contain the same element twice? If not, then in Node.insert there should be no
```
if self.element == element:
    return
```

Remove unreachable statements. There's no point in having
```
raise Exception('Should never reach this line!')
```
in Node.contains, while having it in Node.insert effectively makes the method raise an exception in almost all cases. Actually if you fix the error mentioned in the previous point, it would be in completely all cases.

The comment
```
"""
Return size
"""
```
is pointless. The method itself is called size, so it's obvious that it returns size. Also, the name size is quite ambiguous to begin with. Either don't restate code in comments, or actually explain what the method does (eg. how do you compute the size). A more suitable name would be number_of_elements, or maybe something shorter but descriptive like nelems.

The docstring of Node states:
```
"""
Node class to be used in Tree instances.
"""
```
I'd say it can possibly be used in other classes than Tree, so don't create a tight coupling between the two, even if it's just in comments.

size can be a property:

@property
def size(self):
    ...

That way you won't have to call it:

left_size = self.left.size if self.left else 0

Even tests should be documented. Add docstrings explaining what do the test_* methods test. Your non-test code also lacks documentation.

The docstring of Tree says "O(N) access on elements". This is not quite true, for two reasons:
- your Tree and Node classes don't even allow you to access elements, they only allow you to check whether an element is present in the tree,
- \$O(n)\$ is the worst case; average asymptotic complexity is \$O(log(n))\$.

Have you by chance forgotten to implement a remove method? Or you just wanted an insert-only tree?

$$⸻$$

Stack Exchange Network

Python beginner's tree with unit tests

1 Answer 1

Your Answer

Hot Network Questions

Python beginner's tree with unit tests

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions