Parallel Ordered Sets Using Join

arXiv:1602.02120v4 [] 12 Nov 2016

Guy Blelloch
Carnegie Mellon University
guyb@cs.cmu.edu

Daniel Ferizovic
Karlsruhe Institute of Technology
dani93.f@gmail.com

Yihan Sun
Carnegie Mellon University
yihans@cs.cmu.edu
November 15, 2016
Abstract
Ordered sets (and maps when data is associated with each key) are one of the most important and useful data types.
The set-set functions union, intersection and difference are particularly useful in certain applications. Brown and

n
Tarjan first described an algorithm for these functions, based on 2-3 trees, that meet the optimal Θ m log m
+1
time bounds in the comparison model (n and m ≤ n are the input sizes). Later Adams showed very elegant algorithms
for the functions, and others, based on weight-balanced trees. They only require a single function that is specific to the
balancing scheme—a function that joins two balanced trees—and hence can be applied to other balancing schemes.
Furthermore the algorithms are naturally parallel. However, in the twenty-four years since, no one has shown that the
algorithms are work efficient (or optimal), sequential or parallel, and even for the original weight-balanced trees.
In this paper we show that Adams’ algorithms are both work efficient and highly parallel (polylog depth) across
four different balancing schemes—AVL trees, red-black trees, weight balanced trees and treaps. To do this we need
careful, but simple, algorithms for J OIN that maintain certain invariants, and our proof is (mostly) generic across the
schemes.
To understand how the algorithms perform in practice we have also implemented them (all code except J OIN is
generic across the balancing schemes). Interestingly the implementations on all four balancing schemes and three set
functions perform similarly in time and speedup (more than 45x on 64 cores). We also compare the performance of
our implementation to other existing libraries and algorithms including the standard template library (STL) implementation of red-black trees, the multicore standard template library (MCSTL), and a recent parallel implementation
based on weight-balanced trees. Our implementations are not as fast as the best of these on fully overlapping keys
(but comparable), but better than all on keys with a skewed overlap (two Gaussians with different means).

1

1

Introduction

