Category: Code

We’ve talked quite a bit about data structures in this series, although not as much in recent entries. We’ve seen lists and arrays, two of the most important structures around, but they both have a severe limitation: they’re linear. While that’s great for a lot of data that computer programs manipulate, there comes a time when you need to represent both the data and its organization, and that calls for something more substantial.

The tree is a data structure that represents a hierarchy. Like a real tree, it has a root. It has branches and leaves. And a collection of data trees is also called a “forest”. But those similarities are a bit artificial; the terms were chosen for the analogy. What these trees do isn’t much like the natural ones. To a programmer, however, they’re far more useful.

In the abstract

A tree starts with a root. This is a data node, like one in a linked list, and it can hold one value of any type. If you’ll recall, nodes in linked lists also carry along a pointer to the following node (and the preceding one, for a doubly-linked list). Well, trees do something like that, too. The root node, in addition to its data value, also contains a list of pointers to its children.

These children are root nodes, and thus trees in their own right. Each will have its own data and list of children, and those, in turn, will have the same. If the child list is empty, then that node is at the “end” of one branch; it’s a leaf node. (If there are children, you might be wondering, are there parents? Yes. A node having another node in its child list is that second node’s parent. But data trees are asexual: each child only has one parent.)

Trees are a perfect example of recursion. A tree’s children are also trees—empty ones, if they’re leaf nodes—and they can be treated as such. The most used algorithms lend themselves naturally to a recursive style even in imperative languages. So that’s how we’ll be looking at them here.

Growing a tree

Trees consist of nodes, and each node has two main parts: a value and a list of children. Thus, a simple way of representing a tree is as an object (or similar structure) with two fields, like so. (This example uses TypeScript for illustration purposes.)

class TreeNode {
    value: any;
    children: TreeNode[];
}

Not that hard, huh? It’s nothing more than putting our words into code. A TreeNode‘s value could be anything, though you’d probably restrict it in a real application, and its children are more TreeNodes. Adding, removing, and altering children works in almost the same way as with linked lists, at least with this “basic” tree setup.

Traversing the tree (sometimes called walking it) is a different matter. Here, we want to go through each of the root’s children, then their children, and so on, until we’ve visited every node in the tree. There are two main ways to do this, but the depth-first method is more common and easier to explain. In code, it looks about like this:

function traverse(tree, callback) {
    for (var child of tree.children) {
        traverse(child, callback);
        callback(child);
    }
}

This algorithm is “depth-first” because it visits each of a node’s children before moving to its siblings. This is where the recursion comes into play. We loop through each of the children of the root node. They, in turn, become the roots of a new depth-first traversal. Only when we’ve exhausted the “depth” of the tree—when we reach a leaf node—do we start doing anything. (We’re assuming here that our tree doesn’t have any cycles, child nodes that point to higher levels of the tree. Those make things much more difficult.)

Now, there are a lot of things you can do with this function, but I’ve limited it to a simple, nebulous callback that is run for each node. In the abstract, that’s all there is to it. That simple block of code effectively describes the operation of some code generators, AI systems, and many other complex actions.

Special kinds of trees

The general tree described above suffices for a great many applications. Sometimes, though, it’s more efficient to be more restricted. Computer scientists have therefore developed a number of specializations of the tree for different uses.

The binary tree is probably the most well-known of these. It’s called “binary” because each node has exactly two children: left and right. These children are themselves trees, of course, but empty trees are often represented as null values. Here’s what it looks like in code, once again using TypeScript:

class BinaryTree {
    data: any;
    left: BinaryTree;
    right: BinaryTree;
}

Binary trees add an extra wrinkle to the depth-first traversal we say earlier. Now, we have three possible ways to do things: pre-order, in-order, and post-order traversal. The only thing that changes is when we process the “current” node.

function preOrder(node, callback) {
    if (node == null) return;

    callback(node.data);
    preOrder(node.left, callback);
    preOrder(node.right, callback);
}

function inOrder(node, callback) {
    if (node == null) return;

    inOrder(node.left, callback);
    callback(node.data);
    inOrder(node.right, callback);
}

