Sometimes, the data arrangement schemes we have already covered are not ideal for solving certain problems. For example, when having a set of data that is frequently being searched or modified, while having to maintain a sorted nature, we could place it into an array or a sorted linked list, but the search times could be non-satisfactory. In such a case, it would probably be best to arrange the data in the form of a tree. A binary search tree, for instance, is the best way to minimize the search time when searching dynamic (changing) data. In fact, the same applies to static data as well.

But, first of all, what are trees in computing? When talking about trees, one may imagine a special type of graph (graphs will be briefly covered later in this chapter), consisting of nodes which have a parent node (except the root node, which is called, well, root node) and zero or more child nodes. In Assembly, we would declare a structure for a tree node like this:

struc tnode dataPtr, leftChild, rightChild
{
   .left  dd  leftChild   ; Pointer to left node or 0
   .right dd  rightChild  ; Pointer to right node or 0
   .data  dd  dataPtr     ; Pointer to data
}

So, we have a structure which has a pointer to the left child node (traditionally, nodes with a lower value), a pointer to the right child node (traditionally, nodes with a higher value), and a pointer to the data represented by the node. In general, it is not a bad idea to add a pointer to the parent node, which may ease the task of balancing a tree; however, we do not need that for the example that we will examine in this part of the chapter. The preceding node structure is sufficient for building a tree like this:

This figure demonstrates an ideal case of a balanced binary search tree. In reality, however, this happens not that often and depends on the balancing method. Unfortunately, methodologies of tree balancing slightly fall out of the scope of this book. The main idea, though, is to keep lower values to the left and higher values to the right, which may well involve a certain amount of rotation applied to subtrees, or even the whole tree.