Ordered sets and ordered maps (sets with data associated with each key) are two of the most important data types
used in modern programming. Most programming languages either have them built in as basic types (e.g. python) or
supply them as standard libraries (C++, C# Java, Scala, Haskell, ML). These implementations are based on some form
of balanced tree (or tree-like) data structure and, at minimum, support lookup, insertion, and deletion in logarithmic
time. Most also support set-set functions such as union, intersection, and difference. These functions are particularly
useful when using parallel machines since they can support parallel bulk updates. In this paper we are interested in
simple and efficient parallel algorithms for such set-set functions.
The lower bound for comparison-based algorithms for union, intersection
and difference for inputs of size n and
n
+
1
. Brown and Tarjan first described a
m ≤ n and output an ordered structure1 is log2 m+n
=
Θ
m
log
m
n
sequential algorithm for merging that asymptotically match these bounds [11]. It can be adapted for union, intersection
and difference with the same bounds. The bound is interesting since it shows that implementing insertion with union,
or deletion with difference, is asymptotically efficient (O(log n) time), as is taking the union of two equal sized sets
(O(n) time). However, the Brown and Tarjan algorithm is complicated, and completely sequential.
insert(T, k) =
(TL , m, TR ) = split(T, k);
join(TL , k, TR )
delete(T, k) =
(TL , m, TR ) = split(T, k);
join2(TL , TR )

union(T1 ,T2 ) =
if T1 = Leaf then T2
else if T2 = Leaf then T1
else (L2 ,k2 ,R2 ) = expose(T2 );
(L1 ,b,R1 ) = split(T1 ,k2 );
TL = union(L1 ,L2 ) k TR = union(R1 ,R2 );
join(TL ,k2 ,TR )

split(T, k) =
if T = Leaf then (Leaf,false,Leaf)
else (L, m, R) = expose(T );
if k = m then (L,true,R)
else if k < m then
(LL , b, LR ) = split(L, k);
(LL ,b,join(LR , m, R))
else (RL , b, RR ) = split(R, k);
(join(L, m, RL ), b, RR )

intersect(T1 ,T2 ) =
if T1 = Leaf then Leaf
else if T2 = Leaf then Leaf
else (L2 ,k2 ,R2 ) = expose(T2 );
(L1 ,b,R1 ) = split(T1 ,k2 );
TL = intersect(L1 ,L2 ) k TR = intersect(R1 ,R2 );
if b = true then join(TL ,k2 ,TR )
else join2(TL ,TR )

splitLast(T ) =
(L, k, R) = expose(T );
if R = Leaf then (L, k)
else (T 0 , k0 ) = splitLast(R);
(join(L, k, T 0 ),k0 )

difference(T1 ,T2 ) =
if T1 = Leaf then Leaf
else if T2 = Leaf then T1
else (L2 ,k2 ,R2 ) = expose(T2 );
(L1 ,b,R1 ) = split(T1 ,k2 );
TL = difference(L1 ,L2 ) k TR = difference(R1 ,R2 );
join2(TL ,TR )

join2(TL ,TR ) =
if TL = Leaf then TR
else (TL0 , k) = splitLast(TL );
join(TL0 , k, TR )

Figure 1: Implementing U NION, I NTERSECT, D IFFERENCE, I NSERT, D ELETE, S PLIT, and J OIN 2 with just J OIN.
E XPOSE returns the left tree, key, and right tree of a node. The || notation indicates the recursive calls can run in
parallel. These are slight variants of the algorithms described by Adams [1], although he did not consider parallelism.
Adams later described very elegant algorithms for union, intersection, and difference, as well as other functions
using weight-balanced trees, based on a single function, J OIN [1, 2] (see Figure 1). The algorithms are naturally
parallel. The J OIN(L, k, R) function takes a key k and two ordered sets L and R such that L < k < R and returns the
union of the keys [28, 26]. J OIN can be used to implement J OIN 2(L, R), which does not take the key in the middle,
and S PLIT(T, k), which splits a tree at a key k returning the two pieces and a flag indicating if k is in T (See Section
4). With these three functions, union, intersection, and difference (as well as insertion, deletion and other functions)
1 By

“ordered structure” we mean any data structure that can output elements in sorted order without any comparisons.

2

are almost trivial. Because of this at least three libraries use Adams’ algorithms for their implementation of ordered
sets and tables (Haskell [19] and MIT/GNU Scheme, and SML).
J OIN can be implemented on a variety of different balanced tree schemes. Sleator and Tarjan describe an algorithm
for J OIN based on splay trees which runs in amortized logarithmic time [26]. Tarjan describes a version for red-black
tree that runs in worst case logarithmic time [28]. Adams describes version based on weight-balanced trees [1].2
Adams’ algorithms were proposed in an international competition for the Standard ML community, which is about
implementations on “set of integers”. Prizes were awarded in two categories: fastest algorithm, and most elegant yet
still efficient program. Adams won the elegance award, while his algorithm is as fast as the fastest program for very
large sets, and was faster for smaller sets. Adams’ algorithms actually show that in principle all balance criteria for
search trees can be captured by a single function J OIN, although he only considered weight-balanced trees.
Surprisingly, however, there have been almost no results on bounding the work (time) of Adams’ algorithms, in
general nor on specific trees. Adams informally argues that his algorithms take O(n + m) work for weight-balanced
tree, but that is a very loose 
bound. Blelloch and Miller later show that similar algorithms for treaps [6], are optimal for
n
+ 1 ), and also parallel. Their algorithms, however, are specific for treaps. The problem with
work (i.e. Θ m log m
bounding the work of Adams’ algorithms, is that just bounding the time of S PLIT, J OIN and J OIN 2 with logarithmic
costs is not sufficient.3 One needs additional properties of the trees.
The contribution of this paper is to give first work-optimal bounds for Adams’ algorithms. We do this not only for
the weight-balanced trees. we bound the work and depth of Adams’ algorithms (union, intersection and difference)
for four different balancing shemes: AVL trees, red-black trees, weight-balanced trees and treaps. We analyze exactly
the algorithms in Figure 1, and the bounds hold when either input tree is larger. We show that with appropriate (and
simple) implementations of J OIN for each of the four balancing schemes, we achieve asymptotically optimal bounds
on work. Furthermore the algorithms have O(log n log m) depth, and hence are highly parallel. To prove the bounds
on work we show that our implementations of J OIN satisfy certain conditions based on a rank we define for each tree
type. In particular the cost of J OIN must be proportional to the difference in ranks of two trees, and the rank of the
result of a join must be at most one more than the maximum rank of the two arguments.
In addition to the theoretical analysis of the algorithms, we implemented parallel versions of all of the algorithms
on all four tree types and describe a set of experiments. Our implementation is generic in the sense that we use
common code for the algorithms in Figure 1, and only wrote specialized code for each tree type for the J OIN function.
Our implementations of J OIN are as described in this paper. We compare performance across a variety of parameters.
We compare across the tree types, and interestingly all four balance criteria have very similar performance. We
measure the speedup on up to 64 cores and achieve close to a 46-fold speedup. We compare to other implementations,
including the set implementation in the C++ Standard Template library (STL) for sequential performance, and parallel
weight-balanced B-trees (WBB-trees) [12] and the multi-core standard template library (MCSTL) [13] for parallel
performance. We also compare for different data distributions. The conclusion from the experiments is that although
not always as fast as (WBB-trees) [12] on uniform distributions, the generic code is quite competitive, and on keys
with a skewed overlap (two Gaussians with different means), our implementation is much better than all the other
baselines.
Related Work Parallel set operations on two ordered sets have been well-studied, but each previous algorithm only
works on one type of balance tree. Paul, Vishkin, and Wagener studied bulk insertion and deletion on 2-3 trees in the
PRAM model [24]. Park and Park showed similar results for red-black
 trees [23]. These algorithms are not based
n
on J OIN. Katajainen [16] claimed an algorithm with O m log( m
+ 1) work and O(log n) depth using 2-3 tree, but
was shown to contain some bugs so the bounds do not hold [6]. Akhremtsev and Sanders [4] (unpublished) recently
fixed that and proposed an algorithm based on (a, b)-trees with optimal work and O(log n) depth. Their algorithm
only works for (a, b)-trees, and they only gave algorithms on U NION. Besides, our algorithm is much simpler and
easy to be implemented than theirs. Blelloch and Miller showed a similar algorithm as Adams’ (as well as ours)
on treaps with optimal work and O(log n) depth on a EREW PRAM with scan operation using pipelines (implying
O(log n log m) depth on a plain EREW PRAM, and O(log∗ m log n) depth on a plain CRCW PRAM). The pipelining
2 Adams’

version had some bugs in maintaining the balance, but these were later fixed [14, 27].
the cost of J OIN, S PLIT, and J OIN 2 by the logarithm of the smaller tree is probably sufficient, but implementing a data structure with
such bounds is very much more complicated.
3 Bounding

3

is quite complicated. Our focus in this paper is in showing that very simple algorithm are work efficient and have
polylogarithmic depth, and less with optimizing the depth.
Many researchers have considered concurrent implementations of balanced search trees (e.g., [17, 18, 10, 21]).
None of these is work efficient for U NION since it is necessary to insert one tree into the other taking work at least
O(m log n). Furthermore the overhead of concurrency is likely to be very high.

2

Preliminaries

A binary tree is either a Leaf, or a node consisting of a left binary tree TL , a value (or key) v, and a right binary
tree TR , and denoted Node(TL , v, TR ). The size of a binary tree, or |T |, is 0 for a Leaf and |TL | + |TR | + 1 for a
Node(TL , v, TR ). The weight of a binary tree, or w(T ), is one more than its size (i.e., the number of leaves in the
tree). The height of a binary tree, or h(T ), is 0 for a Leaf, and max(h(TL ), h(TR )) + 1 for a Node(TL , v, TR ).
Parent, child, ancestor and descendant are defined as usual (ancestor and descendant are inclusive of the node itself).
The left spine of a binary tree is the path of nodes from the root to a leaf always following the left tree, and the right
spine the path to a leaf following the right tree. The in-order values of a binary tree is the sequence of values returned
by an in-order traversal of the tree.
A balancing scheme for binary trees is an invariant (or set of invariants) that is true for every node of a tree, and
is for the purpose of keeping the tree nearly balanced. In this paper we consider four balancing schemes that ensure
the height of every tree of size n is bounded by O(log n). For each balancing scheme we define the rank of a tree, or
r(T ).
AVL trees [3] have the invariant that for every Node(TL , v, TR ), the height of TL and TR √
differ by at most one.
This property implies that any AVL tree of size n has height at most logφ (n + 1), where φ = 1+2 5 is the golden ratio.
For AVL trees r(T ) = h(T ) − 1.
Red-black (RB) trees [5] associate a color with every node and maintain two invariants: (the red rule) no red
node has a red child, and (the black rule) the number of black nodes on every path from the root down to a leaf is
equal. Unlike some other presentations, we do not require that the root of a tree is black. Our proof of the work
bounds requires allowing a red root. We define the black height of a node T , denoted ĥ(T ) to be the number of black
nodes on a downward path from the node to a leaf (inclusive of the node). Any RB tree of size n has height at most
2 log2 (n + 1). In RB trees r(T ) = 2(ĥ(T ) − 1) if T is black and r(T ) = 2ĥ(T ) − 1 if T is red.
Weight-balanced (WB) trees with parameter α (also called BB[α] trees) [22] maintain for every T = Node(TL , v, TR )
L)
the invariant α ≤ w(T
w(T ) ≤ 1 − α. We say two weight-balanced trees T1 and T2 have like weights if Node(T1 , v, T2 ) is
2
1
weight balanced. Any α weight-balanced tree of size n has height at most log 1−α
n. For 11
< α ≤ 1 − √12 insertion
and deletion can be implemented on weight balanced trees using just single and double rotations [22, 7]. We require
the same condition for our implementation of J OIN, and in particular use α = 0.29 in experiments. For WB trees
r(T ) = dlog2 (w(T ))e − 1.
Treaps [25] associate a uniformly random priority with every node and maintain the invariant that the priority
at each node is no greater than the priority of its two children. Any treap of size n has height O(log n) with high
probability (w.h.p)4 . For treaps r(T ) = dlog2 (w(T ))e − 1.
For all the four balancing schemes r(T ) = Θ(log(|T | + 1)). The notation we use for binary trees is summarized
in Table 1.
A Binary Search Tree (BST) is a binary tree in which each value is a key taken from a total order, and for which
the in-order values are sorted. A balanced BST is a BST maintained with a balancing scheme, and is an efficient way
to represent ordered sets.
Our algorithms are based on nested parallelism with nested fork-join constructs and no other synchronization or
communication among parallel tasks.5 All algorithms are deterministic. We use work (W ) and span (S) to analyze
asymptotic costs, where the work is the total number of operations and span is the critical path. We use the simple
composition rules W (e1 || e2 ) = W (e1 ) + W (e2 ) + 1 and S(e1 || e2 ) = max(S(e1 ), S(e2 )) + 1. For sequential
4 Here
5 This

w.h.p. means that height O(c log n) with probability at least 1 − 1/nc (c is a constant)
does not preclude using our algorithms in a concurrent setting.

4

Notation
|T |
h(T )
ĥ(T )
r(T )
w(T )
p(T )
k(T )
L(T )
R(T )
expose(T )

Description
The size of tree T
The height of tree T
The black height of an RB tree T
The rank of tree T
The weight of tree T (i.e, |T | + 1)
The parent of node T
The value (or key) of node T
The left child of node T
The right child of node T
(L(T ), k(T ), R(T ))

Table 1: Summary of notation.
computation both work and span compose with addition. Any computation with W work and S span will run in time
T <W
P + S assuming a PRAM (random access shared memory) with P processors and a greedy scheduler [9, 8].

3

The JOIN Function

Here we describe algorithms for J OIN for the four balancing schemes we defined in Section 2. The function J OIN(TL , k, TR )
takes two binary trees TL and TR , and a value k, and returns a new binary tree for which the in-order values are a
concatenation of the in-order values of TL , then k, and then the in-order values of TR .
As mentioned in the introduction and shown in Section 4, J OIN fully captures what is required to rebalance a tree
and can be used as the only function that knows about and maintains the balance invariants. For AVL, RB and WB
trees we show that J OIN takes work that is proportional to the difference in rank of the two trees. For treaps the work
depends on the priority of k. All versions of J OIN are sequential so the span is equal to the work. Due to space
limitations, we describe the algorithms, state the theorems for all balancing schemes, but only show a proof outline for
AVL trees.
1 joinRight(TL , k, TR ) =
2
(l, k0 , c) = expose(TL );
3
if h(c) ≤ h(TR ) + 1 then
4
T 0 = Node(c, k, TR );
5
if h(T 0 ) ≤ h(l) + 1 then Node(l, k0 , T 0 )
6
else rotateLeft(Node(l, k0 , rotateRight(T 0 )))
7
else
8
T 0 = joinRight(c, k, TR );
9
T 00 = Node(l, k0 , T 0 );
10
if h(T 0 ) ≤ h(l) + 1 then T 00
11
else rotateLeft(T 00 )
12 join(TL , k, TR ) =
13
if h(TL ) > h(TR ) + 1 then joinRight(TL , k, TR )
14
else if h(TR ) > h(TL ) + 1 then joinLeft(TL , k, TR )
15
else Node(TL , k, TR )

Figure 2: AVL J OIN algorithm.
AVL trees. Pseudocode for AVL J OIN is given in Figure 2 and illustrated in Figure 6. Every node stores its own
height so that h(·) takes constant time. If the two trees TL and TR differ by height at most one, J OIN can simply
create a new Node(TL , k, TR ). However if they differ by more than one then rebalancing is required. Suppose that
h(TL ) > h(TR ) + 1 (the other case is symmetric). The idea is to follow the right spine of TL until a node c for which
h(c) ≤ h(TR ) + 1 is found (line 3). At this point a new Node(c, k, TR ) is created to replace c (line 4). Since either
5

1 joinRightRB(TL , k, TR ) =
2
if (r(TL ) = br(TR )/2c × 2) then
3
Node(TL , hk, redi, TR );
4
else
5
(L0 , hk0 , c0 i, R0 )=expose(TL );
6
T 0 = Node(L0 , hk0 , c0 i,joinRightRB(R0 , k, TR ));
7
if (c0 =black) and (c(R(T 0 )) = c(R(R(T 0 )))=red) then
8
c(R(R(T 0 )))=black;
9
T 00 =rotateLeft(T 0 )
10
else T 00
11 joinRB(TL , k, TR ) =
12
if br(TL )/2c > br(TR )/2c then
13
T 0 =joinRightRB(TL , k, TR );
14
if (c(T 0 )=red) and (c(R(T 0 ))=red) then
15
Node(L(T 0 ), hk(T 0 ), blacki, R(T 0 ))
16
else T 0
17
else if br(TR )/2c > br(TL )/2c then
18
T 0 =joinLeftRB(TL , k, TR );
19
if (c(T 0 )=red) and (c(L(T 0 ))=red) then
20
Node(L(T 0 ), hk(T 0 ), blacki, R(T 0 ))
21
else T 0
22
else if (c(TL )=black) and (c(TR )=black) then
23
Node(TL , hk, redi, TR )
24
else Node(TL , hk, blacki, TR )

Figure 3: RB J OIN algorithm.
1 joinRightWB(TL , k, TR ) =
2
(l, k0 , c)=expose(TL );
3
if (balance(|TL |, |TR |) then Node(TL , k, TR ));
4
else
5
T 0 = joinRightWB(c, k, TR );
6
(l1 , k1 , r1 ) = expose(T 0 );
7
if like(|l|, |T 0 |) then Node(l, k0 , T 0 )
8
else if (like(|l|, |l1 |)) and (like(|l| + |l1 |, r1 )) then
9
rotateLeft(Node(l, k0 , T 0 ))
10
else rotateLeft(Node(l, k0 ,rotateRight(T 0 )))
11 joinWB(TL , k, TR ) =
12
if heavy(TL , TR ) then joinRightWB(TL , k, TR )
13
else if heavy(TR , TL ) then joinLeftWB(TL , k, TR )
14
else Node(TL , k, TR )

Figure 4: WB J OIN algorithm.
1 joinTreap(TL , k, TR ) =
2
if prior(k, k1 ) and prior(k, k2 ) then Node(TL , k, TR )
3
else (l1 , k1 , r1 )=expose(TL );
4
(l2 , k2 , r2 )=expose(TR );
5
if prior(k1 , k2 ) then
6
Node(l1 , k1 ,joinTreap(r1 , k, TR ))
7
else Node(joinTreap(TL , k, l2 ),k2 , r2 )

Figure 5: Treap J OIN algorithm.
h(c) = h(TR ) or h(c) = h(TR ) + 1, the new node satisfies the AVL invariant, and its height is one greater than c. The
increase in height can increase the height of its ancestors, possibly invalidating the AVL invariant of those nodes. This

6

can be fixed either with a double rotation if invalid at the parent (line 6) or a single left rotation if invalid higher in the
tree (line 11), in both cases restoring the height for any further ancestor nodes. The algorithm will therefore require at
most two rotations.
……

The right
branch in 𝑇𝑇𝐿𝐿

𝑘𝑘
k

p

a

c

𝑇𝑇𝑅𝑅

Step 1: connect

……

𝑇𝑇1

𝑇𝑇2

(h or
h+1)

d

𝑇𝑇𝑅𝑅

(h)

c

p
a

k

p

c

h+2
(h or
h+1)

Step 2: rebalance

……

𝑇𝑇1

(h or
h+1)

a

d

𝑇𝑇2

𝑇𝑇𝑅𝑅

(h or
h+1)

(h)

Rebalance
required if
ℎ 𝑇𝑇1 = ℎ
ℎ 𝑇𝑇2 = ℎ + 1

𝑇𝑇1

(h)

k
c1

𝐿𝐿 𝑇𝑇2
(h or
h-1)

c2
𝑅𝑅 𝑇𝑇2
(h or
h-1)

d

h+2

𝑇𝑇𝑅𝑅

(h)

Figure 6: An example for J OIN on AVL trees (h(TL ) > h(TR ) + 1). We first follow the right spine of TL until a
subtree of height at most h(Tr ) + 1 is found (i.e., T2 rooted at c). Then a new Node(c, k, TR ) is created, replacing
c (Step 1). If h(T1 ) = h and h(T2 ) = h + 1, the node p will no longer satisfy the AVL invariant. A double rotation
(Step 2) restores both balance and its original height.
Lemma 1. For two AVL trees TL and TR , the AVL J OIN algorithm works correctly, runs with O(|h(TL ) − h(TR )|)
work, and returns a tree satisfying the AVL invariant with height at most 1 + max(h(TL ), h(TR )).
Proof outline. Since the algorithm only visits nodes on the path from the root to c, and only requires at most two
rotations, it does work proportional to the path length. The path length is no more than the difference in height of the
two trees since the height of each consecutive node along the right spine of TL differs by at least one. Along with the
case when h(TR ) > h(TL ) + 1, which is symmetric, this gives the stated work bounds. The resulting tree satisfies the
AVL invariants since rotations are used to restore the invariant (details left out). The height of any node can increase
by at most one, so the height of the whole tree can increase by at most one.
Red-black Trees. Tarjan describes how to implement the J OIN function for red-black trees [28]. Here we describe
a variant that does not assume the roots are black (this is to bound the increase in rank by U NION). The pseudocode
is given in Figure 3. We store at every node its black height ĥ(·). The first case is when ĥ(TR ) = ĥ(TL ). Then if
both k(TR ) and k(TL ) are black, we create red Node(TL , k, TR ), otherwise we create black Node(TL , k, TR ). The
second case is when ĥ(TR ) < ĥ(TL ) = ĥ (the third case is symmetric). Similarly to AVL trees, J OIN follows the right
spine of TL until it finds a black node c for which ĥ(c) = ĥ(TR ). It then creates a new red Node(c, k, TR ) to replace
c. Since both c and TR have the same height, the only invariant that can be violated is the red rule on the root of TR ,
the new node, and its parent, which can all be red. In the worst case we may have three red nodes in a row. This is
fixed by a single left rotation: if a black node v has R(v) and R(R(v)) both red, we turn R(R(v)) black and perform
a single left rotation on v. The update is illustrated in Figure 7. The rotation, however can again violate the red rule
between the root of the rotated tree and its parent, requiring another rotation. The double-red issue might proceed up
to the root of TL . If the original root of TL is red, the algorithm may end up with a red root with a red child, in which
case the root will be turned black, turning TL rank from 2ĥ − 1 to 2ĥ. If the original root of TL is black, the algorithm
may end up with a red root with two black children, turning the rank of TL from 2ĥ − 2 to 2ĥ − 1. In both cases the
rank of the result tree is at most 1 + r(TL ).
Lemma 2. For two RB trees TL and TR , the RB J OIN algorithm works correctly, runs with O(|r(TL ) − r(TR )|) work,
and returns a tree satisfying the red-black invariants and with rank at most 1 + max(r(TL ), r(TR )).
The proof is similar as Lemma 1.
Weight Balanced Trees. We store the weight of each subtree at every node. The algorithm for joining two weightbalanced trees is similar to that of AVL trees and RB trees. The pseudocode is shown in Figure 4. The like function
in the code returns true if the two input tree sizes are balanced, and false otherwise. If TL and TR have like weights
the algorithm returns a new Node(TL , k, TR ). Suppose |TR | ≤ |TL |, the algorithm follows the right branch of TL
until it reaches a node c with like weight to TR . It then creates a new Node(c, k, TR ) replacing c. The new node will
have weight greater than c and therefore could imbalance the weight of c’s ancestors. This can be fixed with a single
or double rotation (as shown in Figure 8) at each node assuming α is within the bounds given in Section 2.
7

Red node

……

Black node

The right
branch in 𝑇𝑇𝐿𝐿
g

a

k

p
b

𝑇𝑇1

𝑇𝑇2

(h)

(h)

Step 1: connect (when 𝑝𝑝 is red)

𝑇𝑇𝑅𝑅

𝑘𝑘

g
a

c

d

𝑇𝑇3

𝑇𝑇1

𝑇𝑇𝑅𝑅

(h)

(h)

c

d

𝑇𝑇3

𝑇𝑇𝑅𝑅

(h)

(h)

Step 2: rebalance (when 𝑝𝑝 is red)
……

p

r

k

g

v

v

k

𝑇𝑇2

(h)

(h)

1) When k(𝑇𝑇𝐿𝐿 ) is red, after rotation on 𝐿𝐿(𝑇𝑇𝐿𝐿 ):

