15.1. Tree ADT concepts¶
If sequence containers like vector are so great, then why would we need anything else?
In a word: search.
When we have millions of elements in a data structure and need to find
just one element, or a specific range of elements,
we could use a vector.
Appending elements is fast.
No matter how many elements are already in a vector
adding one more using push_back takes
amortized constant time. An occasional reallocation takes linear time,
but the average cost over a sequence of appends is \(O(1)\) per element.
A vector is default ordered only by its index position,
not by the values stored within it.
It's easy to keep throwing items in without paying any attention
to how they are ordered.
But always using push_back is analogous to a messy closet.
We could consider the closet to be ordered by depth:
the last things thrown in the closet are on the top of the pile.
This makes getting a specific item from the closet slow. If we only ever want to access the last item we added, then we know exactly where to go. But if we want to find some arbitrary item, we have to search the vector 1 element at a time until we find it.
1#include <algorithm>
2#include <cstddef>
3#include <iostream>
4#include <numeric>
5#include <random>
6#include <vector>
7
8int main() {
9 std::vector<int> messy_closet(1024);
10 std::iota(messy_closet.begin(), messy_closet.end(), 0);
11 const int search_value = 42;
12 std::mt19937 engine{187};
13 std::size_t total_examined = 0;
14 constexpr int max_iter = 10;
15
16 for (int trial = 1; trial <= max_iter; ++trial) {
17 std::shuffle(messy_closet.begin(), messy_closet.end(), engine);
18
19 std::size_t examined = 0;
20 for (const auto value : messy_closet) {
21 ++examined;
22 if (value == search_value) {
23 break;
24 }
25 }
26
27 total_examined += examined;
28 std::cout << "trial " << trial
29 << ": examined " << examined << " elements\n";
30 }
31
32 std::cout << "average examined: "
33 << static_cast<double>(total_examined) / max_iter << "\n";
34}
Sometimes we may get lucky and find the desired element at index position 0. If the data added to the vector is random and the searched value is present, then finding it near the beginning becomes increasingly less likely as the size grows.
We might sometimes get very unlucky and not find the element until we access the last element. Over many successful searches whose positions are uniformly distributed, we will examine \(N \over 2\) elements on average. An unsuccessful search examines all \(N\) elements.
It's easy to see that the more elements are added, the longer searches will take.
We need a tidy closet.
We could sort the vector, which would speed up our search.
The basic idea is to sort the vector, then examine the middle element
of the current search range. If the middle value is greater than the value
we are looking for, continue in the lower half; otherwise, continue in the
upper half. This is the binary search algorithm.
At each step,
we eliminate the number of remaining elements we need
to search in our vector by half.
For a large vector, this saves a lot of time.
This technique requires that we keep the vector sorted. If elements are added or removed frequently, then adding data to our vector, which used to be fast, is now slow. We can use push_back followed by sort, which costs \(O(N \log N)\) for each update, or use lower_bound to find the insertion position. The binary search then takes \(O(\log N)\) comparisons, but inserting into the middle of a vector still requires \(O(N)\) element movement.
How can we solve this problem?
Can we make an ADT whose performance does not degrade as the number of elements in the ADT grows large?
Yes, but we need a new idea. Instead of a sequential container, we need a tree.
15.1.1. The tree ADT¶
A tree is a hierarchical abstract data type. Conceptually, it can be thought of as a collection of nodes defined by parent-child relationships.
One node is the root. It serves as the 'trunk' of the tree and serves the same function as the head of a list. The root node is the only node in a tree without a parent. Every other node in a tree has exactly one parent. In a binary tree, the children are commonly referred to as the left child and right child, or as the left and right subtrees.
Yes, programmers draw trees upside-down. The root is above the branches.
The height of a tree is the number of edges along the longest path from the root to a leaf node. A tree containing only a root has height 0.
Although there are many different types of trees, this chapter focuses on binary trees. A binary tree is a tree in which no node has more than 2 children. Any tree node may have 0, 1, or 2 children. A tree node with no children is a leaf node.
All of these are valid binary trees:
A roughly balanced binary search tree, one whose subtree heights remain reasonably similar, provides the tidy structure we need for fast inserts and retrievals. Balance alone is not enough: the tree must also maintain the binary search tree ordering property for key-based search.
When a binary search tree is balanced, search, insertion, and removal take \(O(\log N)\) time under the usual balanced-tree guarantees. Binary trees provide a way for us to formalize our half-splitting solution.
Unbalanced search trees are not much more than fancy linked lists. The performance of unbalanced trees degrades back to the messy room, with all of the problems and none of the benefits.
The C++ standard specifies the behavior and complexity of std::set and
std::map; it does not require a particular implementation.
However, balanced search trees are commonly used to implement ordered sets and
maps.
More to Explore