# Two-Way Linear Probing Revisited
## 5 Upper Bounds
### Two-Way Post-Linear Probing: WalkFirst Algorithm
Clearly, the full history tree permits one to deduce the load of the block that contains the root key at the time of its insertion: it is the length of the shortest path from the rootto any gray node. Thus, if the block's load is more than \(h\), then all gray nodes must be at a distance more than \(h\) from the root. This leads to the notion of a _truncated history tree_ of height \(h\), that is, with \(h+1\) levels of nodes. The top part of the full history tree that includes all nodes at the first \(h+1\) levels is copied, and the remainder is truncated. We are in particular interested in truncated history trees without gray nodes. Thus, by the property mentioned above, the length of the shortest path from the root to any gray node (and as noted above, there is at least one such node) would have to be at least \(h+1\), and therefore, the load of the block harboring the root's key would have to be at least \(h+1\). More generally, if the load is at least \(h+\zeta\) for a positive integer \(\zeta\), then all nodes at the bottom level of the truncated history tree that are not black nodes (and there is at least one such node) must be white nodes whose children represent keys that belong to blocks with load of at least \(\zeta\) at their insertion time. We redraw these node as boxes to denote the fact that they represent blocks of load at least \(\zeta\), and we call them \"block\" nodes. Let \(\zeta\in\mathbb{N}\) be a fixed integer to be picked later. For positive integers \(h\) and \(k\), where \(h+\zeta\leq k\leq m\), a _witness tree_\(W_{k}(h)\) is a truncated history tree of a key in the set \(\llbracket k\rrbracket\), with \(h+1\) levels of nodes (thus, of height \(h\)) and with two types of leaf nodes, black nodes and \"block\" nodes. This means that each internal node has two children, and the node labels belong to the set \(\llbracket k\rrbracket\). Each black leaf has a label of an internal node that precedes it in bfs order. Block nodes are unlabeled nodes that represent blocks with load of at least \(\zeta\). Block nodes must all be at the furthest level from the root, and there is at least one such node in a witness tree. Notice that every witness tree is deterministic. An example of a witness tree is shown in Figure 7.  
Figure 6: The full history tree of key 18. White nodes represent type (a) nodes. Black nodes are type (b) nodes—they refer to keys already encountered in bfs order. Gray nodes are type (c) nodes—they occur when a key selects an empty block. Figure 7: A witness tree of height \(h\) which is a truncated history tree without gray nodes. The boxes at the lowest level are block nodes. They represent selected blocks with load of at least \(\zeta\). The load of the block that contains key 70 is at least \(h+\zeta\). Let \(\mathcal{W}_{k}(h,w,b)\) denote the class of all witness trees \(W_{k}(h)\) of height \(h\) that have \(w\geq 1\) white (internal) nodes, and \(b\leq w\) black nodes (and thus \(w-b+1\) block nodes). Notice that, by definition, the class \(\mathcal{W}_{k}(h,w,b)\) could be empty, e.g., if \(w<h\), or \(w\geq 2^{h}\). However, \(|\mathcal{W}_{k}(h,w,b)|\leq 4^{w}2^{w+1}u^{b}k^{w}\), which is due to the following. Without the labeling, there are at most \(4^{w}\) different shape binary trees, because the shape is determined by the \(w\) internal nodes, and hence, the number of trees is the Catalan number \({2^{w}_{w}}/{(w+1)}\leq 4^{w}\). Having fixed the shape, each of the leaves is of one of two types. Each black leaf can receive one of the \(w\) white node labels. Each of the white nodes obtains one of \(k\) possible labels. Note that, unlike the full history tree, not every key has a witness tree \(W_{k}(h)\): the key must be placed into a block of load of at least \(h+\xi-1\) just before the insertion time. We say that a witness tree \(W_{k}(h)\)_occurs_, if upon execution of algorithm WalkFirst, the random choices available for the keys represented by the witness tree are actually as indicated in the witness tree itself.