2
\$\begingroup\$

I have implemented a Ternary search tree. It works well. But if you think something needs to be improved, say it. This code was tested in Python 3.7.4.

class Node(object):

    def __init__(self, character):
        self.character = character
        self.leftNode = None
        self.middleNode = None
        self.rightNode = None
        self.value = 0

class TST(object):

    def __init__(self):
        self.rootNode = None

    def put(self,key,value):
        self.rootNode = self.putItem(self.rootNode, key, value, 0)

    def putItem(self, node, key, value, index):

        c = key[index]

        if node == None:
            node = Node(c)

        if c < node.character:
            node.leftNode = self.putItem(node.leftNode, key, value, index)
        elif c > node.character:
            node.rightNode = self.putItem(node.rightNode, key, value, index)
        elif index < len(key) - 1:
            node.middleNode = self.putItem(node.middleNode, key, value, index+1)
        else:
            node.value = value

        return node

    def get(self, key):

        node = self.getItem(self.rootNode, key, 0)

        if node == None:
            return -1

        return node.value

    def getItem(self, node, key, index):

        if node == None:
            return None

        c = key[index]

        if c < node.character:
            return self.getItem(node.leftNode, key, index)
        elif c > node.character:
            return self.getItem(node.rightNode, key, index)
        elif index < len(key) - 1:
            return self.getItem(node.middleNode, key, index+1)
        else:
            return node

if __name__ == "__main__":

    tst = TST()

    tst.put("apple",100)
    tst.put("orange",200)

    print( tst.get("orange") )
\$\endgroup\$
1
  • \$\begingroup\$ AlexV, Thanks for editing my question. \$\endgroup\$ – Brijesh Kalkani Oct 10 '19 at 11:41
5
\$\begingroup\$

Data structure-wise, it seems okay, and does what you're after.

Code-style wise, I see a few things:

  1. It's not quite PEP8, the coding style. Whilst you can read it, which is always good, there are tools to automatize the process, such as flake8, black. Most likely, your editor will have a plugin.

    This is include things like underscore_names in lieu of camelCasing.

    Note that this standard is a living document, and gets updated once in a while.

  2. None is a singleton in Python, and thus you can use the is keyword instead. Python relies on its id() function to get a hash of an object, and compare them. As None is a singleton, the hash is the same.

    So your line if node == None: could be if node is None.
    Going further this way, None evaluates to False in a test, so you could go if not node: (edit: as discussed with @Gloweye, it's indeed clearer and preferred to use the first variant).

  3. Python returns None when no value is being explicitly returned, whether you have no return in a function, or do a blank return.

These two lines taken together could then be:

if node is None:
    return

and would be considered idiomatic.

  1. Lastly, in Python3 (which you ought to be using), class definition have been revamped. The way you do it:
class TST(object):

is now:

class TST:

If you were inheriting from something, though, it would indeed be:

class TST(ParentClass):

Maybe what you could try next is to implement unit tests with unittest or pytest and see whether your structure holds on with more convoluted cases.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ In Python, if you're actively looking for None instead of falsy value in general, if node is None is preferred to if not node. This applies to this specific case. \$\endgroup\$ – Gloweye Oct 10 '19 at 14:07
  • 1
    \$\begingroup\$ You're right, and I abuse that behaviour. Thanks for the reminder! \$\endgroup\$ – Cyril D. Oct 10 '19 at 14:45
  • 1
    \$\begingroup\$ The point isn't for the computer running the code, it's for the programmer reading it. When they read if not node, they'll wander what node can be other than Node or None. if node is None instead shows you that Nodes and None are the only valid values. That makes it more readable, and especially here on CodeReview, therefore preferable. \$\endgroup\$ – Gloweye Oct 10 '19 at 15:00
  • \$\begingroup\$ Thank a lot Gloweye and Cyril D. to spend your valuable time to get the review of my code. Let me correct as per your suggestion and get back to you. Today I learned many coding fundamentals and styles from your suggestions. Thanks a lot once again. \$\endgroup\$ – Brijesh Kalkani Oct 10 '19 at 17:02
0
\$\begingroup\$

Docstring

You can document the behaviour of the method with a docstring

typing

You can add typing, to clarify for the caller what type the different arguments and variables are

TST.putItem

Apart from the name, which according to PEP-8 would be better as put_item, should not be an ordinary method of the TST. The self is only used as to recursively call the same method. This can be a helper method in the global namespace, or a staticmethod

The same comment goes for the GetItem

get

def get(self, key):

    node = self.getItem(self.rootNode, key, 0)

    if node == None:
        return -1

    return node.value

-1 is a bad sentinel value. How will the caller distinguish between a node.value of -1 or a non-existent key?

Better would be to either raise a KeyError if the value is not in the tree, or mimic the behaviour of dict.get(key\[, default_value\]), with an explicit default value.

tuple unpacking

Instead of explicitly sending the index with it, you can use tuple unpacking.


My take on your Ternary search tree:

With added typing hints, implementing the __getitem__ and __setitem__ magic methods.

The put_item and get_item can be put on the Node class as well. Which you choose is a matter of taste

import typing

V = typing.TypeVar("V")


class Node:
    def __init__(
        self, character: str, value: typing.Optional[V] = None
    ) -> None:
        self.character: str = character
        self.left: typing.Optional[Node] = None
        self.middle: typing.Optional[Node] = None
        self.right: typing.Optional[Node] = None
        self.value: typing.Optional[V] = value


class TernarySearchTree:
    def __init__(self) -> None:
        self.root: typing.Optional[Node] = None

    def __setitem__(
        self, key: typing.Union[str, typing.Iterable[str]], value: V
    ) -> None:
        self.root = TernarySearchTree.put_item(self.root, key=key, value=value)

    put = __setitem__

    @staticmethod
    def put_item(
        node: typing.Optional[Node],
        key: typing.Union[str, typing.Iterable[str]],
        value: V,
    ) -> Node:
        c: str
        c, *rest = key

        if node is None:
            node = Node(c)

        if c < node.character:
            node.left = TernarySearchTree.put_item(
                node=node.left, key=key, value=value
            )
        elif c > node.character:
            node.right = TernarySearchTree.put_item(
                node=node.right, key=key, value=value
            )
        elif rest:
            node.middle = TernarySearchTree.put_item(
                node=node.middle, key=rest, value=value
            )
        else:
            node.value = value
        return node

    def __getitem__(self, key: typing.Union[str, typing.Iterable[str]]) -> V:
        return TernarySearchTree.get_item(self.root, key=key).value

    def get(
        self,
        key: typing.Union[str, typing.Iterable[str]],
        default_value: typing.Optional[V] = None,
    ) -> typing.Optional[V]:
        try:
            return self[key]
        except KeyError:
            return default_value

    @staticmethod
    def get_item(
        node: typing.Optional[Node],
        key: typing.Union[str, typing.Iterable[str]],
    ) -> Node:
        if node is None:
            raise KeyError

        c: str
        c, *rest = key

        if c == node.character and not rest:
            return node

        if c < node.character:
            return TernarySearchTree.get_item(node=node.left, key=key)
        if c > node.character:
            return TernarySearchTree.get_item(node=node.right, key=key)
        return TernarySearchTree.get_item(node=node.middle, key=rest)


if __name__ == "__main__":

    tst = TernarySearchTree()

    tst.put("apple", 100)
    tst["orange"] = 200
    tst.put("orb", 150)

    print(tst["orange"])
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.