# A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical Infrastructures
## 5 The \(D^{3}\)-Tree
### Single and Range Queries  
The search for an element \(a\) may be initiated from any node \(v\) at level \(l\). If \(v\) is a bucket node, then if its range contains \(a\) the search terminates, otherwise the search is forwarded to the bucket representative, which is a binary node. In case \(v\) is a node of the PBT (Algorithm 8), let \(z\) be the node with range of values containing \(a\), \(a\in[x_{z},x_{z}^{\prime}]\) and assume w.l.o.g. that \(x_{\rho}^{\prime}<a\). The case where \(x_{\rho}>a\) is completely symmetric. First, we perform a horizontal binary search at the level \(l\) of \(v\) using the routing tables, searching for a node \(u\) with right sibling \(w\) (if there is such sibling) such that \(x_{u}^{\prime}<a\) and \(x_{w}>a\), unless \(a\) is in the range of \(u\) or in the range of any visited node of \(l\) and the search terminates. More specifically, we keep travelling to the right using the rightmost links of the routing tables of nodes in level \(l\) (the most distant ones), until we find a node \(q\) such that \(x_{q}>a\), or until we have reached the rightmost node \(qr\) of level \(l\). If the first case is true, then \(a\) is somewhere between \(q\) and the last visited node in the left of \(q\), so we start travelling to the left decreasing our travelling step by \(1\). We continue travelling left and right, gradually decreasing the travelling step, until we find the siblings \(u\) and \(w\) mentioned above in step = 0. If the second case is true, then \(x_{qr}^{\prime}<a\) and according to the in-order traversal the search is confined to the right subtree of \(qr\). ```
1:BinaryNode currentNode, step \(\
eq\) 0
2:/* horizontal search */
3:while step \(\
eq\) 0 do
4:if currentNode.Contains(element) then
5:return currentNode;
6:endif
7:if currentNode.UpperValue \(\leq\) element then
8:if currentNode == RightMostNodeInLevel then
9:return currentNode.SearchSubtree(element);
10:endif
11:leftMostNode = currentNode;
12:if rightMostNode \(\
eq\) null then
13:step\(---\);
14:currentNode = currentNode.RightAdjacents[step];
15:else
16:currentNode = currentNode.RightAdjacents.Last;
17:step = currentNode.RightAdjacents.Count;
18:endif
19:elseif currentNode.LowerValue \(>\) element then
20:/*... similar to previous case...*/
21:endif
22:endwhile
23:/* step == 0, vertical search */
24:BinaryNode leftSibling; rightSibling;
25:if currentNode.UpperValue \(\leq\) element then
26:leftSibling = currentNode;
27:rightSibling = currentNode.RightAdjacents[0];
28:elseif currentNode.LowerValue \(>\) element then
29:leftSibling = currentNode.LeftAdjacents[0];
30:rightSibling = currentNode;
31:endif
32:targetNode = leftSibling.SearchSubtree(element);
33:if targetNode == null then
34:targetNode = leftSibling.SearchAncestor(element);
35:if targetNode == null then
36:targetNode = rightSibling.SearchSubtree(element);
37:endif
38:endif
39:return targetNode;
```  
**Algorithm 8** Search(integer element)Having located nodes \(u\) and \(w\), the horizontal search procedure is terminated and the vertical search is initiated. Node \(z\) will either be the common ancestor of \(u\) and \(w\) (Algorithm 9), or in the right subtree rooted at \(u\) (Algorithm 10), or in the left subtree rooted at \(w\). If \(u\) is a binary node, it contacts the rightmost leaf \(y\) of its subtree. If \(x_{y}>a\) then an ordinary top-down search from node \(u\) will suffice to find \(z\). Otherwise, node \(z\) is in the bucket of \(y\), or in its right in-order adjacent (this is also the common ancestor of \(u\) and \(w\)), or in the subtree of \(w\). If \(z\) belongs to the subtree of \(w\), a symmetric search is performed.