US 8,078,642 B1Granted

Concurrent traversal of multiple binary trees

AssigneeYahoo! Inc.

InventorTomi Poutanen

Life of this patent

Estimating the term…

Loading patent…

Abstract

In one embodiment, a tree traversal sequentially processes every level of two or more binary trees until reaching a leaf node for each the binary trees. Processing each level of the binary trees comprises: determining whether each traversed node of the remaining binary trees at the level is a non-leaf node or a leaf node; for the traversed leaf nodes at the level, remove the binary trees to which the leaf nodes belong from the remaining binary trees; and iteratively evaluating the traversed non-leaf nodes at the level of every n remaining binary trees until the non-leaf nodes at the level of all of the remaining binary trees are evaluated, where n≧2 and evaluating the non-leaf nodes of each n binary trees comprises concurrently evaluating the n non-leaf nodes of the n binary trees to determine to which one of the two child nodes of each of the n non-leaf nodes to traverse.

Claims50

Dependent claims

A method comprising:

accessing, by one or more computer systems, m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one or more non-leaf nodes, two or
more leaf nodes, and one or more levels,
the non-leaf nodes of each of the m binary trees comprising one root node
and zero or more intermediate nodes,
for each of the m binary trees, the non-leaf nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, and the levels each comprising one or more of the non-leaf or leaf nodes;
and
sequentially processing, by the one or more computer systems, every one of the levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the levels of the m binary trees comprising:
determining whether one or more traversed nodes of one or more remaining of the m binary trees at the level are each a non-leaf node or a leaf node,
the remaining binary trees each having one of its non-leaf or leaf nodes at the level as one of the traversed nodes,
the traversed nodes at the level each being the root node of one of the m binary trees or having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the level, removing the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
iteratively evaluating the traversed non-leaf nodes at the level of every n of the remaining binary trees until the non-leaf nodes at the level of all of the remaining binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the traversed non-leaf nodes of each n binary trees comprising concurrently evaluating the n traversed non-leaf nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed non-leaf nodes to traverse.

14 more elements

A method comprising:

accessing, by one or more computer systems, m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one root node, zero or more intermediate nodes, two or more leaf nodes, one root level, and one or more subsequent levels, and
for each of the m binary trees, the root node and the intermediate nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, the root level comprising the root node, and the subsequent levels each comprising one or more of the intermediate or leaf nodes;
processing, by the one or more computer systems, the root level of the m binary trees, comprising iteratively evaluating the root nodes of every n of the m binary trees until the root nodes of all of the m binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the root nodes of each n binary trees comprising concurrently evaluating the n root nodes of the n binary trees to determine to which one of the two child nodes of each of the n root nodes to traverse;
and
sequentially processing, by the one or more computer systems, every one of the subsequent levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the subsequent levels of the m binary trees comprising:
determining whether one or more traversed nodes of one or more remaining of the m binary trees at the subsequent level are each an intermediate node or a leaf node,
the remaining binary trees each having one of its intermediate or leaf nodes at the subsequent level as one of the traversed nodes,
the traversed nodes at the subsequent level each having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the subsequent level, removing the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
iteratively evaluating the traversed intermediate nodes at the subsequent level of every n of the remaining binary trees until the traversed intermediate nodes at the subsequent level of all of the remaining binary trees are evaluated,
evaluating the traversed intermediate nodes of each n binary trees comprising concurrently evaluating the n traversed intermediate nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed intermediate nodes to traverse.

13 more elements

A system comprising:

a memory comprising instructions executable by one or more processors;
and
one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to:
access m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one or more non-leaf nodes,
two or more leaf nodes, and one or more levels,
the non-leaf nodes of each of the m binary trees comprising one root node and zero or more intermediate nodes,
for each of the m binary trees, the non-leaf nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, and the levels each comprising one or more of the non-leaf or leaf nodes;
and
sequentially process every one of the levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the levels of the m binary trees comprising:
determine whether one or more traversed nodes of one or more remaining of the m binary trees at the level are each a non-leaf node or a leaf node,
the remaining binary trees each having one of its non-leaf or leaf nodes at the level as one of the traversed nodes,
the traversed nodes at the level each being the root node of one of the m binary trees or having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the level, remove the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
iteratively evaluate the traversed non-leaf nodes at the level of every n of the remaining binary trees until the non-leaf nodes at the level of all of the remaining binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the traversed non-leaf nodes of each n binary trees comprising concurrently evaluate the n traversed non-leaf nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed non-leaf nodes to traverse.

16 more elements

A system comprising:

