Fused Trees: Simple BST balancing method by partial & scheduled rebuilds

Tae Woo Kim
Department of Computer Science
Yonsei University, Korea
travis1829@yonsei.ac.kr

Abstract
This paper proposes a simple method to balance a binary search tree, as an attempt to develop the simplest and
most explicit procedure. For a given constant 𝑘 in (0, 0.5), a rebuilt subtree of size 𝑛 rebuilds itself again after
max(1, ⌊𝑘𝑛⌋) insert/delete operations.
With a cost, this scheduled rebuild offers implementational advantages. This cost is frequent rebuilds and a single
integer value to be stored at all nodes. The return is short-coded and explicit extra procedures the only thing needed
to ensure logarithmic search costs and amortized logarithmic insert/delete costs.

1. Introduction
Seeking for a “just-working” solution means preferring the “simplest” solution. Performance deterioration,
neglecting the latest technology and all kinds of things unacceptable in theory can happen in practice, just for
simplicity. An example is the software engineering, or its education. In those fields, the philosophy is often to
produce “just-working” programs, to cite Arne Anderson [1]. As we can see, often, simplicity is the virtue.
This philosophy about “just-working” solutions is also applied to the balanced search tree. The key feature of a
balanced search tree would be the logarithmic costs, sometimes in a probabilistic or amortized sense, for search,
insert, and delete operations. Many examples of a balanced search tree exist, such as the AVL tree [2], or the binary
B-tree [3]. However, in Munro, Papadakis, and Sedgewick [4], they were rarely used in the actual (non-research)
computational practices. Evidently, their cumbersome implementation made their logarithmic efficiencies to be
meaningless, which just emphasizes the importance of a simple balanced search tree. The AA tree [1] is an
example of such simplified tree, which sacrifices some performance for simplicity but still provides logarithmic
costs. This sacrifice can be said to be reasonable since the only thing needed for a “just-working” balanced search
tree is the logarithmic costs.
The balanced search tree must be considered for the “average” programmer. It is a fundamental (and cumbersome)
data structure needed in numerous applications, but nobody welcomes a tiresome progress to be done every time.
Also, note that the notion of a programmer has been becoming broader in modern society. Anyone can become a
software engineer in the field, but not all of them are a computer science graduate or a highly experienced person
[5]. Data structures that require strong comprehension or long-coded procedures, which just fits the most balanced
search trees, get easily neglected in the field. This is because of its heavily time-consuming
implementation/maintenance, or because it is simply too-hard to try for some people.
Thus, we introduce a new method to balance binary search trees. It was done to develop the simplest and most
explicit kind by using the following observations.

-

The process of “detecting unbalance and then rebalancing” can be replaced by “scheduled rebalance”. To be
specific, a rebalance can be deterministically scheduled to occur at the very first moment where such
unbalance can happen. This makes no complicated tree rules, which are used in many balanced search trees
to detect an imbalance, needed to maintain a balance.

-

A single integer value, which will be stored at all nodes, is enough to simply and explicitly implement the
scheduled rebalances.

-

The rebuild procedures can be implemented more explicitly than tree rotation procedures. Tree rotations can
sometimes be done through short-coded procedures [1], but requires a consideration of various conditions.
These can include all possible cases of the tree, complicated tree attributes and restrictions, etc. On the other
hand, rebuild procedures can require less prerequisite considerations, and can be simply operated (See
Section 4.4 for details).

Following is our fused tree’s balancing method, explainable in just one sentence. For a given constant 𝑘 in (0,
0.5), a rebuilt subtree of size 𝑛 rebuilds itself again after max(1, ⌊𝑘𝑛⌋) insert/delete operations. In details, 𝑘 is
α
a given constant that has a similar role with the α in the scapegoat tree, except that 𝑘 is equivalent to 1 −
2

(See Section 3 for details). It shall be decided before the initialization of the tree. Also, the scheduled rebuilds will
be implemented by a single integer value, the “fuse”. The “fuse” refers to the remaining insert/delete operations
until rebuild, and is stored at all nodes. It is set to ⌊𝑘𝑛⌋ at rebuilds (or 0 at a node’s creation), reduced by 1 after
every insert/delete operation. When it is reduced to be no more than 0, it explicitly means that a rebuild is required
at this node. The integer value is named “fuse” since it acts like an explosive’s fuse, which is the string attached
to an explosive and represents the remaining time until an explosion.
This whole simple and explicit method can be easily implemented by adding small extra codes to a naïve binary
search tree (See Section 4 for details). In details, a rebuild procedure and some extra code for the insert/delete
operation is the only thing needed.
In addition, the fused tree is based on the scapegoat tree [6]. The scapegoat tree is already said to be simple [6,
7], but the fused tree made differences from it for even more simplicity. This leads to different performances and
implementations, explained in Section 6.

