Efficient Top-Down Updates in AVL Trees

A binary search tree is an ordered rooted tree $𝒯$ in which each tree node $x$ has one key $\mathrm{𝗄𝖾𝗒}(x)$, one left child $x_1$ and one right child $x_2$, which can be tree nodes or null nodes; null nodes represent the empty tree and have no key nor children, and tree nodes whose two children are null nodes are called leaves. By definition, the descendants of $x$ consist of $x$, its children $x_1$ and $x_2$, and all their descendants (if they are tree nodes); these descendants form a sub-tree of $𝒯$ rooted at $x$ and denoted by $𝒯(x)$, and $x$ is one of their ancestors.

Node keys are pairwise distinct, and must belong to a linearly ordered set. For each tree node $y$ that descends from $x$, we have if $y$ belongs to $𝒯(x_1)$, and $\mathrm{𝗄𝖾𝗒}(y)>\mathrm{𝗄𝖾𝗒}(x)$ if $y$ belongs to $𝒯(x_2)$. Moreover, the height of $x$ is the length (i.e., the number of parent-child edges) of the longest downward path starting from $x$ and ending in a leaf; it is denoted by $𝗁(x)$. By convention, each null node has height $-1$.

A binary search tree is an AVL tree when the height difference $𝗁(x_1)-𝗁(x_2)$ belongs to the set $\{-1,0,1\}$ for all tree nodes $x$. This ensures that an AVL tree with $n$ nodes is of height $𝒪(\log (n))$.

Here, we follow the presentation of [5] and assume that AVL tree structures are implemented by assigning a rank $𝗋(x)$ to each tree node $x$. This rank is our current estimation of the height $𝗁(x)$, which may be slightly invalid if, say, some leaf was inserted way below $x$, and we did not yet have the time to update information about the height of $x$. Hence, we should control the rank differences $𝗋(x)-𝗋(x_i)$ for each node $x$. Focusing on these differences, we say that $x_i$ is an $\mathrm{\ell }$-child if $𝗋(x)-𝗋(x_i)=\mathrm{\ell }$, and that $x$ is an $\{\mathrm{\ell },{\mathrm{\ell }}^{\prime }\}$-node if its children are $\mathrm{\ell }$- and ${\mathrm{\ell }}^{\prime }$-children.

In practice, these ranks are rarely stored directly in AVL implementations: instead, each node $x$ contains either (i) the difference $𝗋(x_2)-𝗋(x_1)$ between the ranks of its children $x_1$ and $x_2$, or (ii) the difference $𝗋(p)-𝗋(x)$ between the rank of its parent $p$ and its own rank. In what follows, we will disregard these implementation details, and pretend that we stored node ranks in clear; adapting our algorithm to let it fit the frameworks (i) or (ii) is easy.

Since binary search trees represented ordered sets, the three main operations they must support are searching, inserting, and deleting an element. Searching an element is easy: when searching a key $k$ in a non-empty tree $𝒯(x)$, we compare $k$ with $\mathrm{𝗄𝖾𝗒}(x)$; then, we keep searching $k$ in $𝒯(x_1)$ if , or in $𝒯(x_2)$ if $k>\mathrm{𝗄𝖾𝗒}(x)$, or we declare that $k$ was found if $k=\mathrm{𝗄𝖾𝗒}(x)$; whereas, when searching $k$ in an empty tree, we must declare that $k$ was nowhere to be found.

Inserting or deleting an element is substantially more difficult, because it requires altering the structure of the tree: this may change its height and even damage the balance of some tree nodes. As a result, the relation $𝗋(x)=\max \{𝗋(x_1),𝗋(x_2)\}+1$ might fail for one node $x$, or one rank difference $𝗋(x_1)-𝗋(x_2)$ might no longer belong to the set $\{-1,0,1\}$. The purpose of bottom-up rebalancing algorithms is precisely to eliminate this anomaly, either directly, or by “propagating it upward”, i.e., making it concern a strict ancestor of $x$, with rank larger than $𝗋(x)$.

