value(T) is unspecified. As given, an insert will have no effect. The implementor may desire different behavior. Perform skew and then split. The conditionals that determine whether or not a rotation will occur or not are inside of the procedures, as given above. T := skew(T) T := split(T) return T end function Deletion As in most balanced binary trees, the deletion of an internal node can be turned into the deletion of a leaf node by swapping the internal node with either its closest predecessor or successor, depending on which are in the tree or on the implementor's whims. Retrieving a predecessor is simply a matter of following one left link and then all of the remaining right links. Similarly, the successor can be found by going right once and left until a null pointer is found. Because of the AA property of all nodes of level greater than one having two children, the successor or predecessor node will be in level 1, making their removal trivial. To re-balance a tree, there are a few approaches. The one described by Andersson in his original paper is the simplest, and it is described here, although actual implementations may opt for a more optimized approach. After a removal, the first step to maintaining tree validity is to lower the level of any nodes whose children are two levels below them, or who are missing children. Then, the entire level must be skewed and split. This approach was favored, because when laid down conceptually, it has three easily understood separate steps: Decrease the level, if appropriate. Skew the level. Split the level. However, we have to skew and split the entire level this time instead of just a node, complicating our code. function delete is input: X, the value to delete, and T, the root of the tree from which it should be deleted. output: T, balanced, without the value X. if nil(T) then return T else if X > value(T) then right(T) := delete(X, right(T)) else if X < value(T) then left(T) := delete(X, left(T)) else If we're a leaf, easy, otherwise reduce to leaf case. if leaf(T) then return right(T) else if nil(left(T)) then L := successor(T) right(T) := delete(value(L), right(T)) value(T) := value(L) else L := predecessor(T) left(T) := delete(value(L), left(T)) value(T) := value(L) end if end if Rebalance the tree. Decrease the level of all nodes in this