2. Notations and Notes
The following notations are for node attributes that are actually implemented. Note that they will be used mainly
during the discussions over the operations (Section 4).
For node 𝑁,


𝑁. 𝑘𝑒𝑦 is the key stored at 𝑁



𝑁. 𝑙𝑒𝑓𝑡 is the left child node of 𝑁



𝑁. 𝑟𝑖𝑔ℎ𝑡 is the right child node of 𝑁



𝑁. 𝑓𝑢𝑠𝑒 is the “fuse” value stored at 𝑁

The following notations are for subtree attributes, which are not actually implemented. They will be used mainly
during the discussions over the correctness of the tree (Section 5).
For subtree 𝑇,


𝑇. 𝑟𝑜𝑜𝑡 is the root of 𝑇



𝑇. 𝑙𝑒𝑓𝑡 is the subtree rooted by 𝑇. 𝑟𝑜𝑜𝑡. 𝑙𝑒𝑓𝑡. It refers to the left wing(subtree) of 𝑇



𝑇. 𝑟𝑖𝑔ℎ𝑡 is the subtree rooted by 𝑇. 𝑟𝑜𝑜𝑡. 𝑟𝑖𝑔ℎ𝑡. It refers to the right wing(subtree) of 𝑇



𝑇. 𝑓𝑢𝑠𝑒 is 𝑇. 𝑟𝑜𝑜𝑡. 𝑓𝑢𝑠𝑒



𝑇. 𝑠𝑖𝑧𝑒 is the size of 𝑇



𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑 is the size of 𝑇 after its last rebuild.

Note that in this paper, the term “subtree” is used only for trees with at least one node.
In addition, lowercase letters (such as 𝑛, 𝑘) were used to denote numerical values, and uppercase letters (such as
𝑁, 𝑇) were used to denote nodes or (sub)trees.

3. Preliminary Discussions (α-weight-balanced)
For an α in [0.5, 1), a node 𝑁 is α-weight-balanced if and only if
𝑇. 𝑙𝑒𝑓𝑡. 𝑠𝑖𝑧𝑒 ≤ α ∙ 𝑇. 𝑠𝑖𝑧𝑒 and,
𝑇. 𝑟𝑖𝑔ℎ𝑡. 𝑠𝑖𝑧𝑒 ≤ α ∙ 𝑇. 𝑠𝑖𝑧𝑒
where 𝑁 = 𝑇. 𝑟𝑜𝑜𝑡.
Also, a binary search tree is α-weight-balanced if and only if all its nodes are α-weight-balanced. Note that a
rebuilt binary search tree is 1/2-weight-balanced.

The height of an α-weight-balanced binary search tree is no more than ⌊log 1 𝑛⌋ [6].
𝛼

Thus, in scapegoat trees, this pre-fixed constant α is used to determine whether a rebuild is needed and to
consequentially maintain the tree with logarithmic height.
Similarly, the fused tree will use a pre-fixed constant 𝑘 , where 0 < 𝑘 <
consequentially maintain a

1
2−2𝑘

1
2

, to schedule a rebuild and to

-weight-balanced tree (See Section 4 for more details about how it maintains

balance, and Section 5 for the proof). Note that

1
2

<

1
2−2𝑘

< 1.

4. Operations
Operations will be explained based on its small differences with the naïve BST operations. The differences will
also be noted under the provided pseudocode.
Note that the only difference with naïve ones is about designating the location of rebuild (in the case of
insert/delete operations) and changing the “fuse” values.
4.1 Search
The search operations are performed in the same as in naïve binary search trees. No other procedures or rebuilding
methods are required.

4.2 Insert
Insert operations require a few more procedures compared to naïve binary search trees.
1. All the ancestor nodes of the successfully-inserted node get their “fuse” value decreased by 1.
2. During the process, if a node where its “fuse” value is no more than 0 is found, then that is the location where
a rebuild is needed. If several locations exist, the one with top height becomes the final location.
(Example 4.2.1) In Figure 4.2.1, the integer “1” (red node) gets successfully-inserted into the fused tree, as in a
naïve BST. Next, in Figure 4.2.2, all the ancestor nodes of the inserted node get their “fuse” value reduced by 1.
Several nodes where their “fuse” value was no more than 0 existed, and the one with top height (orange node)
was chosen as the final location of rebuild.