A cut of a tree $𝒯$ is a list $(x^1,x^2,\mathrm{\dots },x^{\mathrm{\ell }})$ of nodes of $𝒯$ that are pairwise incomparable for the ancestorship relation (i.e., the sub-trees $𝒯(x^i)$ are pairwise disjoint), ordered from left to right, and which is maximal for inclusion.

Let $x$ denote the root of $𝒯$. When the nodes $x^1,x^2,\mathrm{\dots },x^{\mathrm{\ell }}$ have ranks $𝗋(x)-{\delta }^1$, $𝗋(x)-{\delta }^2,\mathrm{\dots },$ $𝗋(x)-{\delta }^{\mathrm{\ell }}$, the profile of the associated cut is defined as the integer tuple $𝜹=({\delta }^1,{\delta }^2,\mathrm{\dots },{\delta }^{\mathrm{\ell }})$. Accordingly, we say that a node $x$ has profile $𝜹$ when $𝒯(x)$ contains a tree cut of profile $𝜹$. When the order of the integers ${\delta }^1,{\delta }^2,\mathrm{\dots },{\delta }^{\mathrm{\ell }}$ is irrelevant, we may also say that $x$ has profile $\{{\delta }^1,{\delta }^2,\mathrm{\dots },{\delta }^{\mathrm{\ell }}\}$, just writing a multiset of integers: this just means that there exists a permutation $\sigma$ of $\{1,2,\mathrm{\dots },\mathrm{\ell }\}$ such that $x$ has profile $({\delta }^{\sigma (1)},{\delta }^{\sigma (2)},\mathrm{\dots },{\delta }^{\sigma (\mathrm{\ell })})$. In particular, an $\{\mathrm{\ell },{\mathrm{\ell }}^{\prime }\}$-node is simply a node with profile $\{\mathrm{\ell },{\mathrm{\ell }}^{\prime }\}$.

Below, we may modify the structure of a tree $𝒯$, thus generalising so-called rotations: starting from a cut $(x^1,x^2,\mathrm{\dots },x^{\mathrm{\ell }})$ of $𝒯$, let $a^1,a^2,\mathrm{\dots },a^{\mathrm{\ell }-1}$ be the strict ancestors of the cut nodes $x^i$, listed from left to right. We assign a new pair of children to each node $a^i$, and decide that the new root should be some node $a^j$, as long as the graph we obtain is a binary search tree rooted at $a^j$; nodes $a^j$ are said to be affected by the cut rebalancing. While doing so, (i) we must never modify the structure or rank of any of the sub-trees $𝒯(x^i)$, and (ii) node ranks of nodes $a^i$ are reassigned to make sure that each node $a^i$ is a $\{1,1\}$- or a $\{1,2\}$-node in the resulting tree. Such an operation is called a cut rebalancing, and is easy to describe diagrammatically, like in Figure 1 below; cut nodes and their ancestors will typically be denoted with capital letters, from left to right.

Inserting a key may create a zero-edge, i.e., an edge between a parent $x$ and its child $x_i$ such that $𝗋(x)=𝗋(x_i)$; in that case, the integer $𝗋(x)=𝗋(x_i)$ is called the rank of the zero-edge. A zero-edge is created when $x$ is a leaf below which we wish to insert the key $k$, because some child $x_i$ of $x$, which used to be null, becomes a leaf.

Similarly, deleting a key may create a $\{2,2\}$- or $\{1,3\}$-node, which we call a four-node; this happens if $x$ is a $\{1,2\}$-node one of whose children is a leaf containing the key $k$ we wish to delete, because that leaf will be transformed into a null node.

Zero-edges are dealt with as follows, and as illustrated in Figure 1. Up to using a left-right symmetry, and without loss of generality, we assume that $𝗋(x_1)⩾𝗋(x_2)$, i.e., that both $𝗋(x)$ and $𝗋(x_1)$ are equal to the rank $𝗋$ of the zero-edge:

