US 6,675,157 B1 · System and method for balancing binary search trees

Abstract

An improved binary search tree (BST) balancing facility balances BSTs by copying pointers to the nodes of a BST into a pointer list in accordance with a sequential order of respective data values of the nodes. The balancing facility then builds a balanced BST based on a first index to a first pointer of the pointer list and a second index to a last pointer of the pointer list. In an illustrative embodiment, the balanced BST is built by identifying a central pointer at a midpoint of the pointer list, a left range of pointers before the midpoint, and a right range of pointers after the midpoint. The central pointer is then interpreted as a pointer to a root node, and a balanced left subtree of the root node and a balanced right subtree of the root node are built based on the left range of pointers and the right range of pointers, respectively.

Claims21

Dependent claims

A data processing system with facilities for obtaining a balanced binary search tree to optimize searches, said data processing system comprising:

a memory and a processor in communication with said memory;
a collection of at least three nodes and a respective pointer to each node within said collection stored in said memory;
an extraction facility that copies said pointers into a pointer list in accordance with a sequential order of respective data values of said at least three nodes;
and
a tree builder that builds a balanced binary search tree based on a first index to a first pointer of said pointer list and a second index to a last pointer of said pointer list to determine a root node of said balanced binary search tree.

2 more elements

A program product for obtaining a balanced binary search tree to optimize searches in a data processing system containing a collection of at least three nodes and a respective pointer to each node within said collection, said program product comprising:

an extraction facility that copies said pointers into a pointer list in accordance with a sequential order of respective data values of said at least three nodes;
a tree builder that builds a balanced binary search tree based on a first index to a first pointer of said pointer list and a second index to a last pointer of said pointer list to determine a root node of said balanced binary search tree;
and
a computer usable medium encoding said extraction facility and said tree builder.

1 more element

Dependencies are inferred from the claim text.

System and method for balancing binary search trees

Life of this patent

System and method for balancing binary search trees

Life of this patent

Abstract

Claims21