In an object-oriented style, the insert operation can be implemented through two main procedures. One for the
interface and one for the internal recursive function. Note the use of a dummyLeafNode in the latter procedure,
which literally refers to a meaningless leaf node.

Procedure 4.2.1 Insert(value)
Input : value as the value to be inserted.
1: (Root, rebuildLocation) = _Insert(Root, value)
2: if rebuildLocation is not null then
3:
Rebuild(rebuildLocation)
- In line 1, the procedure also receives a result about the location to be rebuilt.
- Also, in line 2 to 3, the procedure checks whether a rebuild is needed, and does a rebuild if necessary.
Procedure 4.2.2 _Insert(root, value)
Input : root as the root of the tree to insert the value, and value as the value to be inserted.
Output : Two results returned. First result is the updated root. Second result is the updated location of
rebuild.
1: if root is null then
2:
set root as a new node
3:
return (root, dummyLeafNode)
4: else if value < root.key then
5:
(root.left, rebuildLocation) = _Insert(root.left, value)
6: else if value > root.key then
7:
(root.right, rebuildLocation) = _Insert(root.right, value)
8: else then
9:
return (root, null)
10:
11: if rebuildLocation is not null then
12:
reduce root.fuse by 1
13:
if root.fuse ≤ 0 then
14:
set rebuildLocation as root
15: return (root, rebuildLocation)
- All the lines of the ‘return’ statements and where returned results are assigned get changed to also return/assign
the location of rebuild.
- Also, in line 11 to 14, the procedure checks if the insert operation was successful and if so, it reduces the “fuse”
value of the root. Then, in the case where the “fuse” value became no more than 0, it updates the location of
rebuild.

4.3 Delete
Same kinds of extra procedures are also required in the delete operation. Just like in insert operations, all “fuse”
values in the trail get decreased and a rebuild occurs at the required location (See section 4.2 for details). However,
note that only the ancestor nodes of the deleted node get their “fuse” values decreased.

Also, as in the insert operations, the implementation can be done through two main procedures. By an interface,
and an internal recursive function. The dummyLeafNode is also used in the delete procedures, too.

Procedure 4.3.1 Delete(value)
Input : value as the value to be deleted.
1: (Root, rebuildLocation) = _Delete(Root, value)
2: if rebuildLocation is not null then
3:
Rebuild(rebuildLocation)
- In line 1, the procedure also receives a result about the location to be rebuilt.
- Also, in line 2 to 3, the procedure checks whether a rebuild is needed, and does a rebuild if necessary.
Procedure 4.3.2 _Delete(root, value)
Input : root as the root of the tree to delete the value, and value as the value to be deleted.
Output : Two results returned. First result is the updated root. Second result is the updated location of
rebuild.
1: if root is null then
2:
return (null, null)
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

else if value < root.key then
(root.left, rebuildLocation) = _Delete(root.left, value)
else if value > root.key then
(root.right, rebuildLocation) = _Delete(root.right, value)
else then
if both root.left and root.right exist then
set root.key as getMax(root.left).key
(root.left, rebuildLocation) = _Delete(root.left, root.key)
else if root.left exists then
return (root.left, dummyLeafNode)
else if root.right exists then
return (root.right, dummyLeafNode)
else then
return (null, dummyLeafNode)

17:
18:

if rebuildLocation is not null then

19:

reduce root.fuse by 1

20:

if root.fuse ≤ 0 then

21:
22:

set rebuildLocation as root
return (root, rebuildLocation)

Same type of change occurs, compared to the insert operation.
- All the lines of ‘return’ statements and where returned results are assigned get changed to also return/assign the
location of rebuild.
- Also, in line 18 to 21, the procedure checks if the delete operation was successful and if so, it reduces the “fuse”
value of the root. Then, in the case where the “fuse” value became no more than 0, it updates the location of
rebuild.

4.4 Rebuild
Many tree-rebuild procedures exist, such as in [6, 8, 9].
Compared to most of the procedures, only a single process is additionally required in fused trees. That is, the “fuse”
value for all the nodes in the rebuilt tree must be reset. To be specific, for the root of subtree 𝑇, ⌊𝑘 ∙ 𝑇. 𝑠𝑖𝑧𝑒⌋ shall
become its new “fuse” value.
1