1. 1.

   If $𝗋(x_{11})=𝗋(x_{12})=𝗋-1$ and $𝗋(x_2)=𝗋-2$ (row 1, left), the cut $(x_{11},x_{12},x_2)$ has profile $(1,1,2)$. Let $𝖠$, $𝖢$ and $𝖤$ denote the cut nodes $x_{11}$, $x_{12}$ and $x_2$, and let $𝖡$ and $𝖣$ denote their ancestors $x_1$ and $x$. We rebalance $𝒯(x)$ by letting $𝖣$ become the parent of $𝖢$ and $𝖤$, and $𝖡$ become the parent of $𝖠$ and $𝖣$, thus obtaining a tree with root $𝖡$. This cut rebalancing is a simple rotation.

2. 2.

   If $𝗋(x_{11})=𝗋-1$ and $𝗋(x_{12})=𝗋(x_2)=𝗋-2$ (row 1, right), we perform the same rotation; however, the resulting ranks differ.

3. 3.

   If $𝗋(x_{12})=𝗋-1$ and $𝗋(x_{11})=𝗋(x_2)=𝗋-2$ (row 2, left), the cut $(x_{11},x_{121},x_{122},x_2)$ is to be rebalanced. Let $𝖠$, $𝖢$, $𝖤$ and $𝖦$ denote the cut nodes $x_{11}$, $x_{121}$, $x_{122}$ and $x_2$, and let $𝖡$, $𝖣$ and $𝖥$ denote their ancestors $x_1$, $x_{12}$ and $x$. We rebalance $𝒯(x)$ by giving these seven nodes the shape of a complete binary tree: $𝖡$ becomes the parent of $𝖠$ and $𝖢$, $𝖥$ becomes the parent of $𝖤$ and $𝖦$, and $𝖣$ becomes the parent of $𝖡$ and $𝖥$, as well as the root of the resulting tree. This is a double rotation.

4. 4.

   If $𝗋(x_2)=1$ (row 2, right), we rebalance $𝒯(x)$ by not changing its structure, but simply increasing the rank of its root $x$. This is a promotion.

Doing so, whenever we face a zero-edge $e$ of rank $𝗋$, we will either eliminate it at once, or replace it by a new zero-edge $e^{\prime }$ of rank $𝗋+1$, placed just above where $e^{\prime }$ used to be. Consequently, if inserting a key creates a zero-edge, we will simply propagate that zero-edge upward until it disappears.

Likewise, four-nodes are dealt with as follows, and as illustrated in Figure 2. Up to using a left-right symmetry, we assume that $𝗋(x_1)⩾𝗋(x_2)$:

1. 5.

   If $𝗋(x_{11})=𝗋(x_{12})=𝗋-2$ and $𝗋(x_2)=𝗋-3$ (row 1, left), we perform a simple rotation.

2. 6.

   If $𝗋(x_{11})=𝗋-2$ and $𝗋(x_{12})=𝗋(x_2)=𝗋-3$ (row 1, right), we perform the same rotation; the resulting ranks differ.

3. 7.

   If $𝗋(x_{12})=𝗋-2$ and $𝗋(x_{11})=𝗋(x_2)=𝗋-3$ (row 2, left), we perform a double rotation.

4. 8.

   If $𝗋(x_2)=𝗋-2$ (row 2, right), we decrease the rank of its root $x$; this is a demotion.

Cut rebalancing operations 5 to 7 are the same as operations 1 to 3 for eliminating zero-edges, except that the ranks of $x_1$, $x_2$ and their descendants were all shifted down by one. In all eight cases, these operations result either in eliminating the four-node $x$ or in making the (former) parent of $x$ our new four-node.

The textbook algorithm presented in Section 2.3 aims at eliminating or propagating upward zero-edges and four-nodes. Thus, each insertion or deletion update consists in (i) finding the location at which we want to create or delete a tree leaf, (ii) observe that we may have created a zero-edge or four-node, (iii) moving this anomaly upward, until (iv) we eliminate it once and for all. Step (i) requires no write operation on the tree structure, and steps (ii) and (iv) occur once per update. However, step (iii) may require arbitrarily many write operations per update.