Rank increases from 2ℎ� + 1 to 2(ℎ� + 1)
2) When k(𝑇𝑇𝐿𝐿 ) is black, after rotation on 𝑘𝑘(𝑇𝑇𝐿𝐿 ):

r

p

b

If the unbalance propagate to the root of 𝑇𝑇𝐿𝐿 :

r

Rebalance required on:
𝒈𝒈: 𝑝𝑝 and 𝑘𝑘 are red
𝒑𝒑: 𝑘𝑘 and 𝑑𝑑 are red,
𝑝𝑝 is black

……

Step 3: adjust on root

w

Node of either color

a

b

c

d

𝑇𝑇1

(h)

𝑇𝑇2

(h)

𝑇𝑇3

𝑇𝑇𝑅𝑅

v

v

u

r

Rank increases from 2ℎ� to 2ℎ� + 1

u

(h)

(h)

Figure 7: An example of J OIN on red-black trees (ĥ = ĥ(TL ) > ĥ(TR )). We follow the right spine of TL until we
find a black node with the same black height as TR (i.e., c). Then a new red Node(c, k, TR ) is created, replacing c
(Step 1). The only invariant that can be violated is when either c’s previous parent p or TR ’s root d is red. If so, a left
rotation is performed at some black node. Step 2 shows the rebalance when p is red. The black height of the rotated
subtree (now rooted at p) is the same as before (h + 1), but the parent of p might be red, requiring another rotation. If
the red-rule violation propagates to the root, the root is either colored red, or rotated left (Step 3).
Lemma 3. For two α weight-balanced trees TL and TR and α ≤ 1 − √12 ≈ 0.29, the weight-balanced J OIN algorithm
works correctly, runs with O(| log(w(TL )/w(TR ))|) work, and returns a tree satisfying the α weight-balance invariant
and with rank at most 1 + max(r(TL ), r(TR )).
The proof is shown in the Appendix.
Treaps. The treap J OIN algorithm (as in Figure 5) first picks the key with the highest priority among k, k(TL ) and
k(TR ) as the root. If k is the root then the we can return Node(TL , k, TR ). Otherwise, WLOG, assume k(TL ) has
a higher priority. In this case k(TL ) will be the root of the result, L(TL ) will be the left tree, and R(TL ), k and TR
will form the right tree. Thus J OIN recursively calls itself on R(TL ), k and TR and uses result as k(TL )’s right child.
When k(TR ) has a higher priority the case is symmetric. The cost of J OIN is therefore the depth of the key k in the
resulting tree (each recursive call pushes it down one level). In treaps the shape of the result tree, and hence the depth
of k, depend only on the keys and priorities and not the history. Specifically, if a key has the tth highest priority among
the keys, then its expected depth in a treap is O(log t) (also w.h.p.). If it is the highest priority, for example, then it
remains at the root.
Lemma 4. For two treaps TL and TR , if the priority of k is the t-th highest among all keys in TL ∪ {k} ∪ TR , the treap
J OIN algorithm works correctly, runs with O(log t + 1) work in expectation and w.h.p., and returns a tree satisfying
the treap invariant with rank at most 1 + max(r(TL ), r(TR )).
From the above lemmas we can get the following fact for J OIN.
Theorem 1. For AVL, RB and WB trees J OIN(TL , k, TR ) does O(|r(TL ) − r(TR )|) work. For treaps J OIN does
O(log t) work in expectation if k has the t-th highest priority among all keys. For AVL, RB, WB trees and treaps, J OIN
returns a tree T for which the rank satisfies max(r(TL ), r(TR )) ≤ r(T ) ≤ 1 + max(r(TL ), r(TR )).
8