a memory comprising instructions executable by one or more processors;
and
one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to:
access m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one root node, zero or more intermediate nodes, two or more leaf nodes, one root level, and one or more subsequent levels, and
for each of the m binary trees, the root node and the intermediate nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, the root level comprising the root node, and the subsequent levels each comprising one or more of the intermediate or leaf nodes;
process the root level of the m binary trees, comprising iteratively evaluate the root nodes of every n of the m binary trees until the root nodes of all of the m binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the root nodes of each n binary trees comprising concurrently evaluate the n root nodes of the n binary trees to determine to which one of the two child nodes of each of the n root nodes to traverse;
and
sequentially process every one of the subsequent levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the subsequent levels of the m binary trees comprising:
determine whether one or more traversed nodes of one or more remaining of the m binary trees at the subsequent level are each an intermediate node or a leaf node,
the remaining binary trees each having one of its intermediate or leaf nodes at the subsequent level as one of the traversed nodes,
the traversed nodes at the subsequent level each having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the subsequent level, remove the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
iteratively evaluate the traversed intermediate nodes at the subsequent level of every n of the remaining binary trees until the traversed intermediate nodes at the subsequent level of all of the remaining binary trees are evaluated,
evaluating the traversed intermediate nodes of each n binary trees comprising concurrently evaluate the n traversed intermediate nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed intermediate nodes to traverse.

16 more elements

One or more computer-readable storage media embodying software operable when executed by one or more computer systems to:

access m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one or more non-leaf nodes, two or more leaf nodes, and one or more levels,
the non-leaf nodes of each of the m binary trees comprising one root node and zero or more intermediate nodes,
for each of the m binary trees, the non-leaf nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, and
the levels each comprising one or more of the non-leaf or leaf nodes;
and
sequentially process every one of the levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the levels of the m binary trees comprising:
determine whether one or more traversed nodes of one or more remaining of the m binary trees at the level are each a non-leaf node or a leaf node,
the remaining binary trees each having one of its non-leaf or leaf nodes at the level as one of the traversed nodes,
the traversed nodes at the level each being the root node of one of the m binary trees or having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the level, remove the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
iteratively evaluate the traversed non-leaf nodes at the level of every n of the remaining binary trees until the non-leaf nodes at the level of all of the remaining binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the traversed non-leaf nodes of each n binary trees comprising concurrently evaluate the n traversed non-leaf nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed non-leaf nodes to traverse.

13 more elements

A One or more computer-readable storage media embodying software operable when executed by one or more computer systems to:

access m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one root node, zero or more intermediate nodes, two or more leaf nodes, one root level, and one or more subsequent levels, and
for each of the m binary trees, the root node and the intermediate nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, the root level comprising the root node, and the subsequent levels each comprising one or more of the intermediate or leaf nodes;
process the root level of the m binary trees, comprising iteratively evaluate the root nodes of every n of the m binary trees until the root nodes of all of the m binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the root nodes of each n binary trees comprising concurrently evaluate the n root nodes of the n binary trees to determine to which one of the two child nodes of each of the n root nodes to traverse;
and
sequentially process every one of the subsequent levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the subsequent levels of the m binary trees comprising:
determine whether one or more traversed nodes of one or more remaining of the m binary trees at the subsequent level are each an intermediate node or a leaf node,
the remaining binary trees each having one of its intermediate or leaf nodes at the subsequent level as one of the traversed nodes,
the traversed nodes at the subsequent level each having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the subsequent level, remove the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
iteratively evaluate the traversed intermediate nodes at the subsequent level of every n of the remaining binary trees until the traversed intermediate nodes at the subsequent level of all of the remaining binary trees are evaluated,
evaluating the traversed intermediate nodes of each n binary trees comprising concurrently evaluate the n traversed intermediate nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed intermediate nodes to traverse.

13 more elements

A system comprising:

means for accessing m binary trees,
m denoting an integer greater than or equal to 2,
the m binary trees each comprising one root node, zero or more intermediate nodes, two or more leaf nodes, one root level, and one or more subsequent levels, and
for each of the m binary trees, the root node and the intermediate nodes each having two child nodes, the intermediate nodes and the leaf nodes each having one parent node, the root level comprising the root node, and the subsequent levels each comprising one or more of the intermediate or leaf nodes;
means for processing the root level of the m binary trees, comprising means for iteratively evaluating the root nodes of every n of the m binary trees until the root nodes of all of the m binary trees are evaluated,
n denoting an integer greater than or equal to 2,
evaluating the root nodes of each n binary trees comprising means for concurrently evaluating the n root nodes of the n binary trees to determine to which one of the two child nodes of each of the n root nodes to traverse;
and
means for sequentially processing every one of the subsequent levels of the m binary trees until reaching a leaf node for each the m binary trees, processing each one of the subsequent levels of the m binary trees comprising:
means for determining whether one or more traversed nodes of one or more remaining of the m binary trees at the subsequent level are each an intermediate node or a leaf node,
the remaining binary trees each having one of its intermediate or leaf nodes at the subsequent level as one of the traversed nodes,
the traversed nodes at the subsequent level each having been determined as a result of evaluating its parent node;
for the traversed leaf nodes at the subsequent level, means for removing the binary trees to which the traversed leaf nodes belong from the remaining binary trees;
and
means for iteratively evaluating the traversed intermediate nodes at the subsequent level of every n of the remaining binary trees until the traversed intermediate nodes at the subsequent level of all of the remaining binary trees are evaluated,
evaluating the traversed intermediate nodes of each n binary trees comprising concurrently means for evaluating the n traversed intermediate nodes of the n binary trees to determine to which one of the two child nodes of each of the n traversed intermediate nodes to traverse.

13 more elements

Dependencies are inferred from the claim text.