function postOrder(node, callback) {
    if (node == null) return;

    postOrder(node.left, callback);
    postOrder(node.right, callback);
    callback(node.data);
}

Each approach has its pros and cons. Pre-order works for copying trees, and it’s essentially how expressions are represented in abstract syntax trees or ASTs, an important part of compilers and interpreters. In-order traversal is best for sorted trees, where an extra “key” value is added to each node, arranged so that it’s greater than all the keys in its left subtree but smaller than all those in the right; these binary search trees are used for set structures, lookup tables, and the like. (Maybe we’ll look at them in more detail later in the series.) Finally, post-order is the option of choice for deleting a node’s children and for making RPN expressions.

The binary tree also has a few of its own alterations. The red-black tree uses a “color bit” to keep the tree balanced. This is helpful because most algorithms working on binary trees work best when there the total numbers of left and right nodes are about equal. (In the worst case, all of a tree’s valid descendants are on one “side”. Then, you’re left with just a more expensive linked list.) The AVL tree is a similar variation that has its own pluses and minuses.

B-trees are a special case that sits between binary trees and the general category of trees. They’re allowed to have more than two children, but only up to a certain number. The trick is that each node is given a number of sort keys (like the one in a binary search tree), one for every child past the first. These are calculated so they fit “between” the children, allowing them to serve as index values, speeding up traversal. B-trees are mostly used in databases and filesystems—the two are practically the same thing these days—including the Windows filesystem of choice, NTFS, Apple’s HFS+, and Ext4 and Btrfs on Linux.

Seeing the forest

Trees are everywhere in programming. Whenever you have a set of data with obvious parent-child relationships, it’s probably going to be represented in tree form. Programming languages often don’t offer direct access to the trees, but they’re in there. Sets, maps, and hash tables all use them under the hood. Any kind of parsing, such as XML or a game’s custom scripting language, is going to be tree-based. Even if you never see them, you’ll be using them somewhere.

Fortunately, if you’re not dealing with the innards of the structures themselves, there’s not much you need to worry about. All the hard work has been taken care of. No one needs to manually balance a binary search tree, for instance. But if you work with them directly, it helps to know how they work.

Big Data is all the rage today, but what good is all that data if you can’t find what you’re looking for? Google, among others, has made billions of dollars by using and developing search algorithms, the backbone of analytics. While I couldn’t even begin to show you how their algorithms work (nor would you likely ever need to know), we can look at their precursors, the simple searches common to many programming languages.

Brute force

The simplest way to search for an item in a list (a value in an array, a substring in a larger body of text, or whatever) is to loop through the list and check each value to see if it’s the one you want. This is a linear search, and it’s not hard to implement, even in JavaScript:

function linear_search(array, value) {
    for (var i = 0; i < array.length; i++) {
        if (array[i] == value) {
            return i;
        }
    }

    return -1;
}

There’s more than one way to do it, but that’s the most straightforward. It’s also the “classic” form familiar to programmers of C and related languages. But it comes at a price: execution time. Linear searches are O(n); the time they take is dependent on the number of items you’re searching over. (Statistically speaking, a linear search of a list of size N will, on average, take N/2 iterations.) Surely we can do better, right?

Divide and conquer

If our list is sorted, we can take an approach that you might recognize from “higher or lower” number guessing games. The binary search starts at a point somewhere in the middle of a list and checks to see if it’s at the right spot. If it’s not, then—because the list is sorted—it knows which way to go for the next guess. It looks a bit like this:

function binary_search(array, value) {
    var idmin = 0;
    var idmax = array.length - 1;

    while (idmin < idmax) {
        // Note: older versions of JS use Math.floor() here
        var midpoint = idmin + Math.trunc((idmax - idmin) / 2);

        if (array[midpoint] == value) {
            return midpoint;
        }
        else if (array[midpoint] < value) {
            idmin = midpoint + 1;
        }
        else {
            idmax = midpoint - 1;
        }
    }

    return -1;
}