Hence, cut rebalancing operations of cases 1 to 8 are called terminal if they result in eliminating the anomaly (thus being a part of step (iv)), and transient if they just propagate it upward (thus being a part of step (iii)): transient operations are operations 1 and 4 when $x$ used to be a $1$-child, and operations 6 to 8 when $x$ had a parent that used to be a $\{1,2\}$-node. We should prove that updating $n$ times an initially empty AVL tree triggers $𝒪(n)$ transient operations.

With the textbook algorithm, the statement we wish to prove is invalid, as was shown in [2]. Consequently, we will tweak the operations performed in cases 1 to 8, aiming at making them terminal whenever possible.

The complexity proof of the resulting algorithm is based on potential techniques. In our case, we define the potential of a a tree $𝒯$ as the the number of $\{1,2\}$-nodes, plus twice the number of full nodes it contains, where full nodes are defined as follows.

In absence of zero-edges, a node $x$ is called full when $x$ and its two children $x_1$ and $x_2$ are $\{1,1\}$-nodes, and at least one of its grand-children $x_{12}$ and $x_{21}$ is a $\{1,1\}$-node. In other words, a node is full when it has profile $(2,3,3,2,2)$ or, symmetrically, $(2,2,3,3,2)$. When zero-edges are (temporarily) allowed, a node $x$ may also be considered full if $x$ is a $\{0,1\}$-node whose $1$-child is a $\{1,1\}$-node; or if $x$ is a $\{1,1\}$-node, $x_1$ and $x_2$ are $\{0,1\}$- and/or $\{1,1\}$-nodes, and one of $x_{12}$ and $x_{21}$ is a $0$-child or a null, a $\{0,1\}$- or a $\{1,1\}$-node.

As we will prove:

1. 1.

   each update or write operation modifies the neighbourhood (parenthood relations and/or rank) of a constant number of nodes, thus increasing the tree potential by at most a constant;

2. 2.

   each transient operation aimed at eliminating a zero-edge of rank $𝗋⩾4$ destroys one full node and creates one $\{1,2\}$-node, thus decreasing the tree potential;

3. 3.

   each transient operation triggered by a deletion decreases the number of $\{1,2\}$-nodes, and does not increase the number of full nodes, also decreasing the tree potential.

Statement 1 will be immediate, and thus we will focus on proving statement 2 in Section 3.3 (this will be Lemma 3), and statement 3 in Section 3.4 (this will be Lemma 4). Once all three statements are proved, we will finally be able to derive the following result.

Some cut profiles, such as the ones that charaterise full nodes, allow rebalancing trees to either increase or decrease their rank. More precisely, if we are lucky enough, a tree $𝒯$ with rank $𝗋$ and profile $𝜹$ will always admit a cut, whose profile does not need to be $𝜹$, that can be rebalanced to obtain a tree ${𝒯}^{\prime }$ of rank ${𝗋}^{\prime }=𝗋+\epsilon$, where $\epsilon =\pm 1$ is an integer of our choice. This cut rebalancing operation is called a cut promotion when $\epsilon =1$, and a cut demotion when $\epsilon =-1$.

Some profiles ensure that a cut promotion or demotion can be performed, as outlined by the following result.

Let us modify the textbook insertion algorithm to make some transient operations, which should occur in cases 1 and 4 of page 1, terminal operations. In particular, all transient operations in our variant are already transient in the textbook algorithm.

Case 1 is easy to take care of. Indeed, let us say that a node $x$ is weak when $x$ is either a leaf or a $\{1,2\}$-node whose $1$-child is also weak. An immediate induction proves that, when using the textbook algorithm, the lower end of a zero-edge is always weak. This proves, in particular, the well-known fact that case 1 is actually spurious, since it features a zero-edge whose lower end is a $\{1,1\}$-node.

It remains to take care of case 4, which we subdivide into two sub-cases. First, we promote $x$ like in the textbook algorithm, thus obtaining a tree ${𝒯}^{\prime }$ of rank $𝗋+1$. Then,

