# SECTION R: AVL TREES

The height of tree T is h(T). For node p, h(p) is the height of the subtree rooted at p.

The balance factor of binary tree T with subtrees L rooted at its left child and R rooted at its right child is Factor(T) = h(L) - h(R). This definition extends to any node of a binary tree. If T is an empty tree, Factor(T) = 0.

If Factor(T) 1, then T is height-balanced.

The nodes of BT8, in Figure R.1 are tagged with their balance factors:

#### Figure R.1

Exercise ER.1 and Problem PR.1 are appropriate at this point.

Given a binary tree bt and a value v, one position at which v may be inserted to retain the order property is determined by NodeSpot and inserted by InsertNode (section 8.5.2). The result is not the only BST with the values it contains. The goal of AVL management is to rearrange bt after the addition of each value so that it is both height-balanced and a BST. There are a number of cases to consider.

A general binary tree T is of the form shown in Figure R.2 .

#### Figure R.2

If h(L) = h(R), then Factor(T) = 0 and the addition of one node to form a new binary tree T' may (or may not) change the balance factor of the root node p to 1, whence T' is still balanced at the node p. Balancing within L or R may be necessary. Note, for example, that a child added to the leftmost leaf node of BT8, would not change the balance of the root node, but an addition to other leaves would do so. Two rightmost additions will leave the root node balanced but the balance factor of the rightmost node of BT8, would change to + 2.

Exercise ER.2 is appropriate at this point.

If h(L) - h(R) = 1, then the addition of a node to R will leave the resulting Factor(p) either 0 or 1 for the root node p, still balanced. If, however, the new tree T' is formed by adding a node to L, the result can be that Factor(p) = 2 unless an adjustment is made. A suitable adjustment switches some of the nodes of L to the right subtree without violating the order property. In that case, p is said to act as a pivot.

Suppose an addition is made to the subtree L, rooted at node Lroot. If the left and right subtrees of Lroot are LL and LR, respectively, then no unbalance is created by an addition unless the height of one of these subtrees is h(R) and the addition is to that subtree and increases its height. Figure R.3 is a model of T.

#### Figure R.3

If the addition increases h(LL) to h(R) + 1, T can be restructured without violating the BST property by using p as a pivot, as shown in Figure R.4. If h(L) - h(R) = - 1 and the addition is at the right in the subtree RR (the analog of LL), the pivot in the opposite direction that may be necessary is symmetric.

#### Figure R.5

A second case occurs when h(LR) = h(R) and an addition is made to LR that causes h(LR) to become h(R) + 1, whence h(Lroot) becomes h(R) + 2. The pivot above will not balance the tree and so one level deeper is involved, as Figure R.5 illustrates. This can be rearranged without violating the BST property by using p as a pivot, as in Figure R.6. The new T' will be balanced if either h(LRR) or h(LRL) is increased by the added node. The symmetric right subtree case for which Factor(T) = - 1 may also occur and be dealt with by a symmetric pivot.

#### Figure R.6

A special case is required for the addition of a node nn to the non-null child of a two-node binary tree. Figure R.7 shows how the left version of this pivot is modeled.

#### Figure R.7

It is important to realize that "root node" generally refers to the root of a subtree, and that pivoting is carried out as deep in the tree as possible.

Exercises ER.3 and ER.4 are appropriate at this point.

## R.1 The Insertion Algorithm for AVL Trees

It is convenient to include a field for the balance factor in the nodes of an AVL tree:

`AVLnode = RECORD`

`Value  : {value type`

`Left :  AVLnode`

`Right :  AVLnode`

`Factor : INTEGER`

`END`

As a node is inserted, the location of the parent of the inserted node and the closest ancestor with Factor > 0, are retained in Parent and Pivot, respectively.

An AVL tree is a BST, and so InsertNode (section 8.5.2) can be used to insert a node p in the tree T. However, it is necessary to modify NodeSpot (section 8.5.2) in order to retain a pointer, Pivot, to the closest ancestor of the new node with nonzero balance factor and its immediate ancestor Parent. This can be done by initializing Pivot to T and Parent to NIL and adding the statement

`if p  .Factor  0`

`then Pivot  p`

`Parent  Pred`

`endif`

as the first statement within the while loop in NodeSpot.

The insertion algorithm becomes:

`procedure AVLinsert(nn,T)`

`if Empty(T)`

`then T  nn`

`nn .Factor  0`

`return`

`endif`

`NodeSpot(T,nn  .Value,Trio,p,Pred,Pivot,Parent)`

`InsertNode(T,nn,Pred,Trio)`

`{small-tree cases are`

`if T  .Right = NIL                      {treated separately`

`then PairLeft`

`return`

`endif`

`if  T  .Left = NIL`

`then PairRight`

`return`

`endif`

`{change factors between Pivot and`

`NewFactors                               {nn, and determine the apparent`

`{change to Pivot  .Factor, PF`

`if  Pivot  .Factor = 0`

`then Pivot  .Factor  PF`

`return`

`endif`

`if  Pivot  .Factor + PF = 0`

`then Pivot  .Factor = 0`

`return`

`endif`

`if  PF < 0`

`then LeftPivot`

`else RightPivot`

`endif`

`end  {AVLinsert`

`procedure NewFactors`

`p  Pivot`

`v  nn  .Value`

`if p  .Value < v`

`then p  p  .Right`

`PF   -1`

`else p  p  .Left`

`PF  +1`

`endif`

`Hub  p                               {the first node between Pivot and nn`

`while p  nn do`

`if p  .Factor < v`

`then p  .Factor  -1`

`p  p  .Right`

`else p  .Factor  +1`

`p  p  .Left`

`endif`

`endwhile`

`end  {NewFactors`

`procedure LeftPivotd`

`if Hub  .Factor = 1                  {do a simple rotation of Hub`

`then Pivot  .Left  Hub  .Right`

`Hub   .Right  Pivot`

`Pivot  .Factor  Hub  .Factor`

`Hub   .Factor  0`

`if  nn  .Value < Parent  .Value`

`then Parent  .Left  Hub`

`else Parent  .Right  Hub`

`endif`

`return`

`endif`

`{do a deeper rotation`

`Cog  Hub  .Left`

`CogLeft  Cog  .Left`

`CogRight  Cog  .Right`

`Hub  .Right  CogLeft`

`Pivot  .Left  CogRight`

`Cog  .Left  Hub`

`Cog  .Right  Pivot`

`case of  Cog  .Factor`

`+1  : Pivot  .Factor  -1`

`Hub  .Factor  0`

`-1  : Pivot  .Factor  0`

`Hub  .Factor  +1`

`else: Pivot  .Factor  0`

`Hub  .Factor  0`

`endcase`

`Cog  .Factor  0`

`if nn  .Value < Parent  .Value`

`then Parent  .Left  Cog`

`else Parent  .Right  Cog`

`endif`

`end  {LeftPivot`

RightPivot is similar.

A PairLeft procedure can be implemented like this:

`procedure PairLeft`

`T  .Left  NIL`

`if Trio = 1`

`then Pred  .Right  T`

`T  Pred`

`else nn  .Right  T`

`nn  .Left  Pred`

`Pred  .Right  NIL`

`T  nn`

`endif`

`T  .Factor  0`

`end {PairLeft`

PairRight is similar.

Deletion from an AVL tree requires modification of CutValue (section 8.5.2) to determine Parent and Pivot, and the rebalance operation must proceed up the tree. It is common to forego deletion entirely; inactive nodes may be so marked or simply ignored.

## Exercises

Exercises immediate applications of the text material

## Problem

Problem not immediate, but not a major extension of the text

## Project

Project for fun; for serious students