Patent ID: 7447698

Claim:
A computer implemented method for balancing a binary search tree, comprising: locating a node in a binary search tree to form a located node; determining whether a depth of the located node is greater than a threshold, wherein determining whether the depth of the located node is greater than the threshold comprises determining by how much the depth of the located node is greater than an ideal maximum depth of a perfectly balanced binary tree, and wherein determining by how much the depth of the located node is greater than the ideal maximum depth of the perfectly balanced binary tree comprises determining whether the depth of the located node is at least a desired amount greater than an ideal maximum depth of a reasonably balanced binary tree; and performing a modified semi-splay balancing operation if the depth of the located node is greater than the threshold, wherein performing a modified semi-splay balancing operation further comprises: responsive to a parent of the located node not being a root of the binary search tree, a right child of the parent being a NULL, and a right child of a grandparent of the located node not being a NULL, rotating the binary search tree on the parent and promoting the grandparent; and responsive to a left child of a parent of the located node being a NULL and a left child of a grandparent of the located node not being a NULL, rotating the binary search tree on the parent and promoting the grandparent.