Storage of tree data structures
Disclosed herein is a computer-implemented method for storing binary tree data in memory. The binary tree data comprises parent node data, first child node data and second child node data. The computer-implemented method comprises determining a first child node memory address, the first child node memory address being less than a parent node memory address; determining a second child node memory address, the second child node memory address being greater than the parent node memory address; storing the parent node data at the parent node memory address; storing the first child node data at the first child node memory address; and storing the second child node data at the second child node memory address.
1. A computer-implemented method for storing binary tree data in a random access memory comprised of memory cells associated with corresponding memory addresses, wherein the binary tree data comprises parent node data, first child node data and second child node data, the computer-implemented method comprising:
determining a first child node memory address using a processor to execute a memory assignment function based on a first node position vector for a first child node, the first child node memory address being less than a parent node memory address;
determining a second child node memory address using the processor to execute the memory assignment function based on a second node position vector for a second child node, the second child node memory address being greater than the parent node memory address;
storing the parent node data in at least one memory cell at the parent node memory address;
storing the first child node data in at least one memory cell at the first child node memory address; and
storing the second child node data in at least one memory cell at the second child node memory address, wherein the first node position vector and the second node position vector are each represented by [i 1 , i 2 , . . . , i k−1 , i k ], where:
i 1 is a layer position of a direct relative of that node in a first layer of the binary tree;
i 2 is a layer position of a direct relative of that node in a second layer of the binary tree;
i k−1 is a layer position of a parent node; and
i k is a layer position of that node.
2. The computer-implemented method of claim 1 , further comprising determining the parent node memory address using the processor to execute the memory assignment function.
3. The computer-implemented method of claim 1 , wherein:
storing the parent node data at the parent node memory address comprises storing a part of the parent node data at the parent node memory address,
storing the first child node data at the first child node memory address comprises storing a part of the first child node data at the first child node memory address, and
storing the second child node data at the second child node memory address comprises storing a part of the second child node data at the second child node memory address.
4. The computer-implemented method of claim 1 , wherein:
the parent node data comprises data associated with a first level of a binary tree,
the first child node data comprises data associated with a second level of the binary tree, and
the second child node data comprises data associated with the second level of the binary tree.
5. The computer-implemented method of claim 1 , wherein:
storing the parent node data at the parent node memory address is performed before storing the first child node data at the first child node memory address, and
storing the parent node data at the parent node memory address is performed before storing the second child node data at the second child node memory address.
6. The computer-implemented method of claim 1 , wherein:
storing the first child node data at the first child node memory address is performed before storing the parent node data at the parent node memory address, and
storing the first child node data at the first child node memory address is performed before storing the second child node data at the second child node memory address.
7. The computer-implemented method of claim 1 , wherein:
storing the second child node data at the second child node memory address is performed before storing the parent node data at the parent node memory address, and
storing the second child node data at the second child node memory address is performed before storing the first child node data at the first child node memory address.
8. The computer-implemented method of claim 1 , wherein the binary tree data comprises first child tree data comprising at least the first child node data, and second child tree data comprising at least the second child node data, the computer-implemented method further comprising:
storing the first child tree data at memory addresses within a range of first tree memory addresses that comprises the first child node memory address, the memory addresses of the range of first tree memory addresses being less than the parent node memory address; and
storing the second child tree data at memory addresses within a range of second tree memory addresses that comprises the second child node memory address, the memory addresses of the range of second tree memory addresses being greater than the parent node memory address.
9. The computer-implemented method of claim 1 , wherein the memory assignment function is configured to determine a target node memory address indicator bt([i 1 , i 2 , . . . , i k−1 , i k ]) by calculating:
b
t
(
[
i
1
,
i
2
,
…
,
i
k
-
1
,
i
k
]
)
=
-
1
-
∑
j
=
0
k
(
-
1
)
i
j
2
d
-
j
where:
i 0 =1; and
d is a depth indicator that is indicative of a depth of the binary tree.
10. The computer-implemented method of claim 1 , further comprising:
storing the parent node data at a range of parent node memory addresses that comprises the parent node memory address;
storing the first child node data at a range of first child node memory addresses that comprises the first child node memory address; and
storing the second child node data at a range of second child node memory addresses that comprises the second child node memory address.
11. The computer-implemented method of claim 10 , wherein
memory addresses of the range of first child node memory addresses are less than memory addresses of the range of parent node memory addresses, and
memory addresses of the range of second child node memory addresses are greater than memory addresses of the range of parent node memory addresses.
12. The computer-implemented method of claim 10 , wherein:
the range of first child node memory addresses and the range of parent node memory addresses form a first consecutive range of memory addresses; and
the range of parent node memory addresses and the range of second child node memory addresses form a second consecutive range of memory addresses.
13. An apparatus for storing binary tree data, the apparatus comprising:
a random access memory comprised of memory cells associated with corresponding memory addresses, wherein the binary tree data comprises parent node data, first child node data and second child node data; and
a processor configured to:
determine, using a memory assignment function and based on a first node position vector for a first child node, a first child node memory address, the first child node memory address being less than a parent node memory address;
determine, using the memory assignment function and based on a second node position vector for a second child node, a second child node memory address, the second child node memory address being greater than the parent node memory address;
store the parent node data in at least one memory cell at the parent node memory address;
store the first child node data in at least one memory cell at the first child node memory address; and
store the second child node data in at least one memory cell at the second child node memory address, wherein the first node position vector and the second node position vector are each represented by [i 1 , i 2 , . . . , i k−1 , i k ], where:
i 1 is a layer position of a direct relative of that node in a first layer of the binary tree;
i 2 is a layer position of a direct relative of that node in a second layer of the binary tree;
i k−1 is a layer position of a parent node; and
i k is a layer position of that node.
14. An apparatus for storing binary tree data, the apparatus comprising:
a random access memory comprised of memory cells associated with corresponding memory addresses, wherein the binary tree data comprising parent node data, first child node data and second child node data;
means for determining, using a memory assignment function and based on a first node position vector for a first child node, a first child node memory address, the first child node memory address being less than a parent node memory address;
means for determining, using the memory assignment function and based on a second node position vector for a second child node, a second child node memory address, the second child node memory address being greater than the parent node memory address;
means for storing the parent node data in at least one memory cell at the parent node memory address;
means for storing the first child node data in at least one memory cell at the first child node memory address; and
means for storing the second child node data in at least one memory cell at the second child node memory address, wherein the first node position vector and the second node position vector are each represented by [i 1 , i 2 , . . . , i k−1 , i k ], where:
i 1 is a layer position of a direct relative of that node in a first layer of the binary tree;
i 2 is a layer position of a direct relative of that node in a second layer of the binary tree;
i k−1 is a layer position of a parent node; and
i k is a layer position of that node.
15. The apparatus of claim 13 , wherein the memory assignment function is configured to determine a node memory address indicator bt([i 1 , i 2 , i k−1 , i k ]) by calculating:
b
t
(
[
i
1
,
i
2
,
…
,
i
k
-
1
,
i
k
]
)
=
-
1
-
∑
j
=
0
k
(
-
1
)
i
j
2
d
-
j
where:
i 0 =1; and
d is a depth indicator that is indicative of a depth of the binary tree.
16. The apparatus of claim 13 , wherein:
the parent node data comprises data associated with a first level of a binary tree,
the first child node data comprises data associated with a second level of the binary tree, and
the second child node data comprises data associated with the second level of the binary tree.
17. The apparatus of claim 13 , wherein:
the parent node data is stored at a range of parent node memory addresses that comprises the parent node memory address,
the first child node data is stored at a range of first child node memory addresses that comprises the first child node memory address, and
the second child node data is stored at a range of second child node memory addresses that comprises the second child node memory address.
18. The apparatus of claim 17 , wherein
memory addresses of the range of first child node memory addresses are less than memory addresses of the range of parent node memory addresses, and
memory addresses of the range of second child node memory addresses are greater than memory addresses of the range of parent node memory addresses.
19. The apparatus of claim 17 , wherein:
the range of first child node memory addresses and the range of parent node memory addresses form a first consecutive range of memory addresses; and
the range of parent node memory addresses and the range of second child node memory addresses form a second consecutive range of memory addresses.
20. The apparatus of claim 13 , wherein:
storing the parent node data at the parent node memory address comprises storing a part of the parent node data at the parent node memory address;
storing the first child node data at the first child node memory address comprises storing a part of the first child node data at the first child node memory address; and
storing the second child node data at the second child node memory address comprises storing a part of the second child node data at the second child node memory address.