With respect to the current node S a sweep

<L_b-1,l_b-1,…,L₀,l₀,S,r₀,R₀,…,r_b-1,R_b-1>

composed of b neighbors and their delimiting keys to the left and to the right of S is called the vicinity of S, where

	S is the current node;
	Li denotes the i-th left neighbor of S;
	Ri denotes the i-th right neighbor of S;
	li is the delimiting key of nodes Li and Li-1;
	ri is the delimiting key of nodes Ri and Ri-1.
	F denotes the direct parent of S.
	FLi (FRi) denotes the parent of node Li (Ri).
	Fli (Fri) denotes the node containing the delimiting key li (ri).
	Li, li, Ri, ri, FLi, FRi, Fli, Fri are the local variables of the procedures.

	WW(S) means that M(S) <= p
	WC(S) means that |S| >= q
	WF(S) means that WW(S) and WC(S)
	IC(s) means that sweep s is incompressible
	WB(s) means that IC(s) for any sweep sof length b containing S
	Sweepbm(S) denotes the m-th (m = 0,…,b) sweep of length b containing node S, namely Sweepb0(S) = <Lb-1,lb-1,…,L0,l0,S> Sweepbb(S) = <S,r0,R0,…,rb-1,Rb-1> Sweepbm(S) = <Lb-m-1,lb-m-1,…,L0,l0,S,r0,R0,…,rm-1,Rm-1>

The following procedures and functions are used for describing the algorithms.

	Search(T,k) given a S(b)-tree T and key k verifies whether the key is contained in the tree. The result of the function is (BoolValue, S, ki). BoolValue is a Boolean variable that specifies whether k is found in the tree or not. S is the node that was visited last while searching in the tree, and ki is the minimal key of S that is greater than or equal to the given key k.
	MakeVicinity(S) initializes the local variables Li, li, Ri, ri, FLi, FRi, Fli, Fri according to S.
	Replace(S,P,Q) replaces a part of node S, that coincides with P, with Q.
	Functions LeftOf(S,k) and RightOf(S,k) define two parts of S, that are, respectively, to the left and to the right of key k in S.
	For each m = 0,…,b we define a function Compressm that is applied to not incompressible sweeps of length b. The result of the function is an incompressible sweep of length b-1, composed of b well-formed (WF see above) nodes. Namely, let Compressm(A0,a1,…,ab,Ab) = <C0,c1,…,cb-1,Cb-1> then the resulting sweep is obtained by distributing the contents of node Am between the other nodes of the initial sweep in such a way that ai < ci for i = 1,…,m, and ci < ai+1 for i = m,…,b-1.
	ComputeSets(S) calculates seven subsets of the set of keys of node S: MLeft, MRight, MDelimL, MDelimR, MDelim, coMLeft, and coMRight.
	ChooseAny(E), ChooseMax(E), ChooseMin(E) for the given key set E return, respectively, an arbitrary, the maximal, and the minimal key of set E.
	MinKey(S) looks for the minimal key in the sub-tree rooted at S, returns (S', k') where k' is the minimal key, and S' is the leaf that contains k'.
	GlueParents(F) takes the parent F of the current node S, the left, and the right neighbors of F, glues them into one node, and returns the result. A more sophisticated variant of this function is to check before gluing whether the neighbors have been modified, and glue to F only the modified ones.
	CreateNewRoot(S) creates the new root of the tree, containing the only reference to the given node S.
	ReleaseRoot(). If the root of the tree contains only one reference to a node S, and no keys, then this root is removed, and S is assigned to be the new root of the tree.
	[P,d,Q] creates a new node composed of all keys, and node references (in case of internal nodes), of the given nodes P and Q, with the key d between them.

If k(S) denotes the set of all keys of node S, then the definitions of the subsets are as follows.

The sets, and the ComputeSets() procedure are used in Balance_W() to control the process of computation.

Procedure Insert(T,k)
    (BoolValue, S, k_i) = Search(T,k);
    if BoolValue = True then return fi;
    /* k haven't been found means that S is a leaf */
    Replace(S,<k_i>,<k,k_i>) /* insert k before k_i */
    Balance(S); /* balance T starting from leaf S */
EndProcedure