Note that for cases where 𝑇. 𝑠𝑖𝑧𝑒 < , the “fuse” value will be reset to 0, though it does not mean it actually
𝑘

requires a rebuild “now”.
(Example 4.4.1) The orange node in Figure 4.4.1 was chosen as the final location of rebuild. Figure 4.4.2 is the
resultant tree, rebuilt and “fuse” values reset.

The paper introducing the scapegoat tree also introduces a way to rebuild a tree [6]. First, it flattens the tree (as if
into a list), and second, recursively constructs a 1/2-weight-balanced tree from the flat tree. In our approach, to
reset all “fuse” values, only the latter part needs to be slightly modified.
Procedure 4.4.1 BuildTree(head, size)
Input : head as the first (most left) node of the flat tree, and size as the size of the flat tree.
Output : Returns the last (most right) node of the constructed 1/2-weight-balanced tree. Its ‘left’ attribute
refers to the root of the constructed tree.
1: if size is 0 then
2:
set head.left as null
3:
set head.fuse as 0
4:
return head
5: set r as BuildTree(head, ⌊(size − 1)/2⌋ )
6: set s as BuildTree(r.right, ⌊(size − 1)/2⌋ )
7: set r.fuse as ⌊k ∙ size⌋
8: set r.right as s.left
9: set s.left as r
10: return s
- In line 3 and 7, the “fuse” attribute gets assigned.

However, this procedure is not always used in actual implementations, possibly because of its complexity. A
frequently-used procedure of using a linear array (or another sequential data structure) exists, which is similar to
the procedure in [8]. The process is simple and explicit. First, it copies all the keys of the subtree into a linear
array in a sorted order, and second, recursively constructs a new 1/2-weight-balanced tree from the array. In our
approach, only the latter part needs a slight change to reset all the “fuse” values.
Procedure 4.4.2 ConvertArrayIntoTree(array, start, finish)1
Input : array as the linear array with all the data of the tree copied in a sorted order, start as the first
index of the array, and finish as the last index of the array
Output : The root of the 1/2-weight-balanced tree is returned.
1: if start > finish then
2:
return null
3: set root.key as array[ ⌊(start + finish)/2⌋ ]
4: set root.fuse as ⌊k ∙ (finish-start+1)⌋
5: set root.left as ConvertArrayIntoTree(array, start, ⌊(start + finish)/2⌋ − 1)
6: set root.right as ConvertArrayIntoTree(array, ⌊(start + finish)/2⌋ + 1, finish)
7: return root
- In line 4, the “fuse” attribute gets assigned.

Note that in the pseudocodes, though the floor function was used to convert fractions into integers, a (automatic)
truncation could be used instead since the values to be floored/truncated will always be positive.

Beyond these, several more applicable rebuild algorithms exist, such as in [8, 9].
Additionally, in actual implementation, rebuild procedures may ignore trees with size less than 3, since already
balanced in all possible forms.

5. Proof of Logarithmic Costs
5.1 α-weight-balanced
It is proven that the fused tree is always α-weight-balanced as follows. This will be done by separating the tree
into two cases mainly based on its size.
First, for small trees (size less than 2/𝒌), they are always rebuilt after an insert/delete operation. This will
be explained through Lemma 5.1.1 and Corollary 5.1.2.

Lemma 5.1.1 For any subtree 𝑇, 𝑇. 𝑓𝑢𝑠𝑒 ≤ ⌊𝑘 ∙ 𝑇. 𝑠𝑖𝑧𝑒⌋
Proof.
For subtree 𝑋 after 𝑖 insert/delete operations, define 𝑓(𝑋, 𝑖) = ⌊𝑘 ∙ 𝑋. 𝑠𝑖𝑧𝑒⌋ − 𝑋. 𝑓𝑢𝑠𝑒
i)
𝑖 = 0 or the 𝑖th operation included a rebuild
𝑓(𝑋, 𝑖) = 0 (∵ 𝑋. 𝑓𝑢𝑠𝑒 = ⌊𝑘 ∙ 𝑋. 𝑠𝑖𝑧𝑒⌋)

