Exercise 23: Ternary Search Trees

The final data structure we'll investigate is called a Ternary Search Tree (TSTree), and it's useful for quickly finding a string in a set of strings. It's similar to a BSTree but instead of two children it has three children, and each child is only a single character rather than an entire string. In the BSTree you had a left and right child for the "less-than" and "greater-than" branches of the tree. With a TSTree you have left, middle, and right branches for "less-than", "equal-to", and "greater-than" branches. This lets you take a string, break it into characters, and then walk the TSTree one character at a time until you find it or you run out.

The TSTree is effectively trading space for speed by breaking the set of possible keys you need to search into one character nodes. Each of these nodes will take up more space than the same keys in a BSTree, but this enables you to find keys by only comparing the characters in the key you want. With a BSTree you have to compare most of the characters in both the search key and node key once each node. With a TSTree you only compare each letter of the search key, and when you get to the end that's it.

The other thing that a TSTree is very good for is knowing when a key does not exist in the set. Imagine you have a key that's 10 characters long and you need to find it in a set of other keys, but you need to stop fast if the key does not exist. With a TSTree you could stop at one or two characters, reach the end of the tree, and know this key does not exist. You'll at most compare only 10 characters in the key to find this out, which is much fewer character comparisons than a BSTree would make. A BSTree could compare all the characters in a 10 character key once for every single node in the most pathological case (where the BSTree is basically a linked list) before deciding the key does not exist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class TSTreeNode(object):

    def __init__(self, key, value, low, eq, high):
        self.key = key
        self.low = low
        self.eq = eq
        self.high = high
        self.value = value


class TSTree(object):

    def __init__(self):
        self.root = None

    def _get(self, node, keys):
        key = keys[0]
        if key < node.key:
            return self._get(node.low, keys)
        elif key == node.key:
            if len(keys) > 1:
                return self._get(node.eq, keys[1:])
            else:
                return node.value
        else:
            return self._get(node.high, keys)

    def get(self, key):
        keys = [x for x in key]
        return self._get(self.root, keys)

    def _set(self, node, keys, value):
        next_key = keys[0]

        if not node:
            # what happens if you add the value here?
            node = TSTreeNode(next_key, None, None, None, None)

        if next_key < node.key:
            node.low = self._set(node.low, keys, value)
        elif next_key == node.key:
            if len(keys) > 1:
                node.eq = self._set(node.eq, keys[1:], value)
            else:
                # what happens if you DO NOT add the value here?
                node.value = value
        else:
            node.high = self._set(node.high, keys, value)

        return node

    def set(self, key, value):
        keys = [x for x in key]
        self.root = self._set(self.root, keys, value)