Again, there are other ways of writing this function, but the one shown here works for our purposes.

The binary search requires a sorted array. That’s how it’s able to deduce where in the list, relative to its pointer, the correct value is. If you ignore the sorting step (probably because you were going to do it anyway), then it comes out to O(log n) time. That’s faster than a simple linear search, and good enough to put a version of the algorithm into the standard libraries of C (bsearch()), C++ (std::binary_search()), and Java (Arrays.binarySearch()), among others.

Substrings

Searching strings for a specific substring is its own problem with its own considerations. If the substring you’re looking for is only a single character, then the whole exercise degenerates into a case of the above, and you can use linear search (as C’s strchr() likely does behind the scenes). But searching for multi-character strings is a bit harder. A naive approach might look like this:

function substring_search(text, ss) {
    var initial = ss[0];
    var found = false;

    for (var i = 0; i < text.length - (ss.length - 1); i++) {
        if (text[i] == initial) {
            found = true;
            for (var j = 1; j < ss.length, found == true; j++) {
                if (text[i+j] != ss[j]) {
                    found = false;
                }
            }

            if (found) {
                return i;
            }
        }
    }

    return -1;
}

Basically, this is a linear search for the first character of the search string, but with a twist. Whenever that first character is found, an inner loop runs, checking the following characters in the text to see if they match as well. If they do, then we’ve got a perfect match. Otherwise, we keep going from where we left off.

This “dumb” approach takes O(n+m) time, but it’s hard to improve on it without creating some more complicated data structures. Fortunately, that’s exactly where the series is going next, so stay tuned.

We’ve looked at quite a few data structures in this series, from simple arrays to objects. Now, let’s turn our focus to algorithms. One class of algorithms is very important to high-level programming: the sorting algorithms. For decades, computer scientists have been developing new ways to sort data, trying to balance the needs of size and speed, and there’s no silver bullet. Some sorting algorithms are good for general use, but they fall apart on certain degenerate cases. Others are bad all around, but they’re interesting from a teaching perspective.

In this post, we’ll look at three specific algorithms that illustrate the evolution of sorting and some of its trade-offs. Mostly, we’ll treat each one as working on a simple array of integers that we want sorted in increasing order, but it’s easy enough to generalize the sort function to whatever you need. Also, the code will all be in JavaScript, but I won’t be using any trickery or obfuscation, so it shouldn’t be too hard to convert to your favorite language. (Of course, most languages—JavaScript included—already have sorting functionality built into their standard libraries, so it’s better to use those than to write your own.)

Simple and stupid

Bubble sort is the first sorting algorithm many coders see. It’s stupidly simple: move through a list, comparing each element to the one before it. If they’re out of order, swap them. When you get to the end, start over, and repeat until the list is sorted. In code, it might look like this:

function bubblesort(arr) {
    var len = arr.length;

    do {
        var swapped = false;

        // run through the list
        // compare each element to the last
        // swap those that are out of order
        for (var i = 1; i < len; i++) {
            if (arr[i] < arr[i-1]) {
                // swap elements
                var temp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = temp;
                swapped = true;
            }
        }

        // optimization (see below)
        len--;

        // repeat until everything's sorted
    } while (swapped);
}

Even this is already optimized a bit from the basic bubble sort method. Because of the way higher values “bubble up” to the end of the list (hence the name “bubble sort”), we know that, after n iterations, the last n values will be sorted. Thus, the line len-- tells the loop to ignore those values.

That optimization doesn’t help the overall performance of bubble sort. It remains O(n²), not very good. But bubble sort’s value is in its simplicity. You wouldn’t use it in the real world, but it’s a good way to show how sorting works. It’s easy to follow along with it. Take a handful of small numbers and try sorting them by hand, maybe even on paper. It’s not that hard.

Quick and dirty

For a few decades, the go-to choice for sorting has been quicksort. It’s the reason that C’s standard sorting function is called qsort, and it’s still used in many languages, both for performance and simplicity. (Haskell lovers will be quick to point out that that language can implement quicksort in two lines of code.)