1. 4.
   1. a)

      if $x_2$ is a $\{1,1\}$-node, we do nothing more: we just performed a node promotion;

   2. b)

      if $x_2$ is a $\{1,2\}$-node, let us recall that $x_1$ is weak, which gives it the profile $\{2,2,3\}$, whereas $x_2$ has profile $\{1,2\}$; hence, ${𝒯}^{\prime }$ has profile $\{3,3,3,4,4\}$, and a cut demotion transforms ${𝒯}^{\prime }$ into a tree ${𝒯}^{\prime \prime }$ of rank $𝗋$ again: we just performed a terminal operation.

Similarly, we wish to transform as many transient operations, which occur in cases 6 to 8 of the textbook textbook algorithm, into terminal operations.

The rotations and demotion performed in these cases transform a tree $𝒯(x)$ of rank $𝗋$ rooted at a four-node $x$ into a tree ${𝒯}^{\prime }$ of rank $𝗋-1$ whose root $x^{\prime }$ is a $\{1,1\}$-node. If $x^{\prime }$ is full, performing a cut promotion on ${𝒯}^{\prime }$ results in another tree ${𝒯}^{\prime \prime }$ of rank $𝗋$; similarly, if some child $x_i^{\prime }$ of $x^{\prime }$ is full, performing a cut promotion on ${𝒯}^{\prime }(x_i^{\prime })$ and increasing the rank of $x^{\prime }$ by $1$ also transforms ${𝒯}^{\prime }$ into another tree ${𝒯}^{\prime \prime }$ of rank $𝗋$; and if both children of $x^{\prime }$ are full, $x^{\prime }$ is also full, a case we already took care of. In all cases, this two-step transformation of $𝒯(x)$ into ${𝒯}^{\prime \prime }$ is a terminal operation.

If, however, neither $x^{\prime }$ nor its children is full, the rotation or demotion we performed in case 6, 7 or 8 did not create any full node. Indeed, replacing $𝒯(x)$ by a tree of smaller rank did not make any ancestor of $x$ a full node. The only other nodes whose rank or induced sub-tree was changed are $x^{\prime }$ and its children, which we precisely assumed are not full either. In that case, our operation is transient if the parent of $x$, say $y$, was a $\{1,2\}$-node, and became a four-node.

Our top-down algorithms for inserting a key $k$ in a tall enough AVL tree $𝒯$ and for deleting $k$ from $𝒯$ follow the same general ideas, which were already successfully applied to weak AVL trees [5]. We will discover, in a top-down manner, the branch $x^0,x^1,\mathrm{\dots }$ below which $k$ should be inserted or deleted, where $x^0$ is the root of $𝒯$ and each node $x^{i+1}$ is a child of the previous node $x^i$. Using a $𝒪(1)$ look-ahead, and after discovering the first $𝒪(1)$ nodes on that branch, we must already decide what to do.

If we are lucky enough, we found a node $x^i$, for some integer $i⩾1$, that is deemed safe: propagating a zero-edge (during insertions) or four-node (during deletions) that we would have planted along our branch far enough below $x^i$ will stop when meeting $x^i$. When such a node $x^i$ exists among the top few nodes of the branch, we say that $𝒯$ was friendly; indeed, we should simply focus on updating the tree $𝒯(x^i)$, whose rank is smaller than $𝒯$ itself, and which will be transformed into a new tree of the same rank.

This fortunate case suggests focusing only on updating trees whose root is safe. Hence, if $𝒯$ has an unsafe root, a preliminary step will consist in transforming $𝒯$ into a tree whose root is safe, which we will then update; all subsequent (recursively called) updates will be performed on trees whose root is safe.

If, however, $𝒯$ has a safe root but is unfriendly, we will choose a deep enough node, say $x^{\mathrm{\ell }}$, and transform the sub-tree $𝒯(x^{\mathrm{\ell }})$ into a tree ${𝒯}^{\prime }$ whose root is safe, while promoting it (during insertions) or demoting it (during deletions). This transformation will create a zero-edge or a four-node that will be propagated upward and whose propagation will stop when meeting the safe root $x$; afterward, it just remains to update ${𝒯}^{\prime }$.