……

(1). Single Rotation
u

(0)
……
v
1

1

The right
branch in 𝑇𝑇𝐿𝐿

𝐴𝐴

𝐴𝐴

5

2

4

𝐵𝐵

𝐶𝐶

4

2

u

3

v

……

𝐵𝐵

3

5

𝐶𝐶

𝐷𝐷

(2). Double Rotation
3

𝐷𝐷

u

(0): The rebalance process is currently
at 𝑣𝑣, which means the tree rooted at 𝑢𝑢
and all of its subtrees are balanced.
(1): The result of the single rotation.
(2): The result of the double rotation.

v

1

2

4

5

𝐴𝐴

𝐵𝐵

𝐶𝐶

𝐷𝐷

Figure 8: An illustration of single and double rotations possibly needed to rebalance weight-balanced trees. In the
figure the subtree rooted at u has become heavier due to joining in TL and its parent v now violates the balance
invariant.

4

Other Functions Using JOIN

In this section, we describe algorithms for various functions that use just J OIN. The algorithms are generic across
balancing schemes. The pseudocodes for the algorithms in this section is shown in Figure 1.
Split. For a BST T and key k, S PLIT(T, k) returns a triple (TL , b, TR ), where TL (TR ) is a tree containing all keys
in T that are less (larger) than k, and b is a flag indicating whether k ∈ T . The algorithm first searches for k in T ,
splitting the tree along the path into three parts: keys to the left of the path, k itself (if it exists), and keys to the right.
Then by applying J OIN, the algorithm merges all the subtrees on the left side (using keys on the path as intermediate
nodes) from bottom to top to form TL , and merges the right parts to form TR . Figure 9 gives an example.
Split 𝑇𝑇 with key 42:

𝑇𝑇𝐿𝐿 = 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗(

^

12
^

^

^

^

22
^

^

36

15
^

17

5

51
17

5

80

30
^

, 25 , 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗(

8

25

13
8

13

^

42
^

^

70
^

^

95
^

^

^

^

𝑇𝑇𝑅𝑅 = 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗(

12
^

^

15
^

,

^

51

,

30
^

36

,

^

)

)

^

22

^

^

^

80

,

70
^

95
^

^

)
^

𝑏𝑏 = 𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡

Figure 9: An example of S PLIT in a BST with key 42. We first search for 42 in the tree and split the tree by the
searching path, then use J OIN to combine trees on the left and on the right respectively, bottom-top.
Theorem 2. The work of S PLIT(T, k) is O(log |T |) for all balancing schemes described in Section 3 (w.h.p. for
treaps). The two resulting trees TL and TR will have rank at most r(T ).
9

Proof. We only consider the work of joining all subtrees on the left side. The other side is symmetric. Suppose we have
l subtrees on the left side, denoted from bottom to top as T1 , T2 , . . . Tl . We have that r(T1 ) ≤ r(T2 ) ≤ · · · ≤ r(Tl ).
As stated above, we consecutively join T1 and T2 returning T20 , then join T20 with T3 returning T30 and so forth, until
all trees are merged. The overall work of S PLIT is the sum of the cost of l − 1 J OIN functions.
For AVL trees, red-black trees and weight-balanced trees, recall Theorem 1 that we have r(Ti0 ) ≤ r(Ti ) + 1, so
r(Ti0 ) ≤ r(Ti ) + 1 ≤ r(Ti+1 ) + 1. According to Theorem 1, the work of a single operation is O(|r(Ti+1 ) − r(Ti0 )|).
Pl
Pl
The overall complexity is i=1 |r(Ti+1 ) − r(Ti0 )| ≤ i=1 r(Ti+1 ) − r(Ti0 ) + 2 = O(r(T )) = O(log |T |).
For treaps, each J OIN uses the key with the highest priority since the key is always on a upper level. Hence by
Lemma 4, the complexity of each J OIN is O(1) and the work of split is at most O(log |T |) w.h.p.
Also notice that when getting the final result TL and TR , the last step is a J OIN on two trees, the larger one of
which is a subtree of the original T . Thus the rank of the two trees to be joined is of rank at most r(T ) − 1, according
to Theorem 1 we have r(TL ) and r(TR ) at most r(T ).
Join2. J OIN 2(TL , TR ) returns a binary tree for which the in-order values is the concatenation of the in-order values
of the binary trees TL and TR (the same as J OIN but without the middle key). For BSTs, all keys in TL have to be less
than keys in TR . J OIN 2 first finds the last element k (by following the right spine) in TL and on the way back to root,
joins the subtrees along the path, which is similar to S PLIT TL by k. We denote the result of dropping k in TL as TL0 .
Then J OIN(TL0 , k, TR ) is the result of J OIN 2. Unlike J OIN, the work of J OIN 2 is proportional to the rank of both trees
since both S PLIT and J OIN take at most logarithmic work.
Theorem 3. The work of J OIN 2(TL , TR ) is O(r(TL ) + r(TR )) for all balancing schemes described in Section 3
(bounds are w.h.p for treaps).
Union, Intersect and Difference. U NION(T1 , T2 ) takes two BSTs and returns a BST that contains the union of all
keys. The algorithm uses a classic divide-and-conquer strategy, which is parallel. At each level of recursion, T1 is split
by k(T2 ), breaking T1 into three parts: one with all keys smaller than k(T2 ) (denoted as L1 ), one in the middle either
of only one key equal to k(T2 ) (when k(T2 ) ∈ T1 ) or empty (when k(T2 ) ∈
/ T1 ), the third one with all keys larger than
k(T2 ) (denoted as R1 ). Then two recursive calls to U NION are made in parallel. One unions L(T2 ) with L1 , returning
TL , and the other one unions R(T2 ) with R1 , returning TR . Finally the algorithm returns J OIN(TL , k(T2 ), TR ), which
is valid since k(T2 ) is greater than all keys in TL are less than all keys in TR .
The functions I NTERSECT(T1 , T2 ) and D IFFERENCE(T1 , T2 ) take the intersection and difference of the keys in
their sets, respectively. The algorithms are similar to U NION in that they use one tree to split the other. However, the
method for joining is different. For I NTERSECT, J OIN 2 is used instead of J OIN if the root of the first is not found in
the second. For D IFFERENCE, J OIN 2 is used anyway because k(T2 ) should be excluded in the result tree. The base
cases are also different in the obvious way.
Theorem 4 (Main Theorem). For all the four balance schemes mentioned in Section 3, the work and span of the
algorithm (asshownin Figure
1) of U NION, I NTERSECT or D IFFERENCE on two balanced BSTs of sizes m and n
n
(n ≥ m) is O m log
+ 1 and O(log n log m) respectively (the bound is in expectation for treaps).
m
A generic proof of Theorem 4 working for all the four balancing schemes will be shown in the next section.
The work bound for these algorithms is optimal in the comparison-based model. In particular considering all possi
n
ble interleavings, the minimum number of comparisons required to distinguish them is log m+n
= Θ m log m
+1
n
[15].
Other Functions. Many other functions can be implemented with J OIN. Pseudocode for I NSERT and D ELETE was
given in Figure 1. For a tree of size n they both take O(log n) work.

5

The Proof of the Main Theorem

In this section we prove Theorem 4, for all the four balance schemes (AVL trees, RB trees, WB trees and treaps) and all
three set algorithms (U NION, I NTERSECT, D IFFERENCE) from Figure 1. For this purpose we make two observations.
The first is that all the work for the algorithms can be accounted for within a constant factor by considering just the
10

Notation
Tp
Td
n
m
Tp (v), v ∈ Tp
Td (v), v ∈ Tp
si
vkj
d(v)

