of the current node then continue search in its right subtree. Search fails if there is no right subtree. Insertion Search for a bounding node for the new value. If such a node exists then: check whether there is still space in its data array, if so then insert the new value and finish if no space is available then remove the minimum value from the node's data array and insert the new value. Now proceed to the node holding the greatest lower bound for the node that the new value was inserted to. If the removed minimum value still fits in there then add it as the new maximum value of the node, else create a new right subnode for this node. If no bounding node was found then insert the value into the last node searched if it still fits into it. In this case the new value will either become the new minimum or maximum value. If the value doesn't fit anymore then create a new left or right subtree. If a new node was added then the tree might need to be rebalanced, as described below. Deletion Search for bounding node of the value to be deleted. If no bounding node is found then finish. If the bounding node does not contain the value then finish. delete the value from the node's data array Now we have to distinguish by node type: Internal node: If the node's data array now has less than the minimum number of elements then move the greatest lower bound value of this node to its data value. Proceed with one of the following two steps for the half leaf or leaf node the value was removed from. Leaf node: If this was the only element in the data array then delete the node. Rebalance the tree if needed. Half leaf node: If the node's data array can be merged with its leaf's data array without overflow then do so and remove the leaf node. Rebalance the tree if needed. Rotation and balancing A T-tree is implemented on top of an underlying self-balancing binary search tree. Specifically, Lehman and Carey's article describes a T-tree balanced like an AVL tree: it becomes out of balance when a node's child trees differ in height by at least two levels. This can happen after an insertion or deletion of a node. After an insertion or