Skip to content

Commit 82fa2ec

Browse files
authored
s-tree.md: fix index formula
The code below is correct, the math was off.
1 parent 080f12e commit 82fa2ec

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

‎content/english/hpc/data-structures/s-tree.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@ Storing and fetching pointers in a B-tree node wastes precious cache space and d
4848
One of the ways to achieve this is by generalizing the [Eytzinger numeration](../binary-search#eytzinger-layout) to $(B + 1)$-ary trees:
4949

5050
- The root node is numbered $0$.
51-
- Node $k$ has $(B + 1)$ child nodes numbered $\\{k \cdot (B+1) + i\\}$ for $i \in [1, B]$.
51+
- Node $k$ has $(B + 1)$ child nodes numbered $\\{k \cdot (B+1) + i + 1\\}$ for $i \in [0, B]$.
5252

5353
This way, we can only use $O(1)$ additional memory by allocating one large two-dimensional array of keys and relying on index arithmetic to locate children nodes in the tree:
5454

0 commit comments

Comments
 (0)