Ternary Search Trees

Question 1

Recall previous Data Structures:

(Balanced) Binary Search Tree (i.e. AVL or R-B Tree)

HashTable

Multiway Trie

Answer 1

Binary Search Tree : very (most) space efficient , but worst-time complexity of O(log n) . Can iterate over the elements in alphabetical order.

HashTable: not as space efficient as BST , but has average case run time complexity of O(k) and worst case O(n) (linked list). Elements in Hashtable is unordered, so iterating through HT is not meaningful (no alphabetical or descending/ascending) order.

MultiWayTrie: most time efficient with worst case O(k), but inefficient in terms of memory/space. Benefits include being able to iterate through each character unit of a lexicon. Autocomplete can be done with a pre-order traversal.

Question 2

Ternary Search Tree is the middle ground between MultiWay Tree and Binary Search Tree

TST first described by Jon Bentley and James Saxe

Answer 2

Ternary Search Tree has nodes arranged like a BST but with 3 children rather than just 2.

Each node represents a character. Each node has 3 children, left, right, and middle. Left child node is traverse looking for a character less than current, right child is traverse looking for character greater than current, and middle child is for matching of character.

Like MWT there is a boolean is_word label.

Question 3

MWT is defined by how it CONCATONATES edge labels along the path from root to a “word node”

Algorithm of traversal

Answer 3

If letter is less than node’s label: If node has a left child, traverse down to node’s left child. Otherwise, we have failed (key does not exist in this Ternary Search Tree)
If letter is greater than node’s label: If node has a right child, traverse down to node’s right child. Otherwise, we have failed (key does not exist in this Ternary Search Tree)
If letter is equal to node’s label: If letter is the last letter of key and if node is labeled as a “word node,” we have successfully found key in our Ternary Search Tree; if not, we have failed. Otherwise, if node has a middle child, traverse down to node’s middle child and set letter to the next character of key; if not, we have failed (key does not exist in this Ternary Search Tree)

Question 4

Pseudocode for find() in Ternary Search Tree

Answer 4

find(key): // return True if key exists in this TST, otherwise return False
    node = root node of the TST
    letter = first letter of key
    loop infinitely:
        // left child
        if letter < node.label:
            if node has a left child:
                node = node.leftChild
            else:
                return False     // key cannot exist in this TST

        // right child
        else if letter > node.label:
            if node has a right child:
                node = node.rightChild
            else:
                return False     // key cannot exist in this TST

    // middle child
    else:
        if letter is the last letter of key and node is a word-node:
            return True      // we found key in this TST!
        else:
            if node has a middle child:
                node = node.middleChild
                letter = next letter of key
            else:
                return False // key cannot exist in this TST

Question 5

Ternary Search Tree: remove() algorithm

Answer 5

Is trivial given the find algorithm. Jsut perform the same find() algorithm and on the final character is the is_word flag true then turn it flase. No deletion.

No deletion since we do not know if node is extending to other nodes/letters/words that rely on it.

Question 6

Ternary Search Tree: insert()

Answer 6

Essentially the insert rides on the coattail of find and:

If you’re able to legally traverse through the tree for every letter of key (which implies key is a prefix of another word in the tree), simply label the node at which you end up as a “word node”

If you are performing the tree traversal and run into a case where you want to traverse left or right, but no such child exists, create a new left/right child labeled by the current letter of key, and then create middle children labeled by each of the remaining letters of key

If you run into a case where you want to traverse down to a middle child, but no such child exists, simply create middle children labeled by each of the remaining letters of key

Question 7

Similar to BST , Ternary Search Trees are affected by the initial/first element inserted

Answer 7

The first insertion will affect the shape of the tree and how successive insertions will cause the weight of the left or right side to be.

Question 8

Describe the ascending In-Order Traversal PsuedoCorde

Answer 8

(incomplete) Ascending InOrder Traversal:

for leftChild of Node:
if node is Word -> output world labeled by path.

for middleChild of Node