Description
The pivot tree
The decomposed tree
max(|Tp |, |Td |)
min(|Tp |, |Td |)
The subtree rooted at v in Tp
The tree from Td that v splits6
The number of nodes in layer i
The j-th node on layer k in Tp
The number of nodes attached to a layer
root v in a treap

Table 2: Descriptions of notations used in the proof.
work done by the S PLITs and the J OINs (or J OIN 2s), which we refer to as split work and join work, respectively. This
is because the work done between each split and join is constant. The second observation is that the split work is
identical among the three set algorithms. This is because the control flow of the three algorithms is the same on the
way down the recursion when doing S PLITs—the algorithms only differ in what they do at the base case and on the
way up the recursion when they join.
Given these two observations, we prove the bounds on work by first showing that the join work is asymptotically
at most as large as the split work (by showing that this is true at every node of the recursion for all three algorithms),
and then showing that the split work for U NION (and hence the others) satisfies our claimed bounds.
We start with some notation, which is summarized in Table 2. In the three algorithms the first tree (T1 ) is split
by the keys in the second tree (T2 ). We therefore call the first tree the decomposed tree and the second the pivot tree,
denoted as Td and Tp respectively. The tree that is returned is denoted as Tr . Since our proof works for either tree
being larger, we use m = min(|Tp |, |Td |) and n = max(|Tp |, |Td |). We denote the subtree rooted at v ∈ Tp as Tp (v),
and the tree of keys from Td that v splits as Td (v) (i.e., S PLIT(v, Td (v)) is called at some point in the algorithm). For
v ∈ Tp , we refer to |Td (v)| as its splitting size.
Figure 10 (a) illustrates the pivot tree with the splitting size annotated on each node. Since S PLIT has logarithmic
work, we have,


X
split work = O
(log |Td (v)| + 1),
v∈Tp

which we analyze in Theorem 6. We first, however, show that the join work is bounded by the split work. We use the
following Lemma, which is proven in the appendix.
Lemma 5. For Tr =U NION(Tp , Td ) on AVL, RB or WB trees, if r(Tp ) > r(Td ) then r(Tr ) ≤ r(Tp ) + r(Td ).
Theorem 5. For each function call to U NION, I NTERSECT or D IFFERENCE on trees Tp (v) and Td (v), the work to do
the J OIN (or J OIN 2) is asymptotically no more than the work to do the S PLIT.
Proof. For I NTERSECT or D IFFERENCE, the cost of J OIN (or J OIN 2) is O(log(|Tr | + 1)). Notice that D IFFER ENCE returns the keys in Td \Tp . Thus for both I NTERSECT and D IFFERENCE we have Tr ⊆ Td . The join work is
O(log(|Tr | + 1)), which is no more than O(log(|Td | + 1)) (the split work).
For U NION, if r(Tp ) ≤ r(Td ), the J OIN will cost O(r(Td )), which is no more than the split work.
Consider r(Tp ) > r(Td ) for AVL, RB or WB trees. The rank of L(Tp ) and R(Tp ), which are used in the recursive
calls, are at least r(Tp ) − 1. Using Lemma 5, the rank of the two trees returned by the two recursive calls will be at
least (r(Tp ) − 1) and at most (r(Tp ) + r(Td )), and differ by at most O(r(Td )) = O(log |Td | + 1). Thus the join cost
is O(log |Td | + 1), which is no more than the split work.
6 The

nodes in Td (v) form a subset of Td , but not necessarily a subtree. See details later.

11

50
20

30

3

1

1
𝑣𝑣01

13
7

6
5

1

12

4

5
1

3

4

(a)

layer
3
2
0

2

3
4

17

8

11
7

Total cost:
log 50 + log 20 + ⋯ + log 8 +

𝑣𝑣11

𝑣𝑣21
𝑣𝑣02

𝑣𝑣31
𝑣𝑣12

(b)

𝑠𝑠3 = 1

𝑣𝑣22
𝑣𝑣03

𝑣𝑣04

𝑣𝑣13

𝑠𝑠2 = 2

𝑣𝑣05

� 𝑥𝑥𝑖𝑖𝑖𝑖 ≤ 𝑀𝑀

𝑠𝑠1 = 3

𝑗𝑗

𝑠𝑠0 = 5

Figure 10: An illustration of splitting tree and layers. The tree in (a) is Tp , the dashed circle are the exterior nodes.
The numbers on the nodes are the sizes of the tree from Td to be split by this node, i.e., the “splitting size” |Td (v)|. In
(b) is an illustration of layers on an AVL tree.
Consider r(Tp ) > r(Td ) for treaps. If r(Tp ) > r(Td ), then |Tp | ≥ |Td |. The root of Tp has the highest priority
|T |+|T |
among all |Tp | keys, so on expectation it takes at most the p|Tp | d ≤ 2-th place among all the |Td | + |Tp | keys. From
Lemma 4 we know that the cost on expectation is E[log t] + 1 ≤ log E[t] + 1 ≤ log 2 + 1, which is a constant.
This implies the total join work is asymptotically bounded by the split work.
We now analyze the split work. We do this by layering the pivot tree starting at the leaves and going to the root
and such that nodes in a layer are not ancestors of each other. We define layers based on the ranks and denote the size
of layer i as si . We show that si shrinks geometrically, which helps us prove our bound on the split work. For AVL
and RB trees, we group the nodes with rank i in layer i. For WB trees and treaps, we put a node v in layer i iff v has
rank i and v’s parent has rank strictly greater than i. Figure 10 (b) shows an example of the layers of an AVL tree.
Definition 1. In a BST, a set of nodes V is called a disjoint set if and only if for any two nodes v1 , v2 in V , v1 is not
the ancestor of v2 .
P
Lemma 6. For any disjoint set V ⊆ Tp , v∈V |Td (v)| ≤ |Td |.
The proof of this Lemma is straightforward.
Lemma 7. For an AVL, RB, WB tree or a treap of size N , each layer is a disjoint set, and si ≤
constant c > 1.

N
cbi/2c

holds for some

Proof. For AVL, RB, WB trees and treaps, a layer is obviously a disjoint set: a node and its ancestor cannot lie in the
same layer.
For AVL trees, consider a node in layer 2, it must have at least two descendants in layer 0. Thus s0 ≥ 2s2 . Since
an AVL tree with its leaves removed is still an AVL tree, we have si ≥ 2si+2 . Since s0 and s1 are no more than N ,
N
we can get that si < 2bi/2c
.
For RB trees, the number of black nodes in layer 2i is more than twice as many as in layer 2(i + 1) and less than
four times as many as in layer 2(i + 1), i.e., s2i ≥ 2s2i+2 . Also, the number of red nodes in layer 2i + 1 is no more
N
than the black nodes in layer 2i. Since s0 and s1 are no more than N , si < 2bi/2c
.
12

For WB trees and treaps, the rank is defined as dlog2 (w(T ))e − 1, which means that a node in layer i has weight
at least 2i + 1. Thus si ≤ (N + 1)/(2i + 1) ≤ N/2i .
Not all nodes in a WB tree or a treap are assigned to a layer. We call a node a layer root if it is in a layer. We attach
each node u in the tree to the layer root that is u’s ancestor and has the same rank as u. We denote d(v) as the number
of descendants attached to a layer root v.
Lemma 8. For WB trees and treaps, if v is a layer root, d(v) is less than a constant (in expectation for treaps).
Furthermore, the random variables d(v) for all layer roots in a treap are i.i.d. (See the proof in the Appendix.)
By applying Lemma 7 and 8 we prove the split work. In the following proof, we denote vkj as the j-th node in
layer k.

n
+1 .
Theorem 6. The split work in U NION, I NTERSECT and D IFFERENCE on two trees of size m and n is O m log m
P

Proof. The total work of S PLIT is the sum of the log of all the splitting sizes on the pivot tree O
log(|T
(v)|
+
1)
.
d
v∈Tp
Denote l as the number of layers in the tree. Also, notice that in the pivot tree, in each layer there are at most |Td |
nodes with |Td (vkj )| > 0. Since P
those nodes with splitting sizes of 0 will not cost any work, we can assume si ≤ |Td |.
We calculate the dominant term v∈Tp log(|Td (v)| + 1) in the complexity by summing the work across layers:
sk
l X
X
k=0 j=1

log(|Td (vkj )| + 1) ≤
=

l
X

P

l
X


sk log

l
X
k=0


sk log

|Td |
sk

|Td (vkj )| + 1



sk

k=0

k=0

We split it into two cases. If |Td | ≥ |Tp |,

j

sk log

|Td |
+1
sk



always dominates 1. we have:

|Td |
+1
sk


=

l
X


sk log

k=0

≤

l
X
k=0

≤ 2

m
cbk/2c


n
+1
sk


n
log
+1
m/cbk/2c

(1)

(2)

l/2
X
n
m
log
k
c
m/ck

k=0

l/2
l/2
X
X
m
n
m
log
+
2
k k
ck
m
c
k=0
k=0

n
= O m log
+ O(m)

mn

= O m log
+1
m

≤ 2

(3)

If |Td | < |Tp |, |Tskd | can be less than 1 when k is smaller, thus the sum should be divided into two parts. Also note
that we only sum over the nodes with splitting size larger than 0. Even though there could be more than |Td | nodes in

13

one layer in Tp , only |Td | of them should count. Thus we assume sk ≤ |Td |, and we have:
l
X
k=0


sk log

|Td |
+1
sk


=

l
X


sk log

k=0
2 logc

k=0

(4)

|Td | log(1 + 1)

l
X

+



n

Xm

≤

m
+1
sk

k=2 logc

n
n
m

cbk/2c


log
l

m
+1
n/cbk/2c

−logc


(5)

m

2 X n
n
m
k0
≤ O m log
+2
0 log c
k
m
c
k0 =0


n
+ O(m)
= O m log
m


n
= O m log( + 1)
m



(6)

From (1) to (2) and (4) to (5) we apply Lemma 7 and the fact that f (x) = x log( nx + 1) is monotonically increasing
when x ≤ n.
For WB trees and treaps, the calculation above only includes the log of splitting
size on layer roots. We need to

n
further prove the total sum of the log of all splitting size is still O m log m
+ 1 . Applying Lemma 8, the expectation
is less than:


xk
l X
X
d(vkj ) log((Td (vkj ) + 1)
E2
k=0 j=1

= E[d(vkj )] × 2

xk
l X
X

log((Td (vkj ) + 1)

k=0 j=1



n
+1
= O m log
m
For WB trees d(vkj ) is no more than a constant, so we can also come to the same bound.
To conclude, the split work on all four balancing schemes of all three functions is O m log

n
m


+1 .

Theorem 7. The total work of U NION, I NTERSECT
or D IFFERENCE of all four balancing schemes on two trees of

n
size m and n (m ≥ n) is O m log m
+1 .
This directly follows Theorem 5 and 6.
Theorem 8. The span of U NION and I NTERSECT or D IFFERENCE on all four balancing schemes is O(log n log m).
Here n and m are the sizes of the two tree.
Proof. For the span of these algorithms, we denote D(h1 , h2 ) as the span on U NION, I NTERSECT or D IFFERENCE on
two trees of height h1 and h2 . According to Theorem 5, the work (span) of S PLIT and J OIN are both O(log |Td |) =
O(h(Td )). We have:
D(h(Tp ), h(Td )) ≤ D(h(Tp ) − 1, h(Td )) + 2h(Td )
Thus D(h(Tp ), h(Td )) ≤ 2h(Tp )h(Td ) = O(log n log m).
Combine Theorem 7 and 8 we come to Theorem 4.

14

6

Experiments

To evaluate the performance of our algorithms we performed several experiments across the four balancing schemes
using different set functions, while varying the core count and tree sizes. We also compare the performance of our
implementation to other existing libraries and algorithms.
Experiment setups and baseline algorithms For the experiments we use a 64-core machine with 4 x AMD Opteron(tm)
Processor 6278 (16 cores, 2.4GHz, 1600MHz bus and 16MB L3 cache). Our code was compiled using the g++ 4.8
compiler with the Cilk Plus extensions for nested parallelism. The only compilation flag we used was the -O2 optimization flag. In all our experiments we use keys of the double data type. The size of each node is about 40 bytes,
including the two child pointers, the key, the balance information, the size of the subtree, and a reference count. We
generate multiple sets varying in size from 104 to 108 . Depending on the experiment the keys are drawn either from
an uniform or a Gaussian distribution. We use µ and σ to denote the mean and the standard deviation in Gaussian
distribution. Throughout this section n and m represent the two input sizes for functions with two input sets (n ≥ m).
We test our algorithm by comparing it to other available implementations. This includes the sequential version
of the set functions defined in the C++ Standard Template Library (STL) [20] and STL’s std::set (implemented
by RB tree). The STL supports the set operations set union, set intersection, and set difference on
any container class. Using an std::vector these algorithms achieve a runtime of O(m + n). Since the STL does
not offer any parallel version of these functions we could only use it for sequential experiments. To see how well
our algorithm performs in a parallel setting, we compare it to parallel WBB-trees [12] and the MCSTL library [13].
WBB-trees, as well as the MCSTL, offer support for bulk insertions and deletions. They process the bulk updates
differently. The MCSTL first splits the main tree among p processors, based on the bulk sequence, and then inserts
the chunks dynamically into each subtree. The WBB-tree recursively inserts the bulk in parallel into the main tree. To
deal with heavily skewed sequences they use partial tree reconstruction for fixing imbalances, which takes constant
amortized time. The WBB-tree has a more cache aware layout, leading to a better cache utilization compared to both
the MCSTL and our implementation. To make a comparison with these implementations we use their bulk insertions,
which can also be viewed as an union of two sets. However notice that WBB-trees take the bulk in the form of a sorted
sequence, which gives them an advantage due to the faster access to the one array than to a tree, and far better cache
performance (8 keys per cache line as opposed to 1).

Comparing the balancing schemes and functions To compare the four balancing schemes we choose U NION as
the representative operation. Other operations would lead to similar results since all operations except J OIN are generic
across the trees. We compare the schemes across different thread counts and different sizes.
Figure 11 (a) shows the runtime of U NION for various tree sizes and all four balancing schemes across 64 cores.
The times are very similar among the balancing schemes—they differ by no more than 10%.
Figure 11 (b) shows the speedup curves for U NION on varying core numbers with two inputs of size 108 . All
balancing schemes achieve a speedup of about 45 on 64 cores, and about 30 on 32 cores. The less-than-linear speedup
beyond 32 cores is not due to lack of parallelism, since when we ran the same experiments on significantly smaller
input (and hence less parallelism) we get very similar curves (not shown). Instead it seems to be due to saturation of
the memory bandwidth.
We use the AVL tree as the representative tree to compare different functions. Figure 11 (c) compares the U NION,
I NTERSECT and D IFFERENCE functions. The size of the larger tree is fixed (108 ), while the size of the smaller tree
varies from 104 to 108 . As the plot indicates, the three functions have very similar performance.
The experiments are a good indication of the performance of different balancing schemes and different functions,
while controlling other factors. The conclusion is that all schemes perform almost equally on all the set functions. It
is not surprising that all balancing schemes achieve similar performance because the dominant cost is in cache misses
along the paths in the tree, and all schemes keep the trees reasonably balanced. The AVL tree is always slightly faster
than the other trees and this is likely due to the fact that they maintain a slightly stricter balance than the other trees,
and hence the paths that need to be traversed are slightly shorter. For different set functions the performance is also as
expected given the similarity of the code.
15

Union, m = n = 108

Union, m = 108 , Threads = 64

Sequential union, m = 108

m = 108 , Threads = 64

50

100

100

102

105

106
n

107

AVL
WB
Treap
RB

10
0

108

0

20

(a)

0

10

−2

10

10−3

10

105

(e)

106
n, m

107

108

−1

10

−2

10

104

106
n

107

108

Union, m = n = 108

−2

10

10−3
10−4
106
n, m

105

(d)

10−1

−4

105

10−3

108

100

10−3
104

107

Join-AVL
std::vector
std::set

10−2

101

10

104

106
m

10−1

Union, Threads = 64

Time (s)

−1

10−4

105

100

(c)

Join-AVL
WBB
MCSTL

101
Time (s)

Time (s)

10

104

60

Union, Threads = 64, σ = 0.25

Join-AVL
WBB
MCSTL

0

Union
Intersect
Difference

(b)

Union, Threads = 64
101

40
Threads

10−2

107

108

Time (s)

104

20

10−1

Time (s)

AVL
WB
Treap
RB

10−2

101

30

Time (s)

10

Speedup

Time (s)

40
−1

Join-AVL
WBB
MCSTL
0

0.2

0.4

(g)

(f)

0.6
σ

0.8

1

101

Join-AVL
WBB
MCSTL

100
0

20

40
Threads

60

(h)

Figure 11: (a) Times for U NION as a function of size (n = 108 ) for different BBSTs; (b) speed up of U NION for
different BBSTs; (c) times for various operations on AVL trees as a function of size (n = 108 ); (d) comparing STLs
set union with our U NION; (e, f, g, h) comparing our U NION to other parallel search trees; (e, h) input keys are
uniformly distributed doubles in the range of [0, 1]; (f, g) inputs keys follow a normal distribution of doubles - the
mean of the main tree is always µ1 = 0, while the mean of the bulk is µ2 = 1. Figure (f) uses a standard deviation of
σ = 0.25, while Figure (g) shows the performance across different standard deviations.
Given the result that the four balancing schemes do not have a big difference in timing and speedup, nor do the
three set functions, in the following experiments we use the AVL tree along with U NION to make comparisons with
other implementations.
Comparing to sequential implementations The STL supports set union on any sorted container class, including
sets based on red-black trees, and sorted vectors (arrays). The STL set union merges the two sorted containers by
moving from left to right on the two inputs, comparing the current values, and writing the lesser to the end of the output.
For two inputs of size n and m, m ≤ n, it takes O(m+n) time on std::vectors, and O((n+m) log(n+m)) time
on std::set (each insertion at the end of the output red-black tree takes O(log(n+m)) time). In the case of ordered
sets we can do better by inserting elements from the smaller set into the larger, leading a time of O(m log(n + m).
This is also what we do in our experiments. For vectors we stick with the available set union implementation.
Figure 11 (d) gives a comparison of times for U NION. For equal lengths our implementation is about a factor of 3
faster than set variant (red-black trees), and about 8 times slower than the vector variant. This is not surprising since
we are asymptotically faster than their red-black tree implementation, and their array-based implementation just reads
and writes the values, one by one, from flat arrays, and therefore has much less overhead and much fewer cache misses.
For taking the union of smaller and larger inputs, our U NION is orders of magnitude faster than either STL version.
This is because their theoretical work bound (O(m + n) and O(m log(m + n)) is worse than our O(m log(n/m + 1)),
which is optimal in comparison model.
Comparing to parallel implementations on various input distributions We compare our implementations to other
parallel search trees, such as the WBB-trees, as described in [12], and parallel RB trees from the MCSTL [13]. We
test the performance on different input distributions.

16

In Figure 11 (e) we show the result of U NION on uniformly distributed doubles in the range of [0,1] across 64
cores. We set the input size to n = m = 10i , i from 4 to 8. The three implementations have similar performance
when n = m = 104 . As the input size increases, MCSTL shows much worse performance than the other two because
of the lack of parallelism (Figure 11 (h) is a good indication), and the WBB-tree implementation is slightly better
than ours. For the same reason that STL vectors outperform STL sets (implemented with RB trees) and our sequential
implementation, the WBB-trees take the bulk as a sorted array, which has much less overhead to access and much
better cache locality. Also their tree layout is more cache efficient and the overall height is lower since they store
multiple keys per node.
Figure 11 (f) shows the result of a Gaussian distribution with doubles, also on all 64 cores with set sizes of
n = m = 10i for i = 4 through 8. The distributions of the two sets have means at 0 and 1 respectively, and both
having a standard deviation of 0.25, meaning that the data in the two sets have less overlap comparing to a uniform
distribution (as in (e)). In this case our code achieves better performance than the other two implementations. For our
algorithms less overlap in the data means more parts of the trees will be untouched, and therefore less nodes will be
operated on. This in turn leads to less processing time.
We also do an in-depth study on how the overlap of the data sets affects the performance of each algorithm. We
generate two sets of size n = m = 108 , each from a Gaussian distribution. The distributions of the two sets have
means at 0 and 1 respectively, and both have an equal standard deviation varying in {1, 1/2, 1/4, 1/8, 1/16}. The
different standard deviations are to control the overlap of the two sets, and ideally less overlap should simplify the
problem. Figure 11 (g) shows the result of the three parallel implementations on a Gaussian distribution with different
standard deviations. From the figure we can see that MCSTL and WBB-tree are not affected by different standard
deviations, while our join-based union takes advantage of less overlapping and achieves a much better performance
when σ is small. This is not surprising since when the two sets are less overlapped, e.g., totally disjoint, our U NION
will degenerate to a simple J OIN, which costs only O(log n) work. This behavior is consistent with the “adaptive”
property (not always the worst-case) in [?]. This indicates that our algorithm is the only one among the three parallel
implementations that can detect and take advantage of less overlapping in data, hence have a much better performance
when the two operated sets are less overlapped.
We also compare the parallelism of these implementations. In Figure 11 (h) we show their performance across 64
cores. The inputs are both of size 108 , and generated from an uniform distribution of doubles. It is easy to see that
MCSTL does not achieve good parallelism beyond 16 cores, which explains why the MCSTL always performs the
worst on 64 cores in all settings. As we mentioned earlier, the WBB-tree are slightly faster than our code, but when
it comes to all 64 cores, both algorithms have similar performance. This indicates that our algorithm achieves better
parallelism.
To conclude, in terms of parallel performance, our code and WBB-trees are always much better than the MCSTL
because of MCSTL’s lack of parallelism. WBB-trees achieve a slightly better performance than ours on uniformly
distributed data, but it does not improve when the two sets are less overlapped. Thus our code is much better than
the other two implementations on less overlapped data, while still achieving a similar performance with the other
algorithms when the two sets are more intermixed with each other.

17

7

Conclusions

In this paper, we study ordered sets implemented with balanced binary search trees. We show for the first time that a
very simple “classroom-ready” set of algorithms due to Adams’ are indeed work optimal when used with four different
balancing schemes–AVL, RB, WB trees and treaps—and also highly parallel. The only tree-specific algorithm that
is necessary is the J OIN, and even the J OINs are quite simple, as simple as I NSERT or D ELETE. It seems it is not
sufficient to give a time bound to J OIN and base analysis on it. Indeed if this were the case it would have been done
years ago. Instead our approach defines the notion of a rank (differently for different trees) and shows invariants on
the rank. It is important that the cost of J OIN is proportional to the difference in ranks. It is also important that when
joining two trees the resulting rank is only a constant bigger than the larger rank of the inputs. This insures that when
joins are used in a recursive tree, as in U NION, the ranks of the results in a pair of recursive calls does not differ much
on the two sides. This then ensures that the set functions are efficient.
We also test the performance of our algorithm. Our experiments show that our sequential algorithm is about 3x
faster for union on two maps of size 108 compared to the STL red-black tree implementation. In parallel settings our
code is much better than the two baseline algorithms (MCSTL and WBB-tree) on less overlapped data, while still
achieves similar performances with WBB-tree when the two sets are more intermixed. Our code also achieves 45x
speedup on 64 cores.

References
[1] S. Adams. Implementing sets effciently in a functional language. Technical Report CSTR 92-10, University of
Southampton, 1992.
[2] S. Adams. Efficient sets—a balancing act. Journal of functional programming, 3(04):553–561, 1993.
[3] G. Adelson-Velsky and E. M. Landis. An algorithm for the organization of information. Proc. of the USSR
Academy of Sciences, 145:263–266, 1962. In Russian, English translation by Myron J. Ricci in Soviet Doklady,
3:1259-1263, 1962.
[4] Y. Akhremtsev and P. Sanders. Fast parallel operations on search trees(unpublished), 2016.
[5] R. Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Informatica, 1:290–306,
1972.
[6] G. E. Blelloch and M. Reid-Miller. Fast set operations using treaps. In Proc. ACM Symposium on Parallel
Algorithms and Architectures (SPAA), pages 16–26, 1998.
[7] N. Blum and K. Mehlhorn. On the average number of rebalancing operations in weight-balanced trees. Theoretical Computer Science, 11(3):303–320, 1980.
[8] R. D. Blumofe and C. E. Leiserson. Space-efficient scheduling of multithreaded computations. SIAM J. on
Computing, 27(1):202–229, 1998.
[9] R. P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201–206, Apr.
1974.
[10] N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In Proc. ACM
SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPoPP), pages 257–268, 2010.
[11] M. R. Brown and R. E. Tarjan. A fast merging algorithm. Journal of the ACM (JACM), 26(2):211–226, 1979.
[12] S. Erb, M. Kobitzsch, and P. Sanders. Parallel bi-objective shortest paths using weight-balanced b-trees with bulk
updates. In Experimental Algorithms, pages 111–122. Springer, 2014.
[13] L. Frias and J. Singler. Parallelization of bulk operations for STL dictionaries. In Euro-Par 2007 Workshops:
Parallel Processing, HPPC 2007, UNICORE Summit 2007, and VHPC 2007, pages 49–58, 2007.
18

[14] Y. Hirai and K. Yamamoto. Balancing weight-balanced trees. Journal of Functional Programming, 21(03):287–
307, 2011.
[15] F. K. Hwang and S. Lin. A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. on Computing, 1(1):31–39, 1972.
[16] J. Katajainen. Efficient parallel algorithms for manipulating sorted sets. In Proceedings of the 17th Annual
Computer Science Conference. University of Canterbury, 1994.
[17] H. T. Kung and P. L. Lehman. Concurrent manipulation of binary search trees. ACM Trans. Database Syst.,
5(3):354–382, 1980.
[18] K. S. Larsen. AVL trees with relaxed balance. J. Comput. Syst. Sci., 61(3):508–522, 2000.
[19] S. Marlow et al. Haskell 2010 language report. Available online http://www. haskell. org/(May 2011), 2010.
[20] D. R. Musser, G. J. Derge, and A. Saini. STL tutorial and reference guide: C++ programming with the standard
template library. Addison-Wesley Professional, 2009.
[21] A. Natarajan and N. Mittal. Fast concurrent lock-free binary search trees. In Proc. ACM SIGPLAN Symp. on
Principles and Practice of Parallel Programming (PPoPP), pages 317–328, 2014.
[22] J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM J. Comput., 2(1):33–43, 1973.
[23] H. Park and K. Park. Parallel algorithms for red–black trees. Theoretical Computer Science, 262(1):415–435,
2001.
[24] W. J. Paul, U. Vishkin, and H. Wagener. Parallel dictionaries in 2-3 trees. In Proc. Intl. Colloq. on Automata,
Languages and Programming (ICALP), pages 597–609, 1983.
[25] R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica, 16:464–497, 1996.
[26] D. D. Sleator and R. E. Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686,
1985.
[27] M. Straka. Adams’ trees revisited. In Trends in Functional Programming, pages 130–145. Springer, 2012.
[28] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1983.

A
A.1

Proofs for Some Lemmas
Proof for Lemma 8

Proof. One observation in WB trees and treaps is that all nodes attached to a single layer root form a chain. This is
true because if two children of one node v are both in layer i, the weight of v is more than 2i+1 , meaning that v should
be layer i + 1.
For a layer root v in a WB tree on layer k, w(v) is at most 2k+1 . Considering the balance invariant that its child
has weight at most (1 − α)w(v), the weight of the t-th generation of its descendants is no more than 2k+1 (1 − α)t .
1
1
2 generations, the weight should decrease to less than 2k . Thus d(v) ≤ log 1−α
2,
This means that after t∗ = log 1−α
which is a constant.
For treaps consider a layer root v on layer k that has weight N ∈ [2k , 2k+1 ). The probability that d(v) ≥ 2 is
equal to the probability that one of its grandchildren has weight at least 2k . This probability P is:

19

(1). Single Rotation
……
u
1

v
3

(0)

The left
branch in ܶோ

4

‫ܤ‬

C

……

‫ܣ‬

v

u

1

5

2

5

3

‫ܦ‬

(2). Double Rotation

‫ܣ‬

2

4

‫ܤ‬

C

……

3

‫ܦ‬

u

(0): The rebalance process is currently at ‫ݒ‬,
which means the tree rooted at ‫ ݑ‬and all of
its subtrees are balanced.
(1): The result of the single rotation.
(2): The result of the double rotation.

v

1

2

4

5

‫ܣ‬

‫ܤ‬

‫ܥ‬

‫ܦ‬

Figure 12: An illustration of two kinds of outcomes of rotation after joining two weight balanced trees. After we
append the smaller tree to the larger one and rebalance from that point upwards, we reach the case in (0), where u has
been balanced, and the smaller tree has been part of it. Now we are balancing v, and two options are shown in (1) and
(2). At least one of the two rotation will rebalance v.

P =

≤

1
2k
1
2k

N
X
i − 2k
i
k

(7)

i=2 +1
k+1
2X

i=2k +1

≈ 1 − ln 2

i − 2k
i

(8)
(9)

We denote 1 − ln 2 as pc . Similarly, the probability that d(v) ≥ 4 should be less than p2c , and the probability shrink
geometrically as d(v) increase. Thus the expected value of d(v) is a constant.
Since treaps come from a random permutation, all s(v) are i.i.d.

A.2

Proof for Lemma 5

Proof. We are trying to show that for Tr =U NION(Tp , Td ) on AVL, RB or WB trees, if r(Tp ) > r(Td ) then r(Tr ) ≤
r(Tp ) + r(Td ).
For AVL and RB trees we use induction on r(Tp ) + r(Td ). When r(Td ) + r(Tp ) = 1 the conclusion is trivial. If
r = r(Tp ) > r(Td ), Tp will be split into two subtrees, with rank at most r(Tp )−1 since we remove the root. Td will be
split into two trees with height at most r(Td ) (Theorem 2). Using the inductive hypothesis, the two recursive calls will
return two trees of height at most r(Tp ) − 1 + r(Td ). The result of the final J OIN is therefore at most r(Tp ) + r(Td ).
For WB trees, |T | ≤ |Tp | + |Td | ≤ 2|Tp |. Thus r(T ) ≤ r(Tp ) + 1 ≤ r(Tp ) + r(Td ).

20

A.3

Proof for Lemma 3

Proof. Recall that in a weight balanced tree, for a certain node,
√neither of its children is β times larger than the other
one, where β = α1 − 1. When α ≤ 1 − √12 , we have β ≥ 1 + 2.
WLOG, we prove the case when |TL | < |TR |, where TL is inserted along the left branch of TR . Then we rebalance
the tree from the point of key k and go upwards. As shown in Figure 12 (0), suppose the rebalance has been processed
to u (then we can use reduction). Thus the subtree rooted at u is balanced, and TL is part of it. We name the four trees
from left to right A, B, C and D, and the number of nodes in them a, b, c and d. From the balance condition we know
that A is balanced with B + C, and B is balanced to C, i.e.:
1
(b + c) ≤a ≤ β(b + c)
β
1
b ≤c ≤ βc
β

(10)
(11)

We claim that at least one of the two operations will rebalanced the tree rooted at v in Figure 12 (0):
Op. (1). Single rotation: right rotation at u and v (as shown in Figure 12 (1));
Op. (2). double rotation: Left rotation followed by a right rotation (as shown in Figure 12 (2)).
Also, notice that the inbalance is caused by the insertion of a subtree at the leftmost branch. Suppose the size
of the smaller tree is x, and the size of the original left child of v is y. Note that in the process of J OIN, TL is not
concatenated with v. Instead, it goes down to deeper nodes. Also, note that the original subtree of size y is weight
balanced with D. This means we have:

x<

1
(d + y)
β

1
d ≤ y ≤ βd
β
x+y =a+b+c
From the above three inequalities we get x <

1
βd

+ d, thus:

a + b + c = x + y < (1 + β +

1
)d
β

(12)

Since a unbalance occurs, we have:
a + b + c > βd

(13)

1
(b + c) ≤ d ≤ β(b + c)
β

(14)

We discuss the following 3 cases:
Case 1. B + C is weight balanced with D, i.e.,

In this case, we apply a right rotate. The new tree rooted at u is now balanced. A is naturally balanced.
Then we discuss in two cases:
Case 1.1. βa ≥ b + c + d.
Notice that b+c ≥ β1 a, meaning that b+c+d > β1 a. Then in this case, A is balanced to B +C +D,
B + C is balanced to D. Thus just one right rotation will rebalance the tree rooted at u (Figure 12
(1)).
21

Case 1.2. βa < b + c + d.
In this case, we claim that a double rotation as shown in Figure 12 (2) will rebalance the tree. Now
we need to prove the balance of all the subtree pairs: A with B, C with D, and A + B with C + D.
First notice that when βa < b + c + d, from (13) we can get:
βd < a + b + c <

1
(b + c + d) + b + c
β

1
1
)d < ( + 1)(b + c)
β
β
⇒(β − 1)d < b + c

⇒(β −

(15)

Considering (14), we have (β − 1)d < b + c ≤ βd. Notice b and c satisfy (11), we have:
1
(b + c) >
β+1
1
c>
(b + c) >
β+1
b>

Also note that when β > 1 +

√

β−1
d
β+1
β−1
d
β+1

(16)
(17)

2 ≈ 2.414, we have
β+1
<β
β−1

We discuss the following three conditions of subtrees’ balance:
I. Prove A is weight balanced to B.
i. Prove b ≤ βa.
Since βa ≤ b + c (applying (10)) , we have b ≤ βa.
ii. Prove a ≤ βb.
In the case when βa < b + c + d we have:
1
(b + c + d) (applying(11), (16))
β
1
β+1
< (b + βb +
b)
β
β−1
β+1
=
b
β−1
< βb

a<

II. Prove C is weight balanced to D.
i. Prove c ≤ βd.
Since b + c ≤ βd (applying (14)), we have c ≤ βd.
ii. Prove d ≤ βc.
From (17), we have
d<

β+1
c < βc
β−1

III. Prove A + B is weight balanced to C + D.
i. Prove a + b ≤ β(c + d).

22

(18)

From (15), (11) and (18) we have:
1
1
(b + c) ≤
(βc + c)
β−1
β−1
β+1
=
c < βc
β−1
1
⇒ d<c
β
1
⇒(1 + )d < (1 + β)c
β
1
⇒(1 + + β)d < β(c + d) + c (applying (12))
β
1
⇒a + b + c < (1 + + β)d < β(c + d) + c
β
⇒a + b < β(c + d)
d<

ii. Prove c + d ≤ β(a + b).
β
< β. Thus applying (15) and (10) we have:
When β > 2, we have β−1
d<

1
β
(b + c) ≤
a < βa
β−1
β−1

Also we have c ≤ βb (applying (11)). Thus c + d < β(a + b).
Case 2. B + C is too light that cannot be balanced with D, i.e.,
β(b + c) < d

(19)

In this case, we have a < β(b + c) < d (applying (10) and (19)), which means that a + b + c < d + β1 d < βd
√

when β > 1+2 5 ≈ 1.618. This contradicts with the condition that A + B + C is too heavy to D (a + b + c >
βd). Thus this case is impossible.
Case 3. B + C is too heavy that cannot be balanced with D, i.e.,
b + c > βd
1
⇒a > (b + c) > d
β

(20)
(21)

In this case, we apply the double rotation.
We need to prove the following balance conditions:
I. Prove A is weight balanced to B.
i. Prove b < βa.
Since βa > b + c (applying (10)) , we have b < βa.
ii. Prove a < βb.
Suppose c = kb, where β1 < k < β. Since b + c > βd, we have:
d<

23

1+k
b
β

(22)

From the above inequalities, we have:
a + b + c = a + b + kb
(applying(12))
1
< (1 + β + )d (applying(22))
β
1
1+k
< (1 + β + ) ×
b
β
β
!
1 + β + β1
− 1 (1 + k)b
⇒a<
β
β+1
(1 + k)b
β2
(β + 1)2
<
b
β2

=

When β >

7
9 ×(

√

837+47 −1/3
)
+(
54

√
837+47 1/3
) + 13
54

II. Prove C is weight balanced to D.
i. Prove d ≤ βc. √
When β > 1+2 5 ≈ 1.618, we have β > 1 +
b < βc < d. Thus:
b + c < (1 +

≈ 2.1479, we have

1
β.

(β+1)2
β

< β. Hence a < βb.

Assume to the contrary c <

1
β d,

1
)d < βd
β

, which contradicts with (20) that B + C is too heavy to be balanced with D.
ii. Prove c < βd.
Plug (21) in (12) and get b + c < (β + β1 )d. Recall that β > 1, we have:
1
1
c + c < b + c < (β + )d
β
β
β2 + 1
⇒c <
d < βd
β+1
III. Prove A + B is weight balanced with C + D.
i. Prove c + d ≤ β(a + b).
From (11) we have c < βb, also d < a < βa (applying (21)), thus c + d < β(a + b).
ii. Prove a + b ≤ β(c√+ d).
Recall when β > 1+2 5 ≈ 1.618, we have β > 1 + β1 . Applying (20) and (11) we have:
d≤

1
1
(b + c) ≤ c + c < βc
β
β

1
⇒ d<c
β
1
⇒(1 + )d < (1 + β)c
β
1
⇒(1 + + β)d < β(c + d) + c (applying (12))
β
1
⇒a + b + c < (1 + + β)d < β(c + d) + c
β
⇒a + b < β(c + d)
24

we have

Taking all the three conclusions into consideration, after either a single rotation or a double rotation, the new subtree
will be rebalanced.
Then by induction we can prove Lemma 3.

25

