Linear containers

A sequence of $N$ items can be stored in either an array or a linked list. We will describe each here.

Arrays

In C++, the array represents a contiguous block of memory that can be accessed through an index. If the contiguous block of memory can store capacity items, the indices run from 0 to capacity - 1. We will look at four representations of arrays, and in each case, we will show how these are implemented in C++:

1. The primitive fixed-size static array.
2. The primitive fixed-size dynamic array.
3. A class wrapping a primitive fixed-size static array.
4. A class wrapping the dynamic array but allowing for resizing.

Linked lists

Next, we will look at linked lists: like arrays, linked lists store data in a linear manner, with a zeroth entry, then a first, second, and so on until we get to the (size - 1)th entry.

Important: We will refer to the number of entries in an array as the capacity, as that is the maximum number of items the array can store. The number of useful items in the array, however, will be referred to as the size.

Binary trees

A binary tree is similar to a linked list, where each node stores a value, except that rather than having a single next pointer, there are two pointers: one "left" pointer, and one "right" pointer. Given a node, it may have zero, one or two nodes that it points to, and the nodes it points to are called "child" nodes. If the root node has a value "42" and it has one left child with a value "91", then that tree is different from a tree where the root node has the value "42" and it has one right child with a value "91".

Some more terminology: If a Node B is a child of Node A, then Node A is a "parent" of Node B. The root node is at "depth" zero. Its children are at depth one, and the children of the children of the root are at depth two, and so on. The "height" of a tree is the maximum depth of any node within the tree, so a tree containing only a root node has a height equal to zero.

While an array or linked list is generally viewed from left (the first entry or front) to right (the last entry or back), a binary tree starts with a single node called the "root" node at the top, and its two children are drawn beneath it, but it is always important to differentiate between the "left" child and the "right" child.

When we insert a new value into a linked list, we either insert it at the front or the back, but now there are many "backs", because if there are $n$ nodes in a binary tree, there must be $n + 1$ left or right pointers set to nullptr, so a new node could be inserted into any location.

We will look at two strategies for prescribing where a new node goes: the first uses nodes like a linked list, while the second uses an array.

Now, let us consider a tree of height $h$. This means that there is at least one node of depth $n$, but no nodes of depth $h + 1$ (or higher). In the worst case, the root node has only one child, and each child has only one child, meaning that a tree of height $h$ can have as few as $n = h + 1$ nodes. On the other hand, suppose that all nodes at depth $k$ always have two children. In this case, a tree of depth $n$ could have as many as $n = 2^{h + 1} - 1$ nodes. This is because there is one node (the root node) when the depth is $k = 0$, two nodes when depth $k = 1$, and if each of those has two children, four nodes at depth $k = 2$, and so on, yeilding a total of $\sum_{k = 0}^h 2^k$ nodes, which is a geometric sum, and $\sum_{k = 0}^h 2^k = 2^{h + 1} - 1$. Thus, $n$ nodes can be stored in a tree of height as small as $\log_2(n + 1) - 1$. For example, a tree with a million nodes can have a height as small as $19$.

Binary trees using nodes

A binary tree using nodes has two pointers

struct Node {
  T value_;
  Node *p_left_;
  Node *p_right_;
};

A node may contain other information, as is necessary to ensure that the data structure is efficient.

Like the linked list class, a binary tree class would contain a pointer to the root node:

class Binary_tree {
  Node *p_root_;
};

New items would be inserted to the binary tree at the root, and it would be necessary to step through the tree from parent to child until there is an appropriate location were a new value can be added (usually as a new leaf node).

Binary trees using arrays

If we use an array (static or dynamic), we can proceed as follows:

• Ignore the entry at index 0.
• The root node is stored at index 1.
• The value stored at index k has its children at indices 2*k and 2*k + 1.
• The value stored at index k has its parent at index k/2 where integer division is used: that is, the remainder is discarded, so both 16/2 and 17/2 evaluate to 8, and 2*8 == 16 and 2*8 + 1 == 17.

This second representation is not necessarily all that useful, for the capacity the array is N + 1 and if every node from 1 to N/2 does not have two children (with the exception of possibly the last), then there can be potentially a lot of memory wasted. However, if we can guarantee that the array will be an efficient storage.

As an example, the binary tree shown in the image

is referred to as a complete binary tree (as all nodes at the same depth exist except for maybe the lowest depth, which is never-the-less occupied from left to right), and the values in these nodes could be stored in an array of capacity 13, occupying indices from 1 to 12.