Parent and childs of a full d-node tree

Question

i have a full d-node tree (by that mean a tree that each node has exactly d nodes as kids). My question is, if i get a random k node of this tree, in which position do i get his kids and his parent?

For example, if i have a full binary tree, the positions that i can find the parent,left and right kid of the k node are $\dfrac k2, 2k, 2k+1$ respectively.

Thanks in advance.

Answer 1

Start by labeling your $k$-ary tree with the root as $0$, and continue in a breath-first-search pattern.

1. Given a node $n$, with index $n\text{.i}$, $n$'s children have indices: $$\{(n\text{.i})k+1,\, (n\text{.i})k+1,\, \ldots,\, (n\text{.i})k + k\}$$

2. We can also see that given a node $n$ with index $n\text{.i}\gt0$, we can find the index of the parent by the formula: $$p\text{.i}=\left\lfloor\frac{n\text{.i} - 1}{k}\right\rfloor$$

I haven't proved these, but these formulas appear to be correct based on several different drawings.

Answer 2

It looks like you're starting numbering at 1 for the root, and numbering "left to right" on each level/depth.

If the root has depth $0$, then there are $d^{t}$ nodes with depth $t$ from the root in a full $d$-dimensional tree. Also, the depth of node $k$ is $\ell_{k}=\lceil\log_{d}(k-1)\rceil$.

The number of nodes at depths below the depth of node $k$, then, is $$n_{k} = \sum_{i = 0}^{\ell_{k-1}}d^{i} = \frac{d^{\ell_{k}}-1}{d-1}.$$ So indexing on the row containing node $k$ starts at $n_{k}+1$.

Children of node $k$:

The position of $k$ in its row is just $p_{k}=k-n_{k}$. The children of node $k$ have depth one more than that of $k$, and in their respective row, the first child $c$ has position $d(p_{k}-1)+1=d(k-n_{k}-1)+1$, so the $j^{th}$ child of $k$ has position $$j + \sum_{i = 0}^{\ell_{k}+1}d^{i} + d(k-\sum_{i = 0}^{\ell_{k}}d^{i}-1) = j + \frac{d^{\ell_{k}+1}-1}{d-1} + d(k-\frac{d^{\ell_{k}}-1}{d-1}-1)$$ $$=j +dk-d +1$$

Parent of node $k$:

Since this formula applies for the parent $p$ of $k$, for $1 \leq j \leq d$ $$1+dp-d +1\leq k \leq d+dp - d + 1 = dp+1$$ $$\Rightarrow dp - d \leq k-1 \leq dp$$ $$\Rightarrow p-1 \leq \frac{k-1}{d} \leq p$$ so $p = \lceil\frac{k-1}{d}\rceil$.

Answer 3

If you use zero-based indexing, so that the root is position $0$, then the last node in level $\ell$ of the tree has index $\sum_{i=1}^\ell d^i=\frac{d(d^\ell-1)}{d-1}$. Thus, node $k$ is in level $\ell$ iff

$$\frac{d}{d-1}(d^{\ell-1}-1)<k\le\frac{d}{d-1}(d^\ell-1)\;,$$

or

$$d^{\ell-1}<k\left(1-\frac1d\right)+1\le d^\ell\;,$$

i.e.,

$$\ell=\left\lceil\log_d\left(k\left(1-\frac1d\right)+1\right)\right\rceil\;.$$

Let

$$\ell(k)=\left\lceil\log_d\left(k\left(1-\frac1d\right)+1\right)\right\rceil\;,$$

the level of node $k$. Node $k$ has

$$k-\frac{d(d^{\ell-1}-1)}{d-1}-1$$

predecessors in level $\ell(k)$, each of which has $d$ offspring, so its $d$ offspring have indices from

$$\frac{d(d^\ell-1)}{d-1}+d\left(k-\frac{d(d^{\ell-1}-1)}{d-1}-1\right)+1=dk+1$$

through $dk+d=d(k+1)$.

Now assume that $k>0$, and node $m$ is the parent of node $k$. Then

$$dm+1\le k\le d(m+1)\;,$$

so

$$m+\frac1d\le\frac{k}d\le m+1\;,$$

and therefore $$\left\lceil\frac{k}d\right\rceil=m+1\;,$$

i.e.,

$$m=\left\lceil\frac{k}d\right\rceil-1\;.$$