AA-Tree or simple binary tree

The theme of binary trees has already been discussed in Habré ( here and here ).

About the AA-tree, it was said that "due to the additional restriction, operations are implemented easier than that of a red-ebony tree (due to a decrease in the number of cases to be analyzed)".

However, it seems to me that the AA-tree deserves a separate article.
')
Why?

Because in fact it is the fastest (or one of the fastest) binary tree with a simple implementation.

I will leave outside the scope of this article the consideration of the insertion and deletion algorithms in AVL and red-ebony, but their implementation is usually not trivial. Why?

As it is known, the main problem of a binary tree is its balancing, that is, opposition to degeneration into a regular linked list. Usually when balancing a tree, there are many options for the relative position of the vertices, each of which must be taken into account separately in the algorithm.

The AA-tree was invented by Arne Andersson, who decided that to simplify the balancing of the tree, it was necessary to introduce the concept of level (vertex). If we imagine a tree growing from top to bottom from the root (that is, “standing on the leaves”), then the level of any leaf vertex will be equal to 1. In his work, Arne Andersson gives a simple rule that the AA-tree must satisfy:

To one vertex you can attach another vertex of the same level but only one and only to the right .

(In his article, the author of the AA-tree uses a slightly different terminology associated with 2-3 trees, but the essence does not change).

Thus, the introduced notion of the level of the top does not always coincide with the real height of the top (distance from the ground), but the tree remains balanced when following the rule “one right connection at the same level”.

Balancing an AA tree requires only 2 ( two ) operations.

It is easy to understand them from the rule “one right one-level connection”: this is the elimination of the left connection on the same level and the elimination of two right connections on the same level.

These operations are named in the original work of skew and split , respectively. In the above figures, the horizontal arrow indicates the connection between the vertices of one level, and the inclined (vertical) - between the vertices of different levels.

skew, eliminating the left link on the same level


split, eliminating the two right links at the same level


Let's see what insertion and deletion look like in an AA tree. To simplify the implementation, we introduce the notion of a bottom (" ground "). Her level is always 0 and her left and right link point to her. All leaf vertices refer to bottom instead of storing 0 in the link.

Within the Delphi weeks on Habré, the source code will be in the form of pseudo-code similar to Delphi (for lovers of C ++ coffee : the P ^ .x operation in Delphi is equivalent to P-> x , var means that the variable is passed by reference, and not by value i.e. when changing the external variable changes).

Define the top of an AA-tree.

PNode = ^ TNode ;
TNode = packed record
left , right : PNode ;
level : integer ; // level; 1 at the leaves
key : pointer ; // key, vertex related data
end ;

Inserting the newkey element is easiest to look at in a recursive implementation.

procedure NodeInsert ( var P : PNode ; newkey : pointer ) ;
begin
if P = bottom then begin // reach the "bottom" - create a new vertex
new ( P ) ;
P ^ . left : = bottom ;
P ^ . right : = bottom ;
P ^ . level : = 1 ;
P ^ . key : = newkey ;
end else begin
if newkey <P ^ . key then
NodeInsert ( P ^ . Left , newkey )
else if newkey> P ^ . key then
NodeInsert ( P ^ . Right , newkey )
else begin
P ^ . key : = newkey ;
exit ;
end ;
Skew ( P ) ;
Split ( P ) ;
end ;
end ;

To insert the newkey key into the tree, call NodeInsert (root, newkey) . We go down from the root down the tree, comparing the keys; paste; go up and perform balancing: skew and split for each vertex.

Deleting is a bit trickier.

procedure NodeDelete ( var P : PNode ; newkey : pointer ) ;
begin

if P <> bottom then begin

// 1. go down and remember last and deleted
last : = P ;
if Compare ( newkey , P ) < 0 then // newkey <key
NodeDelete ( P ^ . Left , newkey )
else begin
deleted : = P ;
NodeDelete ( P ^ . Right , newkey ) ;
end ;

// 2. delete the item if found
if ( P = last ) and ( deleted <> bottom ) and ( newkey == deleted ^ . key ) then begin
deleted ^ . key : = P ^ . key ;
deleted : = bottom ;
P : = P ^ . right ;
delete last ;
end else if ( P ^ . left . level <P ^ . level - 1 ) or ( P ^ . right . level <P ^ . level - 1 ) then begin
// 3. perform balancing when moving up
Dec ( P ^ . Level ) ;
if P ^ . right . level > P ^ . level then P ^ . right . level : = P ^ . level ;
Skew ( P ) ;
Skew ( P ^ . Right ) ;
Skew ( P ^ . Right ^ . Right ) ;
Split ( P ) ;
Split ( P ^ . Right ) ;
end ;
end ;

end ;

Two auxiliary variables are used - deleted and last. When going down the tree (as when inserting), the vertex keys are compared with the key to be deleted. If the vertex key is less than the deleted one, then go to the left link, otherwise, go to the right one (that is, go to the right one even if the keys match). Each passable vertex is entered into the last, and only the one where it was “turned right” is entered into the deleted one.

When the “bottom” of the tree is reached, deleted points to the top where the key to be deleted is (if it is in the tree), and last points to the top to be deleted (it can be the same top). The key is transferred from last to deleted and the vertex of last is deleted.

Next is balancing - you need to perform 3 skew and 2 split.

The implementation of skew and split is trivial.

// swap content of records with vertices (not pointers)
procedure Swap ( P1 , P2 : PNode ) ;
var
tmp : TNode ;
begin
tmp : = P1 ^ ;
P1 ^ : = P2 ^ ;
P2 ^ : = tmp ;
end ;

procedure Skew ( T : PNode ) ;
var
L : PNode ;
begin
L : = T ^ . left ;
if T ^ . level = L ^ . level then begin
Swap ( T , L ) ; // now T ==> L, L ==> T
L ^ . left : = T ^ . right ; // i.e. T.left = L.right
T ^ . right : = L ; // i.e. L.right = T
end ;
end ;

procedure Split ( T : PNode ) ;
var
R : PNode ;
begin
R : = T ^ . right ;
if T ^ . level = R ^ . right ^ . level then begin
Swap ( T , R ) ; // now T ==> R, R ==> T
R ^ . right : = T ^ . left ;
T ^ . left : = R ;
Inc ( T ^ . Level ) ;
end ;
end ;

In fact, the above pseudo-code is sufficient to create an implementation of an AA-tree (add only “trifles” such as modifying the root of a tree (root), etc.).

Some useful links.

Implement an AA tree on C.

Wonderful applet where you can play with different types of trees (including AA-trees).

Delphi project with AA-tree visualization and source code.

Wikipedia article .