ii)
𝑖th operation was a rebuild-unincluded insert operation
⌊𝑘 ∙ 𝑋. 𝑠𝑖𝑧𝑒⌋ increases by 1 or stays the same
𝑋. 𝑓𝑢𝑠𝑒 always decreases by 1
∴ 𝑓(𝑋, 𝑖) > 𝑓(𝑋, 𝑖 − 1)
iii)
𝑖th operation was a rebuild-unincluded delete operation
⌊𝑘 ∙ 𝑋. 𝑠𝑖𝑧𝑒⌋ decreases by 1 or stays the same
𝑋. 𝑓𝑢𝑠𝑒 always decreases by 1
∴ 𝑓(𝑋, 𝑖) ≥ 𝑓(𝑋, 𝑖 − 1)
By i), ii), iii), 𝑓(𝑋, 𝑖) ≥ 0
∴ 𝑇. 𝑓𝑢𝑠𝑒 ≤ ⌊𝑘 ∙ 𝑇. 𝑠𝑖𝑧𝑒⌋

Corollary 5.1.2 If 𝑇. 𝑠𝑖𝑧𝑒 <

2
𝑘

for some subtree 𝑇 , then after an insert/delete operation to 𝑇 , a rebuild is

followed for 𝑇 or a subtree including it.
Proof.
2

𝑇. 𝑓𝑢𝑠𝑒 ≤ ⌊𝑘 ∙ 𝑇. 𝑠𝑖𝑧𝑒⌋ ≤ 1 (∵Lemma 5.1.1, 𝑇. 𝑠𝑖𝑧𝑒 < )
𝑘

Therefore, after an insert or delete operation, 𝑇. 𝑓𝑢𝑠𝑒 ≤ 0.
This makes only two cases possible for the location of rebuild.
i)
An ancestor node of 𝑇. 𝑟𝑜𝑜𝑡 was chosen as the location of rebuild.
ii)
𝑇. 𝑟𝑜𝑜𝑡 was chosen as the location of rebuild.
∴ After the insert/delete operation, a rebuild is followed for 𝑇 or a subtree including it.

Second, for rebuilt trees with size no less than 2/𝒌, they are guaranteed to be

𝟏
𝟐−𝟐𝒌

-weight-balanced even

after no more than ⌊𝒌 ∙ 𝑻. 𝒔𝒊𝒛𝒆⌋ − 𝟏 insert/delete operations. It is explained in the following Lemma 5.1.3,
and implies that such trees are

1
2−2𝑘

-weight-balanced even without a rebuild.

2

Lemma 5.1.3 For a rebuilt subtree 𝑇 where 𝑇. 𝑠𝑖𝑧𝑒 ≥ , after less than ⌊𝑘 ∙ 𝑇. 𝑠𝑖𝑧𝑒⌋ insert/delete operations,
𝑘

the resultant subtree is

1
2−2𝑘

-weight-balanced.

Proof.
Assume there were 𝑎 insertions and 𝑏 deletions.
0 ≤ 𝑎 + 𝑏 ≤ ⌊𝑘 ∙ 𝑇. 𝑠𝑖𝑧𝑒⌋ − 1
For the initial balanced subtree 𝑇, assume 𝑛0 = 𝑇. 𝑠𝑖𝑧𝑒 for convenience.
Also say the resultant subtree as 𝑇′, and 𝑛 = 𝑇 ′ . 𝑠𝑖𝑧𝑒
Note that 𝑛 = 𝑛0 + 𝑎 − 𝑏 .
For any subtree 𝑐ℎ𝑖𝑙𝑑 between 𝑇. 𝑙𝑒𝑓𝑡 and 𝑇. 𝑟𝑖𝑔ℎ𝑡,
𝑐ℎ𝑖𝑙𝑑. 𝑠𝑖𝑧𝑒 ≤

𝑛0
2

(∵ 𝑇 is 1/2-weight-balanced)

Thus, for any subtree 𝑐ℎ𝑖𝑙𝑑’ between 𝑇’. 𝑙𝑒𝑓𝑡 and 𝑇’. 𝑟𝑖𝑔ℎ𝑡,
𝑐ℎ𝑖𝑙𝑑′. 𝑠𝑖𝑧𝑒 ≤

𝑛0
2

+𝑎