Once implemented, these ideas lead to a bottom-up updating algorithm, whose amortised complexity we study now.

Below, we say that a node $x$ is insertion-safe (or simply safe, when the context is clear) when (i) $𝗋(x)=1$ and $x$ is a $\{1,2\}$-node, or (ii) $𝗋(x)⩾2$ and $x$ is not full. We showed in Section 3.2 that each tree rooted at a full node, i.e., each tree $𝒯$ of rank $𝗋⩾2$ whose root is unsafe, can be subject to a cut promotion, resulting in a tree ${𝒯}^{\prime }$ of rank $𝗋+1$ whose root is a $\{1,2\}$-node, thus being safe.

This makes following the recipe of Section 4.1 easy once the desired integer $\mathrm{\ell }$ is chosen. First, if $𝗋(𝒯)⩽\mathrm{\ell }+2$, just use the bottom-up algorithm of Section 3.3, which may result in a tree ${𝒯}^{\prime }$ of rank $𝗋({𝒯}^{\prime })=𝗋(𝒯)+1$ only in case $𝒯$ was rooted at an unsafe node. Otherwise, $𝗋(𝒯)⩾\mathrm{\ell }+3$, and:

1. 1.

   if $𝒯$ is rooted at an unsafe node, cut-promote it, thus obtaining a tree ${𝒯}^{\prime }$ of rank $𝗋({𝒯}^{\prime })⩾\mathrm{\ell }+4$ whose root is safe;

2. 2.

   if $𝒯$ is friendly, let $i⩽\mathrm{\ell }$ be the least positive integer for which $x^i$ is safe: we simply focus on inserting the key $k$ in $𝒯(x^i)$;

3. 3.

   if $𝒯$ is unfriendly, the first nodes $x^1,\mathrm{\dots }$ on our branch are all unsafe; thus, they are $\{1,1\}$-nodes, and the branch contains at least $\mathrm{\ell }$ nodes, with the guarantee that $𝗋(x^{\mathrm{\ell }})⩾𝗋(𝒯)-(\mathrm{\ell }+1)⩾2$, so that all nodes $x^1,\mathrm{\dots },x^{\mathrm{\ell }}$ are full; hence we cut-promote $𝒯(x^{\mathrm{\ell }})$ and promote all nodes $x^1,\mathrm{\dots },x^{\mathrm{\ell }-1}$, thereby creating a zero-edge between $x^0$ and $x^1$, which we eliminate by using the cut rebalancing prescribed in Section 3.3.

We will now characterise deletion-safe (or simply safe, when the context is clear) nodes: a node $x$ should be safe when they can stop propagating four-nodes. There will be three families of safe nodes: (i) surely safe nodes, which stop propagating four-nodes even when using the textbook deletion algorithm, (ii) barely safe nodes, which are some of the nodes that can be transformed to create surely safe nodes in their close vicinity, and (iii) simply safe nodes, which stop propagating four-nodes when using the algorithm of Section 3.4.

Surely safe nodes are the nodes $x$ of rank $𝗋(x)⩾1$ with profile $(1,1)$, or rank $𝗋(x)⩾2$ and profile $(2,2,2)$. Indeed, if some child $x_i$ of $x$ is to be replaced by a node of smaller rank, either (i) $x$ had profile $(1,1)$, in which case its new profile is simply $\{1,2\}$, or (ii) $x$ had profiles $\{1,2\}$ and $(2,2,2)$, in which case $x_i$ was the $2$-child of $x$ (because the $1$-child of $x$ had profile $(1,1)$), and we fall in case 5 of the bottom-up algorithm.

Detecting other kinds of safe nodes is more challenging; in particular, whether a node $x$ is safe may depend on which descendants of $x$ are to be replaced by nodes of smaller rank. More precisely, let $x=x^{\mathrm{\ell }}$ be a node that belongs to the branch $x^0,x^1,\mathrm{\dots }$ below which the key $k$ will be deleted, and let $z=x^{\mathrm{\ell }+4}$.