https://g-trees.github.io/g_trees/ Geometric Search Trees 1. Introduction 2. Related Work 3. Preliminaries 1. Data Structures 2. Pseudorandom Geometric Distributions 3. Zip-Trees 4. G-Trees 1. Analysis 1. G-Tree Height 2. G-Node Size 3. G-Tree Size 2. Well-Known G-Trees 1. Zip-Trees as G-Trees 2. Zip-Zip-Trees and Beyond 3. Treaps as G-Trees 3. Novel G-Trees 5. Algorithms 6. Conclusion 7. References 8. Appendix A: Code 9. Appendix B: G-Tree Variants 10. Appendix C: Explicit Insertion and Deletion Carson Farmer Textile, Inc carson@textile.io Aljoscha Meyer TU Berlin research@aljoscha-meyer.de We describe G-trees, a family of randomized, history-independent search tree data structures. The G-trees encompass several independently-discovered data structures such as zip-trees, zip-zip-trees, and dense skip-trees. The family further contains novel trees of arity greater than two, which are significantly more efficient in the presence of cache hierarchies or block storage than zip-trees. Traditionally, such randomized trees have been significantly more complex than their binary counterparts, whereas our k-ary G-trees have no additional conceptual overhead at all. We generalize the zip and unzip operations of zip-trees to provide a uniform, simple, and efficient implementation technique for all members of our family of data structures. 1 Introduction Randomized set data structures eschew self-balancing logic for simpler, probabilistic item organization. When deriving the necessary randomness via pseudorandom functions of the stored items themselves, the resulting graphs depend on the stored set only, but not the order of insertions and deletions. This history-independence ensures that no information about previously deleted items can be reconstructed ( Naor & Teague, 2001), and it enables efficient set fingerprinting ( Pugh & Teitelbaum, 1989) when using the data structure as a merkle-tree (Merkle, 1989). For these reasons, randomized search trees and related data structures have been studied for decades. The most prominent such data structures are treaps (Seidel & Aragon, 1996), skip-lists (Pugh, 1990), and, more recently, zip-trees (Tarjan et al., 2021). All three are different takes on approximating the distribution of items in perfectly balanced binary search trees. While binary trees are highly efficient in theory, they are less efficient on actual hardware than trees that store more than one item per vertex. Unfortunately, generalizing binary randomized data structures to higher-arity counterparts has proven more difficult than in the case of deterministically self-balancing trees. Providing a simple such generalization is the impetus for our work. Figure 1 plots lookup performance of a zip-tree versus a 32-ary tree of ours; our tree is roughly twice as fast (note the logarithmic y-axis). On secondary storage, we can expect the performance difference to be even more pronounced. A plot showing search performance of a zip-tree versus a 32-zip-tree; the latter is roughly twice as fast. Figure 1: Lookup Performance Benchmarking search times for 100 randomly chosen items in randomly generated zip-trees (red, top line) and 32-zip-trees (green, lower line). The latter is a novel variant of zip-trees that arises naturally from our generalization of zip-trees to G-trees. We present the geometric search trees (G-trees), a family of randomized search trees that provides a unified perspective on several independently researched data structures, including zip-trees , zip-zip-trees (Gila et al., 2023), skip-trees (Messeguer, 1997), dense skip-trees (Spiegel & Reynolds Jr, 2009), merkle-search-trees ( Auvolat & Taiani, 2019), and prolly-trees (Boodman et al., 2016). Our framework allows us to trivially define efficient trees that store a bounded number of items per vertex. These trees are arguably the first such randomized search trees whose conceptual complexity is just as low as that of their binary counterparts. Our key insight is to take a byproduct of the usual definition of zip-trees, turn it into a defining property of its own, and to then generalize it. Zip-trees assign geometrically chosen ranks to their items, and use these ranks for probabilistic balancing. A consequence of their balancing mechanism is that certain sequences of items with colliding ranks form sorted linked lists. It turns out we can view and even define zip-trees as collections of such linked lists. From this definition, which is based on arranging sorted linked lists in a certain fashion, it is only a small step to arranging arbitrary set data structures in the same fashion. This yields our G-trees, a family of trees that is parameterized over a secondary search data structure. Using simple linked lists as the underlying data structure yields the zip-trees. Recursively instantiating the G-trees with other G-trees yields a natural (and efficient) generalization of the zip-zip-trees. And finally, using linked lists of k items per vertex yields a generalization of the zip-trees where each node can store up to k items. The G-trees not only define a unique tree shape for any set of items with associated ranks, they also offer a unified means of implementation. We provide generalizations of the zipping and unzipping algorithms of the original zip-trees, and use them to implement insertion and deletion. These general algorithms can be applied to all G-trees whose underlying set data structure supports splitting at arbitrary keys and joining two non-overlapping sets. The algorithms perform a number of splits or joins proportional to the number of distinct ranks in the tree, which is logarithmic in the total number of items with high probability. We give an overview of related work in Section 2, before introducing preliminary definitions and notation in Section 3. We present the geometric trees in Section 4, including a thorough analysis and a an overview of old and novel G-trees. Section 5 describes efficient algorithms for mutating G-trees. 2 Related Work The practically-minded reader can safely skip ahead to Section 3, whereas the more academically inclined may wish to stick around for Section 2, where we outline the current state of the art and contextualize our contributions.Data structures whose exact shape is determined solely by their contents and not by the order of insertion and deletion operations have been studied for decades. This property has been given several names, such as unique representation (Snyder, 1977), structural unicity (Auvolat & Taiani, 2019), confluent persistence (Driscoll et al., 1994), and anti-persistence or history-independence (Naor & Teague, 2001). Deterministically self-balancing history-independent set data structures necessarily take super-logarithmic time to update under arbitrary insertions and deletions (Snyder, 1977). Hence, several probabilistic history-independent data structures have been devised which support membership queries and update operations in logarithmic time with high probability. Well-known such (pseuso-) randomized set data structures include hash tries (as presented, for example, by Pugh and Teitelbaum (Pugh & Teitelbaum, 1989)), treaps (Seidel & Aragon, 1996), and skip-lists ( Pugh, 1990). More recently, zip-trees (Tarjan et al., 2021) and zip-zip-trees (Gila et al., 2023) have been proposed as more efficient variants of skip-lists. All these data structures approximate the vertex distribution of binary balanced search trees. While binary search trees are theoretically efficient, CPU caches or block-sized reads from secondary storage make it so that trees that store more than a single item per vertex outperform binary trees in practice. Theoretical models to capture this behavior in the analysis of algorithms and data structures include external memory models (Aggarwal & Vitter, 1988) and cache-oblivious models (Frigo et al., 1999). Several attempts have been made to find randomized data structures that perform well in an external memory model. Golovin (Golovin, 2009) has proposed bushy treaps (B-treaps) to approximate the behavior of B-trees via treaps. Unfortunately, B-treaps are complicated enough that even their author recommends using simpler alternatives such as the B-skip-list (Golovin, 2010). The B-skip-list still involves a tuning parameter beyond the probability distribution for assigning node levels, a nontrivial invariant, and virtual memory management via hash tables rather than simple usage of pointers. In short, the conceptual complexity goes far beyond that of binary skip-lists or treaps. Safavi and Seybold (Safavi & Seybold, 2023) propose randomized-block-search-trees (RBSTs) as another generalization of binary treaps that performs well in an external-memory model. The construction involves multiple tuning parameters, two distinct layers of data structure internals, and a highly nontrivial complexity analysis. Bender et al (Bender et al., 2016) first specify a history-independent packed-memory array (PMA), and then build a history-independent B-tree analogon and an external-memory skip-list on top of the PMA. So there is again a two-layered aproach; the PMA introduces a significant chunk of conceptual complexity that is not part of regular treaps or skip-lists. Some proponents of randomized data structures claim that a significant advantage over self-balancing data structures is their greater simplicity (Pugh, 1990; Seidel & Aragon, 1996). It seems safe to say that none of the external-memory constructions we have just listed retain this advantage. All prior work that does achieve sufficient simplicity buys it at the price of vertices that must store a dynamic, unbounded number of items. The skip-trees (Messeguer, 1997) are the first such data structure, effectively converting a skip-list into a tree: each vertex stores sequences of items that are being skipped-over together in the corresponding skip-list. The relatively unknown dense skip-trees (Spiegel & Reynolds Jr, 2009) provide two optimizations: expected node size can be increased by flipping coins of success probabilities k1 , and empty vertices are eliminated from the tree. The merkle-search-trees (MSTs) (Auvolat & Taiani, 2019) independently reinvent skip-trees with flexible probabilities similar to dense skip-trees, but without the compression of empty vertices. Additionally, prolly-trees (Boodman et al., 2016) provide a slightly different take, where a rolling hash function over the keys/values is used to determine the set of items in each node, rather than via explicit split and join operations. None of these data structures can provide a non-probabilistic upper bound on the number of items per vertex. This hampers efficient implementation; and adversarial data suppliers can trivially produce n items in O(n) expected time that must all be stored in the same vertex. 3 Preliminaries Here, we define fundamental terminology, and provide proper definitions and background for zip-trees. 3.1 Data Structures A tree data structure for items from some universe U is either the empty tree, or a vertex consisting of a sequence of k-1 items from U and a sequence of k trees called its children. We write t.items for the items of t, and t.items[i] for the i-th item of t. We write t.children for the children of t, and t.children[i] for the i-th child of t. Indexing always starts at zero. Let t be a tree. The set of t, its children, their children, and so on, is called the set of subtrees of t. We say t is of arity k if all subtrees of t have at most k children. If t is a binary tree, we refer to its first child as its left child, and to its second child as its right child. Let be a total order on U, and let c be the number of children of t . Then t is a search tree In a search tree, intuitively speaking, the items are sorted from left to right. That is, an in-order traversal yields a sorted sequence. (with respect to U) if it is the empty tree , or if * t.items is sorted with respect to U, * all items in t.children[0] are less than t.items[0], * for all 0=r)<=qr-1. By the union bound, the probability that there exists some G-node such that rank(g)>=r is P([?]g,rank(g)>=r)<=nqr-1, and so for some positive constant c, P(MT >=(c+1)logk (n))<=n-c (Golovin, 2010). Even for r>[?]logk (n)[?], the tail probability contribution is relatively small; we can estimate it by simplifying the geometric series:r=[?]logk (n)[?]+1[?][?] npr-1=np[?]logk (n)[?]<=nplogk (n)=1-p1 =q1 =k. Hence, E(MT )[?][?]logk (n)[?], and E(MT ) is at most [?]logk (n)[?]+k, with high probability. By construction, the height(T) of a geometric tree is less than or equal to its maximum rank MT . Like zip trees, geometric trees compress their depth where ranks are missing or skipped;While we don't bother with tight bounds on this compressed height, (Archibald et al., 2006) provides an expectation on the number of distinct ranks in a geometrically distributed random sample, which could provide slightly tighter bounds. as such, E(height(T))<=E(MT )<=[?]logk (n)[?]+k. Thus we have that the height of a geometric tree is in O(logn) with high probability. Figure 6 confirms our analysis with experimental data. Maximum Rank n=100 n=1,000 n=10,000 n=100,000 k=2 8.0 (3.48) 11.3 (4.00) 14.7 (3.88) 17.9 (3.27) k=4 4.2 (0.90) 5.9 (0.98) 7.5 (0.86) 9.2 (0.92) k=16 2.4 (0.30) 3.2 (0.21) 4.1 (0.25) 4.9 (0.29) k=64 1.8 (0.19) 2.2 (0.19) 3.0 (0.12) 3.35 (0.24) Height n=100 n=1,000 n=10,000 n=100,000 k=2 6.7 (0.75) 9.9 (0.75) 13.2 (0.72) 16.7 (0.73) k=4 4.0 (0.51) 5.6 (0.51) 7.3 (0.44) 9.0 (0.47) k=16 2.3 (0.24) 3.2 (0.18) 4.1 (0.25) 4.9 (0.24) k=64 1.8 (0.18) 2.2 (0.17) 3.0 (0.11) 3.3 (0.23) Figure 6: G-Tree Maximum Ranks Average maximal ranks and heights (in G-nodes) of 200 randomly generated G-trees, for various combinations of n and k. The numbers in parentheses give the variance. 4.1.2 G-Node Size Given the geometric distribution of (independent) ranks over input values s[?]S, the expected number of values with rank r is about k times the expected number of values with rank r+1, i.e., P(rank(s)>r| rank(s)>=r)=q. Recall that each G-node in a geometric tree contains a set of items with the same rank, and that the rank of the G-node is the maximum rank of its items. Thus, we can think of G-nodes within T as disjoint subsets formed by splitting the (sorted) items of rank r at values of rank r+1. In other words, the number of nodes with a given rank r is a direct function of the number of G-nodes with rank r+1. The above node layout implies that the size |g| of a G-node is itself a random variable drawn from a geometric distribution, this time with success probability k1 and support [n]={1,...,n}. The expected value is roughly k, and the observed size is at most c times the expected value with probability at least 1-(1-k1 )ck. In other words, P(|g|>=ck )<=(1-k1 )ck. Setting c=[?]logk (n)[?], and using 1-k1 <=exp(-k1 ), we have thatP(|g|>=[?]logk (n)[?]k) <=(1-k1 )[?]logk (n)[?]k<=exp(-k1 )[?]logk (n)[?]k=exp (-k1 [?]logk (n)[?]k) which for large n, where [?]logk (n)[?][?]logk (n), we getexp(-k1 logk (n)k)=exp(-logk (n))=n-1This bound demonstrates that the probability that the size of any G-node deviates from k decreases exponentially with n. Figure 7 shows experimental measurements of average G-node sizes. For low n, nodes contain slightly too few items: items are spread-out, and there are not enough items to "fill up" all nodes. The variances are small; average G-node sizes are indeed as stable as our analysis suggests. Average G-Node Size n=100 n=1,000 n=10,000 n=100,000 k=2 1.9095 1.9940 1.9983 1.9998 (0.0000334) (0.0000162) (0.0000006) (0.0000000) k=4 3.6374 3.9516 3.9942 4.0002 (0.0000063) (0.0000036) (0.0000012) (0.0000008) k= 12.1596 15.2423 15.9084 15.9850 16 (0.0257947) (0.0011409) (0.0001009) (0.0000016) k= 30.6534 56.3768 62.6815 63.7859 64 (0.0817688) (0.0023357) (0.0219051) (0.0235732) Figure 7: G-Node Average Sizes Average G-node sizes of 200 randomly generated G-trees, for various combinations of n and k. The numbers in parentheses give the variance . 4.1.3 G-Tree Size The total expected number of G-nodes in a G-tree is intuitively E(|T| )=kn +1. Given that q=k1 this can also be expressed as nq+1. While this expectation is intuitive, it can be estimated more directly as the sum of the expected number of G-nodes at every possible rank (plus a root node). Since the number of G-nodes at rank r is equal to the number of items having rank r+1, and since the rank assignments for items are independent, the number of G-nodes with rank r in a G-tree can be modeled as a binomial random variable Xr , with parameters n (the number of trials, i.e., the number of items) and p= (1-q)qr (the probability of success, i.e., the probability that a item has rank r+1).To see why, consider that a binomial random variable describes the number of successes in a fixed number of independent trials, where each trial has the same probability of success. Here each item is an independent trial, the "success" is the event that a item has rank r, and the probability of success is (1-q) qr. Thus, the expected number of G-nodes at rank r is E(Xr )=n(1-q)qr , and by the linearity of expectation, the total expected number of G-nodes in a G-tree is a geometric series with sumE(|T|)=r=1[?][?] n(1-q) qr+1=n(1-q)r=1[?][?] qr+1and recognizing that for |q|<1 the rightmost infinite sum simplifies to 1-qq , we getE(|T|)=n(1-q)1-qq +1=nq+1.To provide bounds, we can use the usual multiplicative form of a Chernoff bound for the sum of independent (but not identically distributed) Bernoulli random variables (Dubhashi & Panconesi, 2009)2 2Again, you'll probably want to look this up on Wikipedia rather than in a textbook.. Then, for any c>0P(|T|>=(1+c)nq)<=((1+c)1+cec )nqor perhaps more conveniently, for 0( 1+c)kn )<=exp(3k-c2n ).This provides an exponentially small probability that the total number of G-nodes in a geometric tree is much more than kn +1, and thus the G-tree size is in O(n). Figure 8 gives experimental measurements that confirm the analysis. Average Number of G-Nodes n=100 n=1,000 n=10,000 n=100,000 k=2 52.21 (25.081) 502.5 (257.2) 5002 (2394.5) 50001 (26339) k=4 27.51 (19.086) 252.9 (191.70) 2504 (1826.1) 25004 (18939) k=16 8.33 (6.716) 65.46 (57.22) 628.2 (572.4) 6255.3 (6113.3) k=64 3.29 (2.213) 17.75 (15.25) 159.16 (160.2) 1564 (1486.8) Figure 8: G-Node Counts Average number of G-nodes in 200 randomly generated G-trees, for various combinations of n and k. The numbers in parentheses give the variance. This analysis provides some intuition for the practical efficiency and scalability of G-trees: the expected number of G-nodes is linear in the number of items, and is very close to a balanced tree structure. By understanding the total number of nodes and their size distribution, we can optimize and parameterize G-trees to minimize disk accesses, align nodes with disk block sizes, and design effective caching and buffer management strategies. This ensures that the tree operations are performed with high I/O efficiency, reducing latency and increasing throughput. Moreover, it helps in predicting performance, identifying bottlenecks, and managing storage costs by ensuring efficient space allocation and utilization. Combined with the fixed size of the k-lists (see Section 4.3) this makes G-trees potentially well-suited for external memory models while retaining much of their simplicity in practice. 4.2 Well-Known G-Trees We now discuss how several well-known probabilistic data structures can be expressed as G-trees. 4.2.1 Zip-Trees as G-Trees As we described in our derivation of the G-trees, instantiating G-trees with sorted linked lists yields the zip trees. Aside from mentioning zip trees here for the sake of completeness, we want to point out an interesting implementation detail: whereas zip trees store the rank of every item in its vertex, a sorted linked list G-tree only needs to store one rank per linked list that it contains, i.e., one rank per G-node. 4.2.2 Zip-Zip-Trees and Beyond Instantiation of G-trees requires a set data structure. G-trees are set data structures themselves. How about some recursion? Instantiating G-trees with zip trees, i.e., with G-trees instantiated with sorted linked lists, yields exactly the zip-zip-trees. Zip-zip-trees (Gila et al., 2023) were initially introduced as a modification of the tie-breaking algorithm of zip trees. This modification is essentially an ad-hoc variation, whereas our description of zip-zip-trees highlights them as a (highly relevant) member of a family of G-trees obtained from recursive self-instantiation. In particular, once G-trees and sorted linked lists have been implemented, the difference between implementing zip trees and zip-zip-trees consists of a single type-level operation, whereas the algorithmic definition of zip-zip-trees requires manual adjustment of all tree manipulation algorithms. More generally, we can instantiate G-trees with G-trees that are themselves recursively instantiated, to an arbitrary depth and choice of recursion anchor. Using sorted linked lists as recursion anchors yields a family of zipk-trees whose first two members are the zip trees and the zip-zip-trees. 4.2.3 Treaps as G-Trees We end this section with a fun observation: if we restrict each nested tree structure in the zipk-trees to store ranks in a single bit (i.e., we cap the geometric distribution at two), we obtain exactly the treaps with k-bit priorities. We doubt that this has any practical applications, but it shows that the family of recursively instantiated G-trees is interesting beyond just the zip-zip-trees. 4.3 Novel G-Trees Having shown that the G-trees encompass several useful and well-known data structures, we now give some members of the family that have not been independently described before. In particular, we tackle the problem of finding history-independent data structures that are efficient on secondary storage (or in terms of cpu caches) by storing up to k items in a single vertex. Previous solutions (Bender et al., 2016; Golovin, 2009, 2010; Safavi & Seybold, 2023) all incur a significant overhead in terms of conceptual complexity compared to their binary counterparts. With G-trees, we merely need to change the underlying set datastructure S to one that stores items in blocks of k. A key intuition behind classic zip trees is that of choosing ranks from a geometric distribution with p=1-21 =21 because this is the distribution of the height of a randomly chosen vertex in a perfectly balanced binary tree. For k-ary trees, the same intuition instructs us to draw ranks from a geometric distribution with p=1-k1 , as this is the distribution of heights in a perfectly balanced k-ary tree. Our analysis confirmes that -- with high probability -- the resulting trees are of logarithmic height and their G-nodes store O(k) items. The second key insight toward an efficient k-ary data structure is, paradoxically, that there is no need to be clever about it. Sorted linked lists are naive, inefficient data structures, yet zip trees are efficient. We can be similarly naive for our k-ary construction. We use a sorted linked list in which every node stores up to k items. We require all items to be stored as early in the list as possible; this is the simplemost way of achieving history-independence. In other words, the only node to store fewer than k items is the final node. We call such a list a k-list (see Figure 9). A rendering of a 3-list. Figure 9: A 3-List The sorted 3-list containing 1,4,5,8,23,26,32,35. Sometimes, things are just that simple. Instantiating G-trees with the k-lists and a geometric distribution of p=1-1+k1 yields a family of data structures we call the k -zip-trees. Figure 10 depicts the 2-zip-tree for our running example set. A rendering of a 2-zip-tree. Figure 10: 2-Zip-Tree A 2-zip-tree. Linked list pointers are dashed, child pointers are solid. The three layers of the layout correspond to the three different ranks. Observe how contracting the linked lists effectively yields Figure 5. The k-lists are inefficient data structures -- inserting or deleting the first item requires O(n) time in a k-list of n items. The k -zip-trees are nevertheless efficient, because the expected size of the G-nodes, and hence, the expected length of the k-lists, is constant for any p. More efficient alternatives to k-lists exist, such as unrolled linked lists (Shao et al., 1994). These are not history-independent, however. What is the expected height of a k-zip-tree? Asymptotically, we know it to be in O(logn), since we have G-nodes of O(logn) different ranks , each a list of O(k) items (which has a length in O(k)). Figure 11 gives experimental measures for some specific n and k. The height amplification we report is the height of each tree divided by the height of a perfectly-balanced k+1-ary tree on n vertices. Tree Height n=100 n=1,000 n=10,000 n=100,000 k=1 15.29 (5.61) 26.59 (8.89) 38.20 (9.47) 50.58 (11.86) k=3 8.61 (2.40) 14.92 (3.38) 21.97 (4.41) 29.13 (4.93) k=15 4.28 (0.98) 8.06 (2.04) 12.36 (2.43) 16.66 (2.45) k=63 2.37 (0.24) 5.05 (1.43) 8.43 (1.69) 12.08 (2.52) Height Amplification n=100 n=1,000 n=10,000 n=100,000 k=1 2.18 (0.11) 2.66 (0.09) 2.73 (0.05) 2.98 (0.04) k=3 2.15 (0.15) 2.98 (0.14) 3.14 (0.09) 3.24 (0.06) k=15 2.14 (0.24) 2.69 (0.23) 3.09 (0.15) 3.33 (0.10) k=63 1.18 (0.06) 2.53 (0.36) 2.81 (0.19) 4.03 (0.28) Figure 11: K-Zip-Tree Height The heights of 200 randomly generated G-trees, i.e., the maximal number of pointers to traverse from the root to a leaf; for various combinations of n and k. The numbers in parentheses give the variance . The second table normalizes the heights by the heights of perfectly-balanced k+1-ary trees on n vertices. Another concern of interest is space amplification: in the worst case, every item would be in its own k-list, resulting in a space amplification factor of k. Intuitively, this occurs only rarely, however: the expected size of each G-node is k, and the probability for a G-node to have size s { 3 Create a set containing a single item and its left subtree. 4 singleton(item: I, subtree: GTree) -> Self 5 6 Split self into the set of items and their left subtrees strictly less than key, the left subtree of key if key is an item in self, and the set of items and their left subtrees strictly greater than key. 7 split( 8 self: Self, 9 key: I, 10 ) -> (Set, Option>, Set) 11 12 Join two sets left and right into a single set, assuming that all items in left are less than any items in right. 13 join(left: Self, right: Self) -> Self 14 15 Split self into the least item and its left subtree, and the remaining set. 16 remove_min( 17 self: Self, 18 ) -> ((I, GTree), Set) 19 20 Insert an item and its left subtree into self. The new item must be strictly less than any item in self. 21 insert_min( 22 self: Self, 23 new_min: (I, GTree), 24 ) -> Self 25 } 26 27 A set, possibly empty. Parameterized over a type of non-empty sets. 28 enum Set { 29 NonEmpty(S) 30 Empty 31 } 32 33 A G-node. 34 struct GTreeNode> { 35 rank: N, 36 Nonzero number of items and their left subtrees. 37 set: S, 38 The one right subtree. 39 right: GTree, 40 } 41 42 A G-tree, possibly empty. 43 enum GTree> { 44 NonEmpty(GTreeNode) 45 Empty 46 } 47 48 An optional value. 49 enum Option { 50 Some(V) 51 None 52 } The functions we require of a NonemptySet are standard functions that are easily implemented in O(log(n)) time with typical set data structures33Not that we needed an efficient implementation: since G-nodes have constant expected size, even O(n) implementations do not hurt the asymptotic efficiency of our algorithms.. The only choice worth commenting on is that of using a specialized insert_min function instead of a generic insert function. This choice is to allow for more efficient, specialized implementations, as well as to highlight that our algorithms interact with the internal set data structures in a surprisingly constrained manner. Before giving our main algorithms, we define some helper functions: 1 Insert an item and its left subtree into a possibly empty set. The new item must be strictly less than any item in set. 2 fn set_insert_min>( 3 set: Set, 4 new_min: (I, GTree), 5 ) -> S { 6 match set { 7 Set::Empty => return singleton( 8 new_min.0, 9 new_min.1, 10 ) 11 Set::NonEmpty(s) => { 12 return insert_min(s, new_min) 13 } 14 } 15 } 16 17 Replace the leftmost left subtree of a GTreeNode. 18 fn update_leftmost>( 19 node: GTreeNode, 20 new_left: GTree, 21 ) -> GTreeNode { 22 let ( 23 (leftmost_item, _), 24 other_pairs, 25 ) := remove_min(node.set) 26 return GTreeNode { 27 rank: node.rank, 28 set: set_insert_min( 29 other_pairs, 30 (leftmost_item, new_left), 31 ), 32 right: node.right, 33 } 34 } 35 36 Replace the right subtree of a GTreeNode. 37 fn update_right>( 38 node: GTreeNode, 39 new_right: GTree, 40 ) -> GTreeNode { 41 return GTreeNode { 42 rank: node.rank, 43 set: node.set, 44 right: new_right, 45 } 46 } 47 48 A (non-empty) GTree has a root GTreeNode that consists of a rank, a right subtree, and a non-empty set of pairs of items and their left subtrees. Occasionally, we need to construct a non-empty GTree from a rank, a right subtree, and a possibly empty set of pairs of items and their left subtrees. If the set is empty, the lifted GTree is simply the supplied right subtree. 49 fn lift>( 50 s: Set, 51 right: GTree, 52 rank: N, 53 ) -> GTree { 54 match s { 55 Set::Empty => return right 56 Set::NonEmpty(set) => return GTree::NonEmpty( 57 GTreeNode { 58 rank: rank, 59 set: set, 60 right: right, 61 }, 62 ) 63 } 64 } While it is possible to derive insertion and deletion algorithms by generalizing the original zip tree algorithms (see Appendix C for examples), we opt for a fully self-contained presentation here. Zipping and unzipping are similar to the join and split functions of join-based tree algorithms (Blelloch et al., 2016). We consistently use zip and unzip terminology when operating on G-trees, and join and split terminology when operating on the underlying set datastructure S. We build our insertion and deletion algorithms from algorithms for unzipping and zipping G-trees. Unzipping takes a key and splits a G-tree into the tree of all items less than the key and the tree of all items greater than the keyThe key itself occurs in neither returned tree, even if it is part of the input tree.. Zipping takes two trees, the first containing only items strictly lesser than any item of the second, and joins them together into a single tree. We call this version of zipping zip2, because it takes two arguments. We also use a zip3 function, which additionally incorporates a single item into the tree that is strictly greater than all items of the first tree, and strictly less than all items of the second tree. Insertion and deletion can then be implemented as composition of unzipping and zipping (zip3 and zip2, respectively) -- see Figure 13. A G-tree, before and after inserting an item, with the unzipped tree as an intermediate step. Figure 13: Insertion and Deletion Example of inserting or deleting item 18 of rank 3 via unzipping followed by zipping. To unzip a G-tree, split the inner set of the root GTreeNode, and then performs a case distinctionWe give a more thorough description in the form of code comments. to determine whether it is necessary to recurse: 1 Split t into two trees of items strictly less and greater than key respectively. 2 fn unzip>( 3 t: GTree, 4 key: I, 5 ) -> (GTree, GTree) { 6 match t { 7 Unzipping the empty tree is trivial. 8 GTree::Empty => return (Empty, Empty) 9 10 For non-empty trees, split the inner set. 11 GTree::NonEmpty(s) => match split(s.set, key) { 12 If s.set contains the split point (key), then everything up until the split point becomes the left return value, with the left subtree of the split point becoming the right subtree of the left return. Everything after the split point becomes the right return, with the right subtree of the current node becoming the right subtree of the right return. No further recursion. 13 ( 14 left_set, 15 Option::Some(left_subtree_of_key), 16 right_set, 17 ) => return ( 18 lift(left_set, left_subtree_of_key, s.rank), 19 lift(right_set, s.right, s.rank), 20 ) 21 If s.set does not contain the split point, and all its items are less than the split point, then recursively split the right subtree of s. 22 (_, Option::None, Set::Empty) => { 23 let (left, right) := unzip(s.right, key) 24 return ( 25 GTree::NonEmpty(update_right(s, left)), 26 right, 27 ) 28 } 29 If s.set does not contain the split point, but it does contain items greater than the split point, then recursively split the leftmost subtree of those greater items. 30 (left_set, Option::None, Set::NonEmpty(r)) => { 31 let ( 32 (r_leftmost_item, r_leftmost_subtree), 33 r_remaining, 34 ) := remove_min(r) 35 let ( 36 left, 37 right, 38 ) := unzip(r_leftmost_subtree, key) 39 return ( 40 lift(left_set, left, s.rank), 41 GTree::NonEmpty(GTreeNode { 42 rank: s.rank, 43 set: set_insert_min( 44 r_remaining, 45 (r_leftmost_item, right), 46 ), 47 right: s.right, 48 }), 49 ) 50 } 51 } 52 } 53 } Since the expected size of G-nodes is constant with high probability, we can treat all functions of the NonemptySet interface as running in constant time. Each recursive call of the unzip function is to a GTreeNode of strictly decreasing rank, so the recursion depth is bounded by the height of the G-tree, which is logarithmic with high probability. Hence, the overall running time is in O(log(n)) with high probability. We can similarly give a recursive algorithmAgain, the main description takes the form of code comments. for zipping together two G-trees with the same complexity properties: 1 Join two trees left and right into a single tree, assuming that all items in left are less than any items in right. 2 fn zip2>( 3 left: GTree, 4 right: GTree, 5 ) -> GTree { 6 match (left, right) { 7 If left is empty, then the join is the other tree. 8 (GTree::Empty, _) => return right 9 If right is empty, then the join is the other tree. 10 (_, GTree::Empty) => return left 11 Neither tree is empty, so there is real work to do. What that entails depends on how the ranks of the root nodes of the two trees compare. 12 (GTree::NonEmpty(l), GTree::NonEmpty(r)) => { 13 if l.rank < l.rank { 14 Zip l into the leftmost left subtree of r. 15 let ( 16 (_, r_leftmost_subtree), 17 _, 18 ) := remove_min(r) 19 let zipped := zip2(left, r_leftmost_subtree) 20 return GTree::NonEmpty( 21 update_leftmost(r, zipped), 22 ) 23 } 24 else if l.rank > l.rank { 25 Zip r into the right subtree of l. 26 let zipped := zip2(l.right, right) 27 return GTree::NonEmpty( 28 update_right(l, zipped), 29 ) 30 } 31 else { 32 Equal ranks. Join the two inner sets, with the right subtree of the left node being zipped into the leftmost left subtree of the right node. 33 let ( 34 (r_leftmost_item, r_leftmost_subtree), 35 r_others, 36 ) := remove_min(r) 37 let zipped := zip2(l.right, r_leftmost_subtree) 38 let r_set := insert_min( 39 r_others, 40 (r_leftmost_item, zipped), 41 ) 42 43 return GTree::NonEmpty( 44 GTreeNode { 45 rank: l.rank, 46 set: join(l.set, r_set), 47 right: r.right, 48 }, 49 ) 50 } 51 } 52 } 53 } To implement zipping of two G-trees with an additional item in between them, we can simply convert that item into a singleton G-tree , and then call zip2 twice: 1 Join two trees left and right and the item item into a single tree, assuming that all items in left are less than item, and all items in right are greater than item. 2 fn zip3>( 3 left: GTree, 4 item: I, 5 rank: N, 6 right: GTree, 7 ) -> GTree { 8 let mid := GTree::NonEmpty( 9 GTreeNode { 10 rank: rank, 11 set: singleton(item, GTree::Empty), 12 right: GTree::Empty, 13 }, 14 ) 15 16 return zip2(zip2(left, mid), right) 17 } With unzip, zip2, and zip3 in place, insertion and deletion in expected logarithmic time become trivial: 1 Insert an item at a given rank into a G-tree. 2 fn insert>( 3 t: GTree, 4 item: I, 5 rank: N, 6 ) -> GTree { 7 let (left, right) := unzip(t, item) 8 return zip3(left, item, rank, right) 9 } 10 11 Delete an item from a G-tree. 12 fn delete>( 13 t: GTree, 14 item: I, 15 ) -> GTree { 16 let (left, right) := unzip(t, item) 17 return zip2(left, right) 18 } We want to emphasize that our choice of algorithms optimizes for elegance, not for (non-asymptotic) efficiency. Implementations based on in-place mutations will outperform our immutable algorithms. A direct implementation of zip3 will outperform the reduction to two applications of zip2. Iterative implementations might outperform recursive implementations. And finally, direct implementations of insertion and deletion should outperform those based off unzipping and zipping the full trees. The original zip-tree paper (Tarjan et al., 2021) contains examples of direct algorithms that zip and unzip only parts of a tree; our algorithms can be adapted to work analogously, and we provide variants for G-trees in Appendix C. 6 Conclusion We have generalized the zip trees to the rich family of G-trees. G-trees must be instantiated with a concrete set data structure; using a linked list yields the zip trees, and direct recursive self-instantiation yields the zip-zip-trees. All G-trees are history-independent if the underlying set data structure is history-independent, and admit the same efficient algorithms for mutating them. We have proven the G-trees to be similar to perfectly balanced search trees with high probability, a property that makes them asymptotically and practically efficient. Beyond merely generalizing existing data structures, we have defined the k-zip-trees, a conceptually simple family of history-independent data structures that store up to k items in a single vertex. Such data structures make more efficient use of hardware caches than binary trees, allowing the k-zip-trees to outperform the binary zip trees. References Aggarwal, Alok ; Vitter, S, Jeffrey: The input/output complexity of sorting and related problems. In: Communications of the ACM vol. 31, ACM New York, NY, USA (1988), Nr. 9, pp. 1116-1127 Archibald, Margaret ; Knopfmacher, Arnold ; Prodinger, Helmut: The number of distinct values in a geometrically distributed sample. In: European Journal of Combinatorics vol. 27 (2006), Nr. 7, pp. 1059-1081. -- Eurocomb '03 - Graphs and Combinatorial Structures Auvolat, Alex ; Taiani, Francois: Merkle search trees: Efficient state-based CRDTs in open networks. In: 2019 38th Symposium on Reliable Distributed Systems (SRDS) : IEEE, 2019, pp. 221-22109 Bender, Michael A ; Berry, Jonathan W ; Johnson, Rob ; Kroeger, Thomas M ; McCauley, Samuel ; Phillips, Cynthia A ; Simon, Bertrand ; Singh, Shikha ; et al.: Anti-persistence on persistent storage: History-independent sparse tables and dictionaries. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016, pp. 289-302 Blelloch, Guy E ; Ferizovic, Daniel ; Sun, Yihan: Just join for parallel ordered sets. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016, pp. 253-264 Boodman, Aaron ; Weinstein, Rafael ; Arvidsson, Erik ; Masone, Chris ; Willhite, Dan ; Kalman, Benjamin: Prolly Trees: Probabilistic B-Trees. Comer, Douglas: The Ubiquitous B-tree. In: ACM Computing Surveys (CSUR) vol. 11, ACM New York, NY, USA (1979), Nr. 2, pp. 121-137 Driscoll, James R ; Sleator, Daniel DK ; Tarjan, Robert E: Fully persistent lists with catenation. In: Journal of the ACM (JACM) vol. 41, ACM New York, NY, USA (1994), Nr. 5, pp. 943-959 Dubhashi, Devdatt P. ; Panconesi, Alessandro: Chernoff-Hoeffding Bounds. In: Concentration of Measure for the Analysis of Randomized Algorithms : Cambridge University Press, 2009, pp. 1-15 Eisenberg, Bennett: On the expectation of the maximum of IID geometric random variables. In: Statistics & Probability Letters vol. 78, Elsevier (2008), Nr. 2, pp. 135-143 Forbes, Catherine ; Evans, Merran ; Hastings, Nicholas ; Peacock, Brian: Statistical distributions : John Wiley & Sons, 2011 Frigo, Matteo ; Leiserson, Charles E ; Prokop, Harald ; Ramachandran, Sridhar: Cache-oblivious algorithms. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) : IEEE, 1999, pp. 285-297 Gila, Ofek ; Goodrich, Michael T ; Tarjan, Robert E: Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent. In: Algorithms and Data Structures Symposium : Springer, 2023, pp. 474-492 Golovin, Daniel: B-treaps: A uniquely represented alternative to B-trees. In: International Colloquium on Automata, Languages, and Programming : Springer, 2009, pp. 487-499 Golovin, Daniel: The B-skip-list: A simpler uniquely represented alternative to B-trees. In: arXiv preprint arXiv:1005.0662 (2010) Merkle, Ralph C: A certified digital signature. In: Conference on the Theory and Application of Cryptology : Springer, 1989, pp. 218-238 Messeguer, Xavier: Skip trees, an alternative data structure to skip lists in a concurrent approach. In: RAIRO-Theoretical Informatics and Applications vol. 31, EDP Sciences (1997), Nr. 3, pp. 251-269 Naor, Moni ; Teague, Vanessa: Anti-persistence: History independent data structures. In: Proceedings of the thirty-third annual ACM symposium on Theory of computing, 2001, pp. 492-501 Pugh, William: Skip lists: a probabilistic alternative to balanced trees. In: Communications of the ACM vol. 33, ACM New York, NY, USA (1990), Nr. 6, pp. 668-676 Pugh, William ; Teitelbaum, Tim: Incremental computation via function caching. In: Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 1989, pp. 315-328 Safavi, Roodabeh ; Seybold, Martin P: B-Treaps Revised: Write Efficient Randomized Block Search Trees with High Load. In: arXiv preprint arXiv:2303.04722 (2023) Seidel, Raimund ; Aragon, Cecilia R: Randomized search trees. In: Algorithmica vol. 16, Springer (1996), Nr. 4, pp. 464-497 Shao, Zhong ; Reppy, John H ; Appel, Andrew W: Unrolling lists. In: Proceedings of the 1994 ACM conference on LISP and functional programming, 1994, pp. 185-195 Snyder, Lawrence: On uniquely represented data strauctures. In: 18th Annual Symposium on Foundations of Computer Science (sfcs 1977) : IEEE, 1977, pp. 142-146 Spiegel, Michael ; Reynolds Jr, Paul F: The Dense Skip Tree: A Cache-Conscious Randomized Data Structure, Citeseer (2009) Szpankowski, Wojciech ; Rego, Vernon: Yet another application of a binomial recurrence. Order statistics. In: Computing vol. 43, Springer (1990), Nr. 4, pp. 401-410 Tarjan, Robert E ; Levy, Caleb ; Timmel, Stephen: Zip trees. In: ACM Transactions on Algorithms (TALG) vol. 17, ACM New York, NY (2021), Nr. 4, pp. 1-12 Appendix A: Code We have published the code powering our experiments on github (under the MIT license). The implementation written is in rust, and can be built with the cargo package manager. Run cargo run --bin stats to replicate the experiments for Figure 6, Figure 7, Figure 8, Figure 11 , and Figure 12. Run cargo bench to recreate the benchmark for Figure 1. Appendix B: G-Tree Variants We now sketch several variants of G-trees that might be useful in practice. Highlights include a G-tree-analogon of the B^+-tree (Comer , 1979), and a cache-efficient generalization of the skip-list. When search trees store not only keys but key-value pairs, some usecases benefit from storing all key-value pairs in leaves of the tree. To support efficient lookup of the leaves, the inner vertices of the tree store duplicates of certain keys. We can easily adapt G-trees to this behavior by placing items not only in the tree layer corresponding to their rank but also on all lower layers. Figure 14 depicts such a naive leafy G-tree, and Figure 15 and Figure 16 show concrete instantiations with a 1-list (a naive leafy zip-tree) and a 2-list (a naive leafy 2-zip-tree) respectively. We arbitrarily44 Spoiler: the ordering is arbitrary in principle, but our choice will surface a deep connection to skip-lists in a few paragraphs. choose to sort items of lower rank to the right of their copies of higher rank. [leafGtree] Figure 14: Naive Leafy G-Tree An example naive leafy G-tree that stores the same items as the G-tree in Figure 5. [leafGtreeO] Figure 15: Naive Leafy Zip-Tree An example naive leafy zip-tree, a concrete instantiation of the naive leafy G-tree in Figure 14. Compare also with Figure 4, which depicts the zip tree for the same items. [leafGtree2] Figure 16: Naive Leafy 2-Zip-Tree An example naive leafy 2-zip-tree, a concrete instantiation of the naive leafy G-tree in Figure 14. Compare also with Figure 10, which depicts the 2-zip-tree for the same items. The figures clearly show a deficiency of this naive approach: almost all items have a single pointer to the layer below, except for the first item of each rank, which needs two pointers. We can restore uniformity by adding a dummy element [?] at the start of each layer. Figure 17 gives an example of the resulting (proper) leafy G-tree; Figure 18 shows a leafy zip-tree, and Figure 19 shows a leafy 2-zip-tree. [leafBotGtr] Figure 17: Leafy G-Tree [leafBot1zi] Figure 18: Leafy Zip-Tree [leafBot2zi] Figure 19: Leafy 2-Zip-Tree The reader familiar with skip-lists should immediately see that Figure 18 -- the rendering of a leafy zip-tree -- essentially shows a skip-list, except that some of the edges within the same layer are missing. Figure 21 shows a proper skip-list with the same items and ranks for comparison. Characterizing the "missing" edges from the perspective of leafy G-trees is trivial: there are no edges between vertices of equal rank that belong to different G-nodes. Characterizing the missing edges from the perspective of skip-lists is quite instructive. Consider the algorithm for searching in a skip-list: start in the topmost layer, follow pointers within a layer until overshooting the search target, drop down a layer when you would overshoot. The "missing" edges are exactly the edges that are always guaranteed to overshoot -- if they did not overshoot, the search would never have descended into this part of the skip-list in the first place. Search in a leafy zip-tree encounters a null pointer at the end of each G-node, whereas search in a skip-list blindly dereferences a pointer and performs a comparison whose result is already predetermined. As far as we are aware, this observation of two classes of next-pointers in skip-lists -- those that always overshoot in a search, and those which might not overshoot in some searches -- is novel. The fact that skip-lists get to conflate the two classes and algorithmically handle them in a uniform way might well be the underlying reason why skip-lists are so appealing compared to binary search trees. We can easily augment the leafy G-trees to generalize the skip-lists by adding pointers between successive G-nodes of equal rank. Figure 20 shows the resulting linked leafy G-tree for our running example. Figure 21 instantiates with a linked list, obtaining a linked leafy zip-tree, i.e., a skip-list. Figure 22 shows the instantiation with a 2-list, yielding a linked leafy 2-zip-tree. Instantiating the linked leafy zip-trees with k-lists gives a family of generalizations of skip-lists that store k items per vertex. Finding such a family could easily be reason for a dedicated publication, were it not for the fact that the powerful framework of geometric trees gives us this family essentially for free. [linkedLeaf] Figure 20: Linked Leafy G-Tree [linkedLeaf] Figure 21: Linked Leafy Zip-Tree aka Skip-List [linkedLeaf] Figure 22: Linked Leafy 2-Zip-Tree aka 2-Skip-List To conclude, we point out that linking only the leaves of a leafy G-tree yields a family analogous to the B^+-trees (Comer, 1979). Figure 23 shows such a G^+-tree; Figure 24 shows an instantiation with a linked list (a zip^+-tree), and Figure 25 shows an instantiation with a 2-list (a 2-zip^+-tree). [gPlusGtree] Figure 23: G^+-Tree [gPlus1zip] Figure 24: Zip^+-Tree [gPlus2zip] Figure 25: 2-Zip^+-Tree Appendix C: Explicit Insertion and Deletion As alluded to in Section 5, it is possible to derive direct insertion and deletion functions for G-trees that are analgous to Algorithm 1 from the original zip tree paper. For completeness, we provide pseudocode for purely functional variants of these functions for G-trees. The functions leverage the previously defined zip2 and various helper functions. We also define an additional helper function which joins a possibly empty Set with a greater NonemptySet.: 1 Join a (possibly empty) Set with a greater NonemptySet. 2 fn set_join>( 3 left: Set, 4 right: S, 5 ) -> S { 6 match left { 7 Set::Empty => return right 8 Set::NonEmpty(l) => join(l, right) 9 } 10 } The following explicit delete pseudocode follows a very similar structure to Algorithm 1 from (Tarjan et al., 2021), though we use pattern matching here for consistency. 1 Delete an item from a G-tree. 2 fn delete>( 3 t: GTree, 4 item: I, 5 ) -> GTree { 6 match t { 7 Deletion in the empty tree is trivial. 8 GTree::Empty => return Empty 9 10 For non-empty trees, split the inner set. 11 GTree::NonEmpty(s) => match split(s.set, item) { 12 The target item was found. Simply exclude it and zip the left and right subtrees together. 13 ( 14 left_set, 15 Option::Some(left_subtree_of_key), 16 right_set, 17 ) => return zip2( 18 lift(left_set, left_subtree_of_key, s.rank), 19 lift(right_set, s.right, s.rank), 20 ) 21 The target item is strictly greater than all items in s.set, recurse into the s.right subtree and build from the left. 22 (left_set, Option::None, Set::Empty) => { 23 return lift( 24 left_set, 25 delete(s.right, item), 26 s.rank, 27 ) 28 } 29 The target item is strictly less than the leftmost_item of r, recurse down the left and build from the right. 30 (left_set, Option::None, Set::NonEmpty(r)) => { 31 let ( 32 (leftmost_item, leftmost_subtree), 33 remaining, 34 ) := remove_min(r) 35 let new_right := insert_min(remaining, ( 36 leftmost_item, 37 delete(leftmost_subtree, item), 38 )) 39 return GTree::NonEmpty( 40 GTreeNode { 41 set: set_join(left_set, new_right), 42 right: s.right, 43 rank: s.rank, 44 }, 45 ) 46 } 47 } 48 } 49 } While the explicit insert function requires a bit more code, it also follows the same general structure of its original zip tree counterpart. The bulk of the additional code is devoted to operations on the inner set, whereas the matched patterns remain mostly equivalent. 1 Insert an item into a G-tree. 2 fn insert>( 3 t: GTree, 4 item: I, 5 rank: N, 6 ) -> GTree { 7 match t { 8 Insertion into the empty tree is trivial. 9 GTree::Empty => return GTree::NonEmpty( 10 GTreeNode { 11 set: singleton(item, GTree::Empty), 12 right: GTree::Empty, 13 rank: rank, 14 }, 15 ) 16 17 For non-empty trees, split the inner set. 18 GTree::NonEmpty(s) => match split(s.set, item) { 19 Found the item, nothing more to do. 20 (_, Option::Some(_), _) => return t 21 The NonemptySet of the current GTreeNode contains no items greater than item. 22 (left_set, Option::None, Set::Empty) => { 23 if rank < s.rank { 24 return GTree::NonEmpty( 25 GTreeNode { 26 set: s.set, 27 right: insert(s.right, item, rank), 28 rank: s.rank, 29 }, 30 ) 31 } else if rank = s.rank { 32 let (l, r) := unzip(s.right, item) 33 return GTree::NonEmpty( 34 GTreeNode { 35 set: set_join( 36 left_set, 37 singleton(item, l), 38 ), 39 right: r, 40 rank: s.rank, 41 }, 42 ) 43 } else { 44 let (l, r) := unzip(s.right, item) 45 let left_subtree := lift( 46 left_set, 47 l, 48 s.rank, 49 ) 50 return GTree::NonEmpty( 51 GTreeNode { 52 set: singleton(item, left_subtree), 53 right: r, 54 rank: rank, 55 }, 56 ) 57 } 58 } 59 The NonemptySet of the current GTreeNode does contain items greater than item. 60 ( 61 left_set, 62 Option::None, 63 Set::NonEmpty(right_set), 64 ) => { 65 let ( 66 (leftmost_item, leftmost_subtree), 67 remaining, 68 ) := remove_min(right_set) 69 if rank < s.rank { 70 let new_subtree := insert( 71 leftmost_subtree, 72 item, 73 rank, 74 ) 75 let new_right := set_insert_min( 76 remaining, 77 (leftmost_item, new_subtree), 78 ) 79 return GTree::NonEmpty( 80 GTreeNode { 81 set: set_join(left_set, new_right), 82 right: s.right, 83 rank: s.rank, 84 }, 85 ) 86 } else if rank = s.rank { 87 let (l, r) := unzip(leftmost_item, item) 88 let new_right := insert_min( 89 insert_min(remaining, (leftmost_item, r)), 90 (item, l), 91 ) 92 return GTree::NonEmpty( 93 GTreeNode { 94 set: set_join(left_set, new_right), 95 right: s.right, 96 rank: s.rank, 97 }, 98 ) 99 } else { 100 let (l, r) := unzip(leftmost_item, item) 101 let left_subtree := lift( 102 left_set, 103 l, 104 s.rank, 105 ) 106 let right_subtree := GTree::NonEmpty( 107 GTreeNode { 108 set: insert_min( 109 remaining, 110 (leftmost_item, r), 111 ), 112 right: s.right, 113 rank: s.rank, 114 }, 115 ) 116 return GTree::NonEmpty( 117 GTreeNode { 118 set: singleton(item, left_subtree), 119 right: right_subtree, 120 rank: rank, 121 }, 122 ) 123 } 124 } 125 } 126 } 127 }