Since 𝑎 + 𝑏 ≤ ⌊𝑘𝑛0 ⌋ − 1 ≤ 𝑘𝑛0 − 1,
𝑏 ≤ 𝑘𝑛0 − 𝑎 − 1.
Therefore,
𝑛 = 𝑛0 + 𝑎 − 𝑏 ≥ 𝑛0 − 𝑘𝑛0 + 2𝑎 + 1
1
1
⟺
𝑛≥
(𝑛 − 𝑘𝑛0 + 2𝑎 + 1)
2 − 2𝑘
2 − 2𝑘 0
𝑛0
2𝑎𝑘 + 1
=
+𝑎+
2
2 − 2𝑘
𝑛0
≥
+𝑎
2
≥ 𝑐ℎ𝑖𝑙𝑑′. 𝑠𝑖𝑧𝑒
∴ 𝑇′. 𝑙𝑒𝑓𝑡. 𝑠𝑖𝑧𝑒 ≤
∴ 𝑇′ is

1
2−2𝑘

1
2−2𝑘

𝑇′. 𝑠𝑖𝑧𝑒, and 𝑇′. 𝑟𝑖𝑔ℎ𝑡. 𝑠𝑖𝑧𝑒 ≤

1
2−2𝑘

𝑇′. 𝑠𝑖𝑧𝑒

-weight-balanced

By combining two of the cases, it can be explained that the fused tree is always

1
2−2𝑘

-weight-balanced. This can

be done by dividing the cases for a fused tree as the i)initial state, ii)rebuilt state, iii)transferred state, and iv)notrebuilt state.

Theorem 5.1.4 The fused tree is

1
2−2𝑘

-weight-balanced.

Proof.
For a subtree 𝑇 in the fused tree, four cases can be supposed.
i)
𝑇 had no insertion/deletion after its creation.
𝑇. 𝑙𝑒𝑓𝑡. 𝑠𝑖𝑧𝑒 = 𝑇. 𝑟𝑖𝑔ℎ𝑡. 𝑠𝑖𝑧𝑒 = 0
Thus,

1
2−2𝑘

-weight-balanced.

ii)
𝑇 was rebuilt after the last insertion/deletion to 𝑇.
Subtree 𝑇 is 1/2-weight-balanced.
Thus,

1
2−2𝑘

-weight-balanced.

iii)
A subtree including 𝑇 but not 𝑇 was rebuilt after the last insertion/deletion to 𝑇.
All nodes of 𝑇 were transferred into a 1/2-weight-balanced tree.
iv)

Neither 𝑇 nor a subtree including 𝑇 was rebuilt after the last insertion/deletion to 𝑇.

By the contraposition of Corollary 5.1.2, 𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑 ≥
Therefore, by Lemma 5.1.3, 𝑇 is
By i),ii),iii),iv), the fused tree is

1
2−2𝑘

1
2−2𝑘

-weight-balanced.

-weight-balanced.

2
𝑘

can be deduced.

To repeat, the height of an α-weight-balanced binary search tree is no more than ⌊log 1 𝑛⌋. Thus, search operations
𝛼

have logarithmic costs in the fused tree.

5.2 Amortized Cost of Insert/Delete Operations
The cost of a rebuild-included insert/delete operation can be amortized to have a logarithmic cost. This is since a
rebuild, which costs Ο(𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑), only happens after Θ(𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑) insert/delete operations. To be
more precise, a rebuild cost for max [𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑 + max(1, ⌊𝑘 ∙ 𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑⌋)] nodes gets amortized
into max(1, ⌊𝑘 ∙ 𝑇. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑⌋) (the number of operations). The cost gets amortized in an explicit sense.
Thus, by using the potential method of amortized analysis [10], we can show that the amortized cost of an
insert/delete operation is logarithmic. This can be done by (over)charging rebuild-unincluded insert/delete
operations

𝑘+1
𝑘

times its actual cost, and then using the accumulated “credit” to pay for the rebuild cost.

Note that in some cases, there is no “credit” accumulated to pay for the rebuild cost. Such cases are possible when
2

𝑇. 𝑠𝑖𝑧𝑒 < + 1 for a rebuilt subtree 𝑇, where its next insert/delete operation includes a (consecutive) rebuild.
𝑘

These cases can be handled exceptionally, since the rebuild cost in such cases are Ο(1).

Theorem 5.2.1 If a fused tree was built from a sequence of 𝑛 insert operations and 𝑚 search/delete operations,
the amortized cost of an insert/delete operation is Ο(log 𝑛).
Proof.
For a fused tree 𝑇, assume the cost of the rebuild-unincluded insert/delete operation is bound by
𝑎 ∙ log 1 𝑇. 𝑠𝑖𝑧𝑒 + C .
α

