Browse Prior Art Database

# Method for a distributed n-nary tree structure and search algorithm for data in a known range

IP.com Disclosure Number: IPCOM000146560D
Publication Date: 2007-Feb-16
Document File: 8 page(s) / 92K

## Publishing Venue

The IP.com Prior Art Database

## Abstract

Disclosed is a method for a distributed n-nary tree structure and search algorithm for data in a known range. Benefits include improved functionality and improved performance.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 38% of the total text.

Method for a distributed n-nary tree structure and search algorithm for data in a known range

Disclosed is a method for a distributed n-nary tree structure and search algorithm for data in a  known range. Benefits include improved functionality and improved performance.

Background

A conventional n-nary tree contains a stem and branches. For example, a binary tree can have a data range of 0 – 999. Data entries include the following values (see Figure 1):

300, 20, 100, 500, 250, 10, 30, 800, 600, 330, 550, 60, 900, 80, 850

The depth of the tree is 6. Reaching a node requires the following number of steps:

•     Node 10 takes 2 steps

•     Node 80 takes 5 steps

•     Node 550 takes 4 steps

•     Node 850 takes 4 steps

Adding two new nodes, 15 and 700, requires 3 steps and 4 steps, respectively.

A balanced tree has a total number of number of nodes represented by the following equation:
m = rangemax - rangemin +1

The original depth of a conventional tree is represented by the following equation:

dorg = logn (m+1)

For a binary tree, the value of n is 2.

For a balanced tree with a data range from 1 to 15, the total nodes is (see Figure 2):

m = 15 – 1 + 1 = 15

As a result, the depth is:

dorg = log2 (15 + 1) = 4

For a left/right biased tree with a data range of 1 to 15, the total nodes is (see Figure 3):

m = 15 – 1 + 1 = 15

The original depth is:

dorg =  m = 15

General description

The disclosed method is a distributed n-nary tree structure and search algorithm for data in known ranges. The method is a generic concept that can be applied for any related field/product regardless of the software or hardware implementation. The method speeds up the data manipulation process and enables some degree of parallel processing. The method can be applied to functions such as database management, simulation, and routing path calculation.