Quicksort works by a recursive approach that boils down to “divide and conquer”. Imagine a list as a line of values. Now pick one of those values as the pivot. Take everything less than the pivot and sort it, then take everything greater, and sort that. (This is the recursive step.) Your sorted list is everything in the first sublist, then all the values equal to the pivot, then the second sublist. Or, in code:

function quicksort(arr) {
    if (arr.length <= 1) {
        // recursion base case
        return arr;
    }

    // find the pivot value
    var pivotIndex = parseInt(arr.length / 2);
    var pivotValue = arr[pivotIndex];

    // these will hold our sublists
    var left = [], right = [], pivots = [];

    // partition the list into three:
    // 1. less than the pivot
    // 2. greater than the pivot
    // 3. equal to the pivot
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivotValue) {
            left.push(arr[i]);
        } else if (arr[i] > pivotValue) {
            right.push(arr[i]);
        } else {
            pivots.push(arr[i]);
        }
    }

    // the sorted list is (left + pivots + right)
    return quicksort(left).concat(pivots).concat(quicksort(right));
}

That’s essentially an expanded version of the Haskell two-liner. It’s not the best from a memory or speed standpoint, but it works to show you the way the algorithm works. Another way works in-place, directly operating on the array by swapping elements around so that all the values less than the pivot are placed before it, then putting those greater after it, and then recursing on the resulting partially-sorted list. That one is a lot faster, but it’s a bit harder to grasp. It also needs either a helper function or a bit of logic to allow both sorting of an entire list and of a portion of one.

The gains from that added complexity are huge, though. With it, quicksort becomes one of the faster sorting methods around, and its space efficiency (with the in-place version) can’t be beat. That’s why quicksort remains so popular, even despite some well-known shortcomings. It’s good enough for most purposes.

Good all around

The last of the “simple” sorts we’ll look at is merge sort. This one is very much like quicksort in that it uses a strategy of repeatedly subdividing a list, but it works without a pivot element. At each step, it breaks the list in half and sorts each half separately. (A list with only one element is sorted by definition, so that’s the stopping point.) Then, it merges those halves an element at a time. Here’s the code:

function mergesort(arr) {
    // An element with 0-1 elements is always sorted
    if (arr.length < 2) {
        return arr;
    }

    // break the list into halves
    var middle = arr.length / 2;
    var left = arr.slice(0, middle);
    var right = arr.slice(middle);

    // sort each half separately
    left = mergesort(left);
    right = mergesort(right);

    // now merge the halves
    // take the 1st element of each array, and compare
    // the lower one moves into the "result" list
    // repeat until there's nothing left
    var result = [];
    while (left.length && right.length)
    {
        if (left[0] <= right[0])
        {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    // add in anything we didn't get
    // (in case we had uneven lists)
    result = result.concat(left).concat(right);

    return result;
}

Merge sort uses more space than a good quicksort, but it’s generally faster, and it’s especially good for sorting linked lists. It isn’t the fastest overall, however, nor is it the best for tight memory situations. But it’s a happy medium, all else being equal. Not that it ever is.

Never enough

These aren’t the only sorting algorithms around. They’re merely the easiest to explain. Heapsort is another good one that gets used a lot. Radix sort works best with a lot of data that can be easily indexed. And there are many more than that. There’s even a site that has more details and graphical visualizations of many of the algorithms, including those we’ve discussed in this post.

Of course, it’s very likely that you’ll never need to implement a sorting algorithm yourself. Almost every language already has dozens of them implemented either in the standard library or in open 3rd-party code. Most are even fine-tuned for you. But this whole series is about peeling back those layers to see how things work on the inside. Calling array.sort() is easy, but there are times when it might not be the best option. Learning the algorithms—how they work, their advantages and disadvantages—can give you the knowledge to find those spots when the “standard” sort is a bad idea. That’s a rare case, but finding it just once pays for itself.

Next up, we’ll look at the other side of sorting: searching. With Google and “Big Data”, searching has become more important than ever, so stay tuned.