Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-01
2002-02-12
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06347318
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a method, system, and apparatus for improving performance of a program executing on a computer system. More particularly the present invention improves the balance determined by an ordering of information stored in a tree-based data structure on a computer and thereby reduces the time required to search, update, or perform other common operations on the tree-based data structure on a computer system.
BACKGROUND OF THE INVENTION
Typically a tree-based data structure is used to store information in a computer system. It will be appreciated that the term “tree-based data structure” as used herein represents connected information that includes “nodes” that are individual units of information and that include at least one value. Further, the connection of the nodes may represent a hierarchy in which the value of a node may be equal to, greater than, or less than another node. One implementation of a tree-based data structure, typically called a Binary Tree, represents the descendant nodes of a parent node having a value that is less than or equal to the parent node as left nodes, and the descendant nodes having a value greater than the parent node as right nodes. One form of the Binary Tree, typically called a Cartesian Tree, represents the descendant nodes of a parent node being associated with a second value less than or equal to the second value associated with the parent node. The terms “tree” and “tree-based data structure” will be used interchangeably herein.
Inserting a new node into an existing tree-based data structure may include the following operations. Initially, a search is conducted starting at the initial, or root, node and traversing down the tree until the correct position for insertion is located. At each node a direction, or branch, is followed depending on whether the new node value is equal to, less than, or greater than the existing node value. Then a proper location for insertion is determined based on the properties of the tree, such as the properties of a Binary Tree or a Cartesian Tree, and the relationship of the two nodes.
A problem with trees of the past, such as Binary Trees, is that nodes associated with equivalent values have not been specially handled by operations that manage a tree. It will be appreciated that the information stored in the tree-based data structure may be catalogued by reference to a value, typically called a key, and the key may be identical to other keys associated with the tree-based data structure. Therefore, since the operation of inserting a node in a tree proceeds to the same branch when the value associated with the new node is equal to the value associated with an existing node, the insertion of many new nodes will be on the same branch thereby leading to an imbalanced tree. It will be appreciated that an imbalanced tree has a preponderance of the nodes placed on the same branch of the tree.
Another problem with trees of the past, such as Cartesian Trees, occurs when the values associated with the nodes in a tree progress in a patterned order, since the related information in the tree will be imbalanced. For instance, when the values associated with the nodes progress sequentially, the representative node will generally be placed on the same branch of the tree as the previous node thus creating an imbalanced tree.
An important characteristic of a tree is that it enables quick searches of the nodes on the tree. Therefore, if the tree is imbalanced the tree may be considered a degenerate tree. The degenerate tree is characterized by a long search path, similar to a linked list, and information is reached by traversal of the nodes via the long search path. Those skilled in the art will appreciate the use of a linked list.
The operations of the past that operate to manage a tree by compact solutions do not efficiently manage the occurrence of equal keys that are associated with nodes or the occurrence of keys that are associated with nodes in a patterned order. Therefore, the resulting tree is degenerate and does not enable quick searching, updating, or performing other related operations on the tree. Also operations of the past may efficiently balance a tree but require expensive inefficient solutions to manage the tree.
SUMMARY OF THE INVENTION
The present invention is a method, system, and apparatus for improving performance of a program executing on a computer system. More particularly the present invention improves the balance determined by an ordering of information stored in a tree-based data structure on a computer by a compact solution thereby reducing the time required to search, update, or perform other common operations on the tree-based data structure.
The present invention specially handles operations that manage a tree to ensure that the tree is balanced. More particularly, when the key associated with a new node is equal to the key associated with another node in the tree, the present invention manages the operation of inserting the new node in a tree such that the tree is balanced. Further, when the values associated with the nodes in a tree progress in a patterned order, the present invention specially handles operations that manage a tree to ensure that the nodes in the tree are balanced.
The present invention novelly manages the operations of inserting a node in a tree by specially handling nodes with associated keys that are equal or nodes with associated keys that progress in a pattern. Thereby, the present invention reduces the occurrence of a degenerate tree during the operation of inserting nodes in a tree over tree-related operations in the past, and enables quick searching, updating, or other related operations on the tree. It will be appreciated that patterns associated with keys, such as sequentially progressing keys, may cause a degenerate tree.
The present invention novelly and efficiently compares at least two computer-based values by determining a bit reversal order value of a first value and a second value. The computer system includes computer readable medium that is encoded in a source program that executes on the computer system. Also, the computer system supports two's complement execution of the source program, a logical XOR operation, and a logical AND operation, subtraction, and negation.
In one embodiment of the present invention a third value is assigned the result of executing logical XOR on the first value and the second value. Further, a fourth value is assigned the result of executing negation on the third value. In an alternative embodiment the third value is assigned the result of subtracting the second value from the first value; and the fourth value is assigned the result of subtracting the first value from the second value.
Then in either embodiment of the present invention, a fifth value is assigned a result of executing logical AND on the third value and the fourth value. Further, a bit reversal order value is assigned the result of executing logical AND on the fifth value and the second value, and if the bit reversal order value is not zero then the reverse of the second value is greater than the reverse of the first value thereby ordering the first value and the second value.
Accordingly, it is an object of the invention to balance the placement of nodes on a tree when the keys associated with the nodes are equal or when the keys associated with the nodes progress in a pattern. More particularly the present invention introduces a tie-breaking operation during the insertion of a node in a tree. The tie-breaking operation may be based on information that is associated with the node or associated with the location of the node.
Also, it is an object of the invention to improve the efficiency of searching, updating, and other associated operations of a node in a tree by using a bit reversal value or bit reversed address associated with the node to balance the tree. Typically, computer-based information is represented by bits in a computer system. A bit is a basic unit used to store information in a compu
No associations
LandOfFree
Method, system, and apparatus to improve performance of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and apparatus to improve performance of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and apparatus to improve performance of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2975878