Augmented Data Structures

An augmented data structure is a data structure where we add an extra piece of information so that we can acheive better performance. From a user's perspective the augmented data structure works no differently than the non-augmented version.

We will be looking at two augmented data structures in this section and they both help to solve a problem with the basic version of the BST.

Consider the following set of numbers:

5, 3, 7, 2, 9, 4, 6, 1, 8

If we were to insert each of these values in order into a BST using the algorithm we currently have studied, our tree would look like this:

However, suppose we were to created a BST with exactly the same numbers but in the following order instead:

1, 2, 3, 4, 5, 6, 7, 8, 9

The tree created by the insertion algorithm would look like this:

In the first case, the tree looks like tree. In the second case it looks like a stick. The problem of a tree that looks like a stick is that its run time for searching is not log n. its basically a linked list and its performance will match that of a linked list and thus search will perform in O(n) time.

As we cannot know how our data structure will be used, or prevent someone from using our data structure with sorted data, it would be good if we can ensure that no matter how the data comes in, the tree will be tree shaped.

In this chapter we will look at how we can add a little bit of extra information to our tree and use that to help ensure our tree does not turn into a stick no matter how we receive our data.