STL’s Associative Containers - Learn C++ for Game Development - page 161

{
pResult = m_pRight->Find(searchValue);
}
return pResult;
}
};
All of the code you need to search for a value inside a binary search tree is contained within the Find
method in Listing 16-7. If you imagine that we have used this class to represent the tree in Figure 16-1 ,
then you would have a pointer to the tree head node stored in our program. You can then call Find on
this node and pass it a value to search for.
If we pass in 1, the first if statement in Find would fail. The second if statement would pass so we
would return the result of m_pLeft->Find . This call to find would follow the same process: The first
if would fail and we would return the result of m_pLeft->Find . This call to find will see the first if
statement pass, so we do not call another function; we simply return this . At this point, all of our
function calls will unwind. Our last call to Find returns this to the second call to Find , which returns
the pointer to the first call to Find , which finally returns it back to the variable being assigned.
Searching for values in a binary tree is, generally, a faster operation than searching through an array ,
vector , or list . In those collections you would have to potentially compare against every element
if the value you were looking for was at the very end of the collection. A binary search tree is much
more efficient. In Figure 16-1 we would only ever have to make 3 comparisons to search against 7
different values. If we were to add another level to the tree, we would have 4 comparisons to make
against 15 different values, and another layer would be 5 comparisons for 31 values. You can see
how quickly these numbers are rising for each level in a binary search tree.
Note Recursion can be a complicated topic for beginning programmers to understand as it ties in with the
concept of the program stack. We'll cover more about this stack in Chapter 22.
The other major algorithm for traversing a collection is called iteration. You have already seen
multiple examples of iteration in action and the iterator types you have seen in use take their name
from this algorithm. Iterating a binary search tree involves visiting each node in turn, and you can use
iterators on a set and a map to visit each element in order.
Binary search trees are one way to store data in associative containers, and another is to use a
hash map.
Fast Data Access Using a Hash Map
A binary search tree structure provides fast access to sorted data. The tree is automatically sorted
when adding data and you've seen how a search of that data can be done very quickly. It is possible
to use an even faster structure than a binary search tree when you do not need to iterate over sorted
data. A hash map has a constant time insert and retrieval of a value. This means that it will take the
same length of time to insert the first element as it will to insert the tenth or the millionth. It also has a
constant time retrieval of data. This means that finding data in a container does not increase the time
elapsed along with the number of elements the container holds.