Procedure Delete(T,k)
    (BoolValue, S, k_i) = Search(T,k);
    if BoolValue = False then return fi;
    if S is not a leaf then
        /* S is internal, and contains reference */
        /* S_i+1, which is to the right of k_i in S */
        (S', k') = MinKey(S_i+1);
        Replace(S,<k_i>,<k'>);
        S := S';
        k := k';
    fi
    /* S is a leaf */
    Replace(S,<k>,<>) /* delete k from leaf S */
    Balance(S); /* balance T starting from leaf S */
EndProcedure

Procedure Balance(S)
    while S is not the root do
        if ! WB(S) then F := Balance_B(S);
        else if ! WC(S) then F := Balance_C(S);
        else if ! WW(S) then F := Balance_W(S);
        else S := F; continue;
        fi fi fi
        S := GlueParents(F);
    od
    /* S is the root now */
    if |S| = 0 then
        ReleaseRoot();
    fi
    if ! WW(S) then
        CreateNewRoot(S);
        Balance_W(S);
    fi
EndProcedure

Procedure Balance_W(S)
MakeVicinity(S);
ComputeSets(S);

// Compression:
// Distribute all keys of S between
// the other nodes of the vicinity
if coMLeft # coMRight != Empty then
    d := ChooseAny(coMLeft # coMRight);
    <X_b-1,x_b-1,…,x₁,X₀> := Compress^b(L_b-1,l_b-1,…,L₀,l₀,LeftOf(S,d));
    <Y₀,y₁,…,y_b-1,Y_b-1> := Compress⁰(RightOf(S,d),r₀,R₀,…,r_b-1,R_b-1);
    for i := 1 to b-1 do
        Replace(FL_i,<L_i>,<X_i>);
        Replace(Fl_i,<l_i>,<x_i>);
        Replace(FR_i,<R_i>,<Y_i>);
        Replace(Fr_i,<r_i>,<y_i>);
    od
    Replace(FR₀,<R₀>,<Y₀>);
    Replace(Fr₀,<r₀>,<d>);
    if FL₀ = F then
        Replace(F,<L₀,l₀,S>,<X₀>);
    else
        Replace(F,<S>,<X₀>);
        Replace(Fl₀,<l₀>,<x₁>);
        Replace(FL₀,<X₁,x₁,L₀>,<X₁>);
    fi
    return F;
fi

// Move left:
// Move to the left part of the vicinity
// as much keys from S as possible
if coMLeft != Empty then
    if MDelimL # coMLeft != Empty then d := ChooseAny(MDelimL # coMLeft);
    else                               d := ChooseMax(coMLeft);
    <X_b-1,x_b-1,…,x₁,X₀> := Compress^b(L_b-1,l_b-1,…,L₀,l₀,LeftOf(S,d));
    Y := RightOf(S,d);
    for i := 1 to b-1 do
        Replace(FL_i,<L_i>,<X_i>);
        Replace(Fl_i,<l_i>,<x_i>);
    od
    Replace(FL₀,<L₀>,<X₀>);
    Replace(Fl₀,<l₀>,<d>);
    Replace(F,<S>,<Y>);
    if WW(Y) then return F; fi
    S := Y;
    MakeVicinity(S);
    ComputeSets(S);
fi

// Move right:
// Move to the right part of the vicinity
// as much keys from S as possible
if coMRight != Empty then
    if MDelimR # coMRight != Empty then d := ChooseAny(MDelimR # coMRight);
    else                                d := ChooseMin(coMRight);
    X := LeftOf(S,d);
    <Y₀,y₁,…,y_b-1,Y_b-1> := Compress⁰(RightOf(S,d),r₀,R₀,…,r_b-1,R_b-1);
    for i := 1 to b-1 do
        Replace(FR_i,<R_i>,<Y_i>);
        Replace(Fr_i,<r_i>,<y_i>);
    od
    Replace(FR₀,<R₀>,<Y₀>);
    Replace(Fr₀,<r₀>,<d>);
    Replace(F,<S>,<X>);
    if WW(X) then return F; fi
    S := X;
    MakeVicinity(S);
    ComputeSets(S);
fi

// Split:
// Even after moving out of S all keys that fit into the other nodes
// of the vicinity S is still too large, and
// need to be split into two nodes
if MDelim != Empty then d := ChooseAny(MDelim);
else                    d := ChooseMax(MDelimR);
X := LeftOf(S,d);
Y := RightOf(S,d);
Replace(F,<S>,<X,d,Y>);
if WW(Y) then return F; fi

// Recursion:
// Even after splitting off a node X the remaining part Y is still
// too large, Balance_W() will be applied to Y again
F := Balance_W(Y);
return F;
EndProcedure

Procedure Balance_B(S)
MakeVicinity(S);

// First Compression:
// Check which of the first b sweeps of the vicinity is
// compressible, and compress the first found
for m := 0 to b-1 do
    if ! IC(Sweep_b^m(S)) then break; fi
od

if m < b then // a compressible sweep is found, compress it
    <X_b-m-1,x_b-m-1,…,x₁,X₀,y₀,Y₀,y₁,…,y_m-1,Y_m-1> := Compress^b-m(Sweep_b^m(S));
    for i := 1 to b-m-1 do
        Replace(FL_i,<L_i>,<X_i>);
        Replace(Fl_i,<l_i>,<x_i>);
    od
    for i := 0 to m-1 do
        Replace(FR_i,<R_i>,<Y_i>);
        Replace(Fr_i,<r_i>,<y_i>);
    od
    if FL₀ = F then
        Replace(F,<L₀,l₀,S>,<X₀>);
    else
        Replace(F,<S>,<X₀>);
        Replace(Fl₀,<l₀>,<x₁>);
        Replace(FL₀,<X₁,x₁,L₀>,<X₁>);
    fi
    m := m + 1;
    S := X₁;
    MakeVicinity(S);
fi

// Second Compression:
// Among the remaining sweeps of the vicinity check which one is
// compressible, and compress the first found
for m := m to b do
    if ! IC(Sweep_b^m(S)) then break; fi
od

if m > b then return F; fi
// A compressible sweep is found, compress it
<X_b-m-1,x_b-m-1,…,x₁,X₀,y₀,Y₀,y₁,…,y_m-1,Y_m-1> := Compress^b-m(Sweep_b^m(S));
for i := 0 to b-m-1 do
    Replace(FL_i,<L_i>,<X_i>);
    Replace(Fl_i,<l_i>,<x_i>);
od
for i := 1 to m-1 do
    Replace(FR_i,<R_i>,<Y_i>);
    Replace(Fr_i,<r_i>,<y_i>);
od
if FR₀ = F then
    Replace(F,<S,r₀,R₀>,<Y₀>);
else
    Replace(F,<S>,<Y₀>);
    Replace(Fr₀,<r₀>,<y₁>);
    Replace(FR₀,<R₀,y₁,Y₁>,<Y₁>);
fi
// It is proven that not more than 2 nodes of the vicinity
// can be shrunken
return F;
EndProcedure