Also, assume the cost of rebuild is bounded by 𝑏 ∙ 𝑇. 𝑠𝑖𝑧𝑒 + C .
For after 𝑖 insert/delete operations, say the resultant tree as 𝑇𝑖 .
Also, define the potential function for node 𝑁 as
𝑘+1
Φ𝑁,𝑖 = 𝑏 ∙
(𝑖 − 𝐿𝑁 )
𝑘
where the creation of 𝑁 or the last rebuild for the subtree rooted at 𝑁 was after 𝐿𝑁 insert/delete operations.
Note that since 𝑖 ≥ 𝐿𝑁 , Φ𝑁,𝑖 ≥ 0 .
Several cases can be supposed for the subsequent events of an insertion/deletion.
i)
The 𝑖th insert/delete operation of node 𝑁 did not cause a rebuild.
ci ≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝐶
𝛼

ĉi = ci +

∑

(Φ𝑀,𝑖 − Φ𝑀,𝑖−1 )

𝑀 is an ancestor node of 𝑁

≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙
𝛼

𝑘+1
∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + C
𝑘
𝛼

𝑘+1
) log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + C
𝑘
𝛼
∴ ĉi = Ο(log 𝑇𝑖 . 𝑠𝑖𝑧𝑒)
= (𝑎 + 𝑏 ∙

ii)
A rebuild for subtree 𝑋 followed the 𝑖th insertion/deletion of node 𝑁.
This implies 𝑖 = 𝐿𝑁 + max(1, ⌊𝑘 ∙ 𝑋. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑⌋), and leads to two cases.
⌊𝑘 ∙ 𝑋. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑⌋ ≤ 1
i)
This means Φ𝑋,𝑖 = Φ𝑋,𝑖−1 = 0 (The potential cannot “pay off” the credit).
Since 𝑋. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑 <

2
𝑘

and 𝑋. 𝑠𝑖𝑧𝑒 ≤ 𝑋. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑 + 1,

2
+1
𝑘
Note that 𝑋. 𝑠𝑖𝑧𝑒 = Ο(1)
𝑋. 𝑠𝑖𝑧𝑒 <

ci ≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ 𝑋. 𝑠𝑖𝑧𝑒 + 2C
𝛼

ĉi = ci +

∑

(Φ𝑀,𝑖 − Φ𝑀,𝑖−1 )

𝑀 is an ancestor node of 𝑋.𝑟𝑜𝑜𝑡

𝑘+1
∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 2C
𝑘
𝛼
𝛼
2
𝑘+1
< 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ ( + 1) + 𝑏 ∙
∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 2C
𝑘
𝑘
𝛼
𝛼
𝑘+1
2
= (𝑎 + 𝑏 ∙
) log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ ( + 1) + 2C
𝑘
𝑘
α
∴ ĉi = Ο(log 𝑇𝑖 . 𝑠𝑖𝑧𝑒)
≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ 𝑋. 𝑠𝑖𝑧𝑒 + 𝑏 ∙

⌊𝑘 ∙ 𝑋. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑⌋ > 1
ii)
Say 𝑛0 = 𝑋. 𝑙𝑎𝑠𝑡_𝑟𝑒𝑏𝑢𝑖𝑙𝑑
ci ≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ 𝑋. 𝑠𝑖𝑧𝑒 + 2C
α

ĉi = ci +

∑

(Φ𝑀,𝑖 − Φ𝑀,𝑖−1 )

𝑀 is an ancestor node of 𝑋.𝑟𝑜𝑜𝑡

𝑘+1
∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + Φ𝑋,𝑖 − Φ𝑋,𝑖−1 + 2C
𝑘
α
α
𝑘+1
𝑘+1
(𝑘𝑛0 − 1) + 2C
= 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ 𝑋. 𝑠𝑖𝑧𝑒 + 𝑏 ∙
∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 0 − 𝑏 ∙
𝑘
𝑘
α
α
𝑘+1
𝑘+1
(𝑘𝑛0 − 1) + 2C
≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ (𝑛0 + 𝑘𝑛0 ) + 𝑏 ∙
∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 − 𝑏 ∙
𝑘
𝑘
α
α
𝑘+1
= 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙
log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 + 2C
𝑘
α
α
𝑘+1
= (𝑎 + 𝑏 ∙
) log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 + 2C
𝑘
α
∴ ĉi = Ο(log 𝑇𝑖 . 𝑠𝑖𝑧𝑒)
≤ 𝑎 ∙ log 1 𝑇𝑖 . 𝑠𝑖𝑧𝑒 + 𝑏 ∙ 𝑋. 𝑠𝑖𝑧𝑒 + 𝑏 ∙

