Class questions: (1) slots (2) __ + method name

What is the function of “slots” in a class?

With a “get” method, why do we need “__get” method?

Does the “__” before “get” only for us or have a special meaning?

Could we use any other name for “__get” method?

class Node:
    __slots__ = '_item' , '_left' , '_right'

    def __init__ (self, item, left=None, right=None):
        self._item = item
        self._left = left
        self._right = right

class BinarySearchTree:

    def __init__ (self, root=None):
        self._root = root
    # Get methods
    def get(self, key):
        return self.__get(self._root, key);

    def __get(self, node, key): # helper
        if (node is None):
            return None
        if (key == node._item):
            return node._item
        if (key < node._item):
            return self.__get(node._left, key)
            return self.__get(node._right, key)

__slots__ is advanced and you probably shouldn’t bother with it unless you really need it. It is used to reduce memory consumption for objects by avoiding creating a __dict__ for storing attributes.

By default, instances have an internal dict for storing arbitrary attributes. Instead, we can declare up front what attributes are needed, and memory will be reserved for them directly instead of inside the internal dict.

So you could remove the __slots__ line from the Node class, and the only difference would be that the individual nodes would use a little more memory, and you could assign arbitrary attributes to them.

Names that start and end with double underscores __ are called dunder (Double UNDERscore) names, or just dunders. Dunders are reserved for special use by the Python interpreter.

Names that start with a single underscore are considered “private”. By convention, code outside of the Node class is supposed to not touch the Node private attributes.

Nodes that start with two underscores (but not end with them) are also considered private, but more so. The interpreter takes the name and automatically mangles it by inserting the name of the class, so to help avoid name clashes with subclasses.

All of this is considered moderately advanced so don’t worry about it if you find it hard to understand.

(But feel free to ask more questions if you wish.)

I think you could re-write the two classes in a simpler fashion without losing any functionality:

class Node:
    def __init__ (self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right

class BinarySearchTree:
    def __init__ (self, root=None):
        self.root = root

    def search(self, key):
        # Search the tree for the node containing the key.
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None:  # empty tree does not contain the key
            return None
        elif key == node.item:
            # Found it!
            return node
        elif (key < node.item):
            # Search the left subtree.
            return self._search(node.left, key)
            # Search the right subtree.
            return self._search(node.right, key)

I also changed the name “get” to search.

I removed the underscores from most of the names because this is a learning exercise and they really aren’t needed. Feel free to put them back if you wish.

The search() method (originally called “get”) takes one argument, the key to search for, and returns the node containing that key.

If order to find that node, it calls a second method _search. It has a leading underscore to tell you that only the BinaryTree class should use that method. This method does the work of actually inspecting each node and deciding whether or not it matches the key we are looking for.

That needs to be a second method because, unlike the search() method, it needs two arguments: the key to search for, and the current node where we are up to in the search.

1 Like