Weight-balanced tree

<h2 id="description">Description</h2>
A weight-balanced tree is a binary search tree that stores the sizes of subtrees in the nodes. That is, a node has fields

<ul><li>key, of any ordered type</li>
<li>value (optional, only for mappings)</li>
<li>left, right, pointer to node</li>
<li>size, of type integer.</li></ul>
By definition, the size of a leaf (typically represented by a nil pointer) is zero. The size of an internal node is the sum of sizes of its two children, plus one: (size[n] = size[n.left] + size[n.right] + 1). Based on the size, one defines the weight to be weight[n] = size[n] + 1.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> Weight has the advantage that the weight of a node is simply the sum of the weights of its left and right children.

Operations that modify the tree must make sure that the weight of the left and right subtrees of every node remain within some factor α of each other, using the same <a href="/facts/AVL_tree/DfexIbS6">rebalancing operations</a> used in <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a>: rotations and double rotations. Formally, node balance is defined as follows:

A node is α-weight-balanced if weight[n.left] ≥ α·weight[n] and weight[n.right] ≥ α·weight[n].<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
Here, α is a numerical parameter to be determined when implementing weight balanced trees. Larger values of α produce "more balanced" trees, but not all values of α are appropriate; Nievergelt and Reingold proved that

α
 <
 1
 −
 
 
 
 2
 
 2
 
 
 ≈
 0.29289
 
 
 {\displaystyle \alpha <1-{\frac {\sqrt {2}}{2}}\approx 0.29289}

is a necessary condition for the balancing algorithm to work. Later work showed a lower bound of 2⁄11 for α, although it can be made arbitrarily small if a custom (and more complicated) rebalancing algorithm is used.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Applying balancing correctly guarantees a tree of n elements will have height<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>

h
        ≤
        
          log
          
            
              1
              
                1
                −
                α
              
            
          
        
        ⁡
        n
        =
        
          
            
              
                log
                
                  2
                
              
              ⁡
              n
            
            
              
                log
                
                  2
                
              
              ⁡
              
                (
                
                  
                    1
                    
                      1
                      −
                      α
                    
                  
                
                )
              
            
          
        
        =
        O
        (
        log
        ⁡
        n
        )
      
    
    {\displaystyle h\leq \log _{\frac {1}{1-\alpha }}n={\frac {\log _{2}n}{\log _{2}\left({\frac {1}{1-\alpha }}\right)}}=O(\log n)}

If α is given its maximum allowed value, the worst-case height of a weight-balanced tree is the same as that of a red–black tree at 
 
 
 
 2
 
 log
 
 2
 
 
 ⁡
 n
 
 
 {\displaystyle 2\log _{2}n}
 
.
The number of balancing operations required in a sequence of n insertions and deletions is linear in n, i.e., balancing takes a constant amount of overhead in an <a href="/facts/Amortized_analysis/9fFYenJz">amortized</a> sense.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
While maintaining a tree with the minimum search cost requires four kinds of double rotations (LL, LR, RL, RR as in an AVL tree) in insert/delete operations, if we desire only logarithmic performance, LR and RL are the only rotations required in a single top-down pass.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<h2 id="set-operations-and-bulk-operations">Set operations and bulk operations</h2>
Several set operations have been defined on weight-balanced trees: <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a>, <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> and <a href="/facts/Set_difference/yWUePIYY">set difference</a>. Then fast bulk operations on insertions or deletions can be implemented based on these set functions. These set operations rely on two helper operations, Split and Join. With the new operations, the implementation of weight-balanced trees can be more efficient and highly-parallelizable.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a><a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

Join
The function Join is on two weight-balanced trees t1 and t2 and a key k and will return a tree containing all elements in t1, t2 as well as k. It requires k to be greater than all keys in t1 and smaller than all keys in t2. If the two trees have the balanced weight, Join simply create a new node with left subtree t1, root k and right subtree t2. Suppose that t1 has heavier weight than t2 (the other case is symmetric). Join follows the right spine of t1 until a node c which is balanced with t2. At this point a new node with left child c, root k and right child t2 is created to replace c. The new node may invalidate the weight-balanced invariant. This can be fixed with a single or a double rotation assuming 
 
 
 
 α
 <
 1
 −
 
 
 1
 
 2
 
 
 
 
 
 {\displaystyle \alpha <1-{\frac {1}{\sqrt {2}}}}