Since 𝑇𝑖 . 𝑠𝑖𝑧𝑒 ≤ 𝑛,
Ο(log 𝑇𝑖 . 𝑠𝑖𝑧𝑒) = Ο(log 𝑛).
Therefore, the amortized cost for an insert/delete operation is Ο(log 𝑛).

This completes the following Theorem 5.2.2.
Theorem 5.2.2 In a fused tree, for a sequence of 𝑛 insert operations and 𝑚 search/delete operations, the
amortized cost is Ο(log 𝑛) per insert/delete operation and Ο(log 𝑥) for search operations, where x is the size
of the tree the search is performed on.

6. Comparison with the Scapegoat Tree
Since the fused tree was based on the scapegoat tree, it shall be compared with it in the following.
Both use partial rebuilds to balance search trees, based on an α-weight-balance.
-

This offers the choice between lower height and rarer rebuilds.

-

Insert/delete operations have an amortized logarithmic cost.

-

Applicable for multidimensional trees. [7]

Fused trees have some implementational differences with the scapegoat tree.
-

Uses consistent methods for both insert and delete operations.
Deciding a rebuild is only done by constantly checking and updating “fuse” values. Not by separated
methods of 1)comparing the depth of the inserted node with its appropriate depth, or 2)comparing the
tree’s current size with the max-reached size of the tree, which needs constant update.

-

The process of deciding a rebuild was simplified.
No need to check whether the tree is actually unbalanced. Thus, also no need to (recursively) count the
size of the tree to find the non-α-weight-balanced node.

-

When several locations for rebuild exists, the one with max height is chosen.

-

A rebuild needs to reset all “fuse” values.

Fused trees have some performance differences with the scapegoat tree.
-

Strictly α-weight-balanced. May lead to smaller height compared to the scapegoat tree.

-

Possibly more frequent rebuilds. A rebuild can occur even for balanced subtrees.

-

Requires an extra integer value at all nodes.

7. Conclusion
With a cost, the scapegoat tree was simplified to be even simpler. This cost was more frequent rebuilds and an
extra integer value to be stored at all nodes. The return was a simple and explicit method of balancing trees, mainly
explainable in one sentence. In situations where this cost is not much concerned, the fused tree will fit perfect as
a simple and “working” balanced search tree.

References

[1] A. Andersson, "Balanced search trees made simple," in Proceedings of the 3rd Workshop on Algorithms and
Data Structures, 1993, pp. 60-71, doi:10.1007/3-540-57155-8 236.
[2] G. Adelson-Velsky and E. Landis, "An algorithm for the organization of information," Dokladi Akademia
Nauk SSSR, vol. 146, 1962, pp. 263-266.
[3] R. Bayer, "Binary B-trees for virtual memory," in Proceedings of the 1971 ACM SIGFIDET (now SIGMOD)
Workshop on Data Description, 1971, pp. 219-235, doi:10.1145/1734714.1734731.
[4] M. J. Ian, T. Papadakis and R. Sedgewick, "Deterministic skip lists," in Proceedings of the third annual
ACM-SIAM symposium on Discrete algorithms, 1992, pp. 367-375.
[5] "Stack Overflow Developer Survey 2017,"
https://insights.stackoverflow.com/survey/2017.

Stack

Overflow,

2017.

[Online].

Available:

[6] I. Galperin and R. L. Rivest, "Scapegoat trees," in Proceedings of the fourth annual ACM-SIAM Symposium
on Discrete algorithms, 1993, pp. 165-174.
[7] A. Andersson, "General Balanced Trees," Journal of Algorithms, vol. 30, 1999, pp. 1-18, doi:
10.1006/jagm.1998.0967.
[8] H. Chang and S. S. Iyangar, "Efficient algorithms to globally balance a binary search tree," Communications
of the ACM, vol. 27, 1984, pp. 695-702, doi:10.1145/358105.358191.
[9] W. A. Martin and D. N. Ness, "Optimizing binary trees grown with a sorting algorithm," Communications
of the ACM, vol. 15, 1972, pp. 88-93, doi:10.1145/361254.361259.
[10] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, "Amortized Analysis," in Introduction to
Algorithms, 3rd ed., MIT Press, 2009, pp. 459-463.

