Improving Balance of Ternary Search Tries

mgcadmin 08-21-2026

Ternary Search Tries are one of my favorite data structures. They're also somewhat of a black-sheep data structure in that while they are quite useful, theyre often shoved to the side in favor of more main stream data structures like hash tables. They are designed explicitly for string keys, so right off the bat they have a loss of generality compared to other symbol table or set data structures.

This sacrifice comes with an upside of course, when it comes to memory efficient trie structures TST's cant be beat, unfortunately certain operations which are constant time operations in array based tries, we have to accept logarithmic access times in TSTs. 

This brings us to the topic of todays post: What can we do to help TST's perform at their best? In todays post we're going to explore a few options, from managing balance through rotations to pre-sorting our data for building optimal TST's, todays post is all about the ternary search trie, so lets get to it.

Keeping Ternary Search Tries Balanced

When it comes to keeping ternary search tries balanced there are two main strategies and which one is better is dependent on the use case. If your search tree will be built once and then remain mostly (or entirely) static, then we can order the insertion of keys to build an optimal tree from the beginning.

    private Node put(Node x, String key, int d) {
        char c = key.charAt(d);
        if (x == null) { x = new Node(c); }
        if (c < x.c) x.left = put(x.left, key, d);
        else if (c > x.c) x.right = put(x.right, key, d);
        else if (d < key.length() - 1) x.mid = put(x.mid, key, d+1);
        else x.eos = true;
        return x;
    }

 If we cannot pre-sort the keys or if we intend for the tree to be highly dynamic then we will need more flexible "on line" algorithms. These algorithms, like those for most balanced search trees, make use of rotations to keep the tree balanced. 

Building Optimal TST's From Pre-Sorted Input

Being a relative of binary search trees, they suffer from the same order-sensitive input issues where performance devolves to little more than a linked list if inserted in strictly increasing or decreasing order, (with bitonic insertions not beign much better). However, we can also exploit their similarities by using the same trick for building our tree from a sorted list, with a simple divide and conquer algorithm.

    private void balanced(ArrayList<String> strings, int l, int r) {
        if (l <= r) {
            int m = (l+r)/2;
            head = put(head, strings.get(m), 0);
            balanced(strs, l, m-1);
            balanced(strs, m+1, r);
        }
    }
    public void putBalanced(ArrayList<String> strs) {
        strs.sort((a,b) -> a.compareTo(b));
        balanced(strs, 0, strs.size()- 1);
    }

As you can see, this is only really applicable if you have all, or at least most of your keys available ahead of time. While its only applicable sometimes, what it lacks in generality it makes up for in simplicity. For something a bit more... powerful lets turn our attention to some on-line algorithms.

TST's with AVL Balanced sub-trees

Once again we will exploit the similarity between TST and BST's. This time however we will do it by keeping sub-trees balanced using AVL rules. This strategy has us keep the the difference in height between left and right subtrees at no more than one, otherwise we adjust their heights through rotations until the condition holds. 

    private Node put(Node x, String key, Character v, int d) {
        char c = key.charAt(d);
        if (x == null) { x = new Node(c); }
        if (c < x.c) {
            x.left = put(x.left, key, v, d);
        } else if (c > x.c) {
            x.right = put(x.right, key, v, d);
        } else if (d < key.length() - 1) {
            x.mid = put(x.mid, key, v, d+1);
        } else { 
            x.val = v; x.eos = true; 
        }
        x.height = 1 + Math.max(height(x.left), height(x.right));
        if (height(x.left) > height(x.right) + 1)
             x = rightRotate(x);
        if (height(x.right) > height(x.left) + 1)
            x = leftRotate(x);
        return x;
    }

We have to be careful to only rotate the subtrees while leaving the "trunk" untouched so as to keep the actual keys themselves intact. In other words, we can change where a tree is rooted from, but not what is rooted from that location. The same balancing logic used for insertion can be extended to the deletion algorithm as well:

    private Node erase(Node x, String key, int d) {
        if (x == null)
            return x;
        Character c = key.charAt(d);
        if (c < x.c) {
            x.left = erase(x.left, key, d);
        } else if (c > x.c) {
            x.right = erase(x.right, key, d);
        } else {
            if (d == key.length() - 1) {
                x.eos = false;
            } else {
                x.mid = erase(x.mid, key, d+1);
            }
        } 
         x.height = 1 + Math.max(height(x.left), height(x.right));
        if (height(x.left) > height(x.right) + 1)
            x = rightRotate(x);
        if (height(x.right) > height(x.left) + 1)
            x = leftRotate(x);
        if (x.left != null || x.right != null || x.mid != null)
            return x;
        return null;
    }

The pre-sorted divide and conquer algorithm can also be combined with AVL balancing for an extra level of balancing. 

---