Split
To split a weight-balanced tree into two smaller trees, those smaller than key x, and those larger than key x, first draw a path from the root by inserting x into the tree. After this insertion, all values less than x will be found on the left of the path, and all values greater than x will be found on the right. By applying Join, all the subtrees on the left side are merged bottom-up using keys on the path as intermediate nodes from bottom to top to form the left tree, and the right part is symmetric. For some applications, Split also returns a Boolean value denoting if x appears in the tree. The cost of Split is 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
, order of the height of the tree. This algorithm actually has nothing to do with any special properties of a weight-balanced tree, and thus is generic to other balancing schemes such as <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a>.
The join algorithm is as follows:

function joinRightWB(TL, k, TR)
 (l, k', c) = expose(TL)
 if balance(|TL|, |TR|) return Node(TL, k, TR)
 else 
 T' = joinRightWB(c, k, TR)
 (l', k', r') = expose(T')
 if (balance(|l|,|T'|)) return Node(l, k', T')
 else if (balance(|l|,|l'|) and balance(|l|+|l'|,|r'|))
 return rotateLeft(Node(l, k', T'))
 else return rotateLeft(Node(l, k', rotateRight(T'))
function joinLeftWB(TL, k, TR)
 /* symmetric to joinRightWB */
function join(TL, k, TR)
 if (heavy(TL, TR)) return joinRightWB(TL, k, TR)
 if (heavy(TR, TL)) return joinLeftWB(TL, k, TR)
 Node(TL, k, TR)

Here balance
 
 
 
 (
 x
 ,
 y
 )
 
 
 {\displaystyle (x,y)}
 
 means two weights T and T are balanced. expose(v)=(l, k, r) means to extract a tree node T's left child T, the key of the node T and the right child T. Node(l, k, r) means to create a node of left child T, key T and right child T.
The split algorithm is as follows:

function split(T, k)
 if (T = nil) return (nil, false, nil)
 (L, (m, c), R) = expose(T)
 if (k = m) return (L, true, R)
 if (k < m) 
 (L', b, R') = split(L, k)
 return (L', b, join(R', m, R))
 if (k > m) 
 (L', b, R') = split(R, k)
 return (join(L, m, L'), b, R))

The union of two weight-balanced trees t1 and t2 representing sets A and B, is a weight-balanced tree t that represents A ∪ B. The following recursive function computes this union:

function union(t1, t2):
 if t1 = nil:
 return t2
 if t2 = nil:
 return t1
 t<, t> ← split t2 on t1.root
 return join(union(left(t1), t<), t1.root, union(right(t1), t>))

Here, Split is presumed to return two trees: one holding the keys less than its input key, the other holding the greater keys. (The algorithm is <a href="/facts/Persistent_data_structure/K7IpHlkR">non-destructive</a>, but an in-place destructive version exists as well.)
The algorithm for intersection or difference is similar, but requires the Join2 helper routine that is the same as Join but without the middle key. Based on the new functions for union, intersection or difference, either one key or multiple keys can be inserted to or deleted from the weight-balanced tree. Since Split and Union call Join but do not deal with the balancing criteria of weight-balanced trees directly, such an implementation is usually called the <a href="/facts/Join-based_tree_algorithms/ceN2nU0C">join-based algorithms</a>.
The complexity of each of union, intersection and difference is 
 
 
 
 O
 
 (
 
 m
 log
 ⁡
 
 (
 
 
 
 n
 m
 
 
 +
 1
 
 )
 
 
 )
 
 
 
 {\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}
 
 for two weight-balanced trees of sizes T and 
 
 
 
 n
 (
 ≥
 m
 )
 
 
 {\displaystyle n(\geq m)}
 
. This complexity is optimal in terms of the number of comparisons. More importantly, since the recursive calls to union, intersection or difference are independent of each other, they can be executed <a href="/facts/Parallel_programming/nQzcpzQt">in parallel</a> with a <a href="/facts/Analysis_of_parallel_algorithms/GC8l28HW">parallel depth</a> 
 
 
 
 O
 (
 log
 ⁡
 m
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log m\log n)}
 
.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> When 
 
 
 
 m
 =
 1
 
 
 {\displaystyle m=1}
 
, the join-based implementation has the same computational <a href="/facts/Directed_acyclic_graph/k6zq1os9">directed acyclic graph</a> (DAG) as single-element insertion and deletion if the root of the larger tree is used to split the smaller tree.

<h2 id="notes">Notes</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Tsakalidis, A. K. (1984). "Maintaining order in a generalized linked list". Acta Informatica. 21: 101–112. doi:10.1007/BF00289142. S2CID 26127563. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Nievergelt, J.; Reingold, E. M. (1973). "Binary Search Trees of Bounded Balance". SIAM Journal on Computing. 2: 33–43. doi:10.1137/0202005. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">This article incorporates public domain material from Paul E. Black. "BB(α) tree". Dictionary of Algorithms and Data Structures. NIST. <a href="/wiki/Copyright_status_of_works_by_the_federal_government_of_the_United_States" target="_blank">/wiki/Copyright_status_of_works_by_the_federal_government_of_the_United_States</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees" (PDF). Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104. <a href="https://yoichihirai.com/bst.pdf" target="_blank">https://yoichihirai.com/bst.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Roura, Salvador (2001). A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7. <a href="978-3-540-42287-7" target="_blank">978-3-540-42287-7</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Adams, Stephen (1993). "Functional Pearls: Efficient sets—a balancing act". Journal of Functional Programming. 3 (4): 553–561. doi:10.1017/S0956796800000885. <a href="https://doi.org/10.1017%2FS0956796800000885" target="_blank">https://doi.org/10.1017%2FS0956796800000885</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Hirai, Y.; Yamamoto, K. (2011). "Balancing weight-balanced trees" (PDF). Journal of Functional Programming. 21 (3): 287. doi:10.1017/S0956796811000104. <a href="https://yoichihirai.com/bst.pdf" target="_blank">https://yoichihirai.com/bst.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">This is the definition used by Nievergelt and Reingold. Adams uses the size as the weight directly,[6] which complicates analysis of his variant and has led to bugs in major implementations.[4] <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. pp. 61–71. <a href="https://archive.org/details/advanceddatastru00bras" target="_blank">https://archive.org/details/advanceddatastru00bras</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. pp. 61–71. <a href="https://archive.org/details/advanceddatastru00bras" target="_blank">https://archive.org/details/advanceddatastru00bras</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. pp. 61–71. <a href="https://archive.org/details/advanceddatastru00bras" target="_blank">https://archive.org/details/advanceddatastru00bras</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Blum, Norbert; Mehlhorn, Kurt (1980). "On the average number of rebalancing operations in weight-balanced trees" (PDF). Theoretical Computer Science. 11 (3): 303–320. doi:10.1016/0304-3975(80)90018-3. <a href="http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf" target="_blank">http://scidok.sulb.uni-saarland.de/volltexte/2011/4019/pdf/fb14_1978_06.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Cho, Seonghun; Sahni, Sartaj (2000). "A New Weight Balanced Binary Search Tree". International Journal of Foundations of Computer Science. 11 (3): 485–513. CiteSeerX 10.1.1.36.3888. doi:10.1142/S0129054100000296. <a href="https://www.researchgate.net/publication/2241064" target="_blank">https://www.researchgate.net/publication/2241064</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793. <a href="978-1-4503-4210-0" target="_blank">978-1-4503-4210-0</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Adams, Stephen (1992), Implementing sets efficiently in a functional language, CiteSeerX 10.1.1.501.8427. <a href="https://groups.csail.mit.edu/mac/users/adams/BB/92-10.ps.gz" target="_blank">https://groups.csail.mit.edu/mac/users/adams/BB/92-10.ps.gz</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016), "Just Join for Parallel Ordered Sets", Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016), ACM, pp. 253–264, arXiv:1602.02120, doi:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0, S2CID 2897793. <a href="978-1-4503-4210-0" target="_blank">978-1-4503-4210-0</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
</ol>

Weight-balanced tree open-in-new

Weight-balanced tree