BinaryTreeParentArrays
The binary trees with nodes, each as its in-order parent array.
BinaryTreeParentArrays(n)the binary trees with nodes, as parent arraysTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<binary_tree_parent_array> | combinatorics | always |
Details
- Number the nodes in order; entry is the number of the -th node's parent, at the root. A node numbered below its parent is its left child, above it its right.
- Listed in BinaryTrees' order: BinaryTreeParentArray of the -th tree is the -th array.
- A binary search tree's values are its in-order numbers, so BinarySearchTreeParentArray lands here.
Definition
Epsil, as the implementation runs it.
count(_n)
0 if _n < 0 else _tables[_n + 1]unrank(_n, _r)
Apply(
(ufinal: list<integer>) => Map(
Function(ufinal[uv + 1], uv),
Range(1, _n, 1),
),
Apply(
(us_init: list<integer>) => Fold((us: list<integer>, uk) => Apply(
(us_next: list<integer>) => us_next,
Apply((ut: integer) => Apply((ulo: integer) => Apply(
(usz: integer) => Apply((upar: integer) => Apply(
(ufound: list<integer>) => Apply((ui: integer) => Apply((uright: integer) => Apply((ucr: integer) => ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(us, 1, ut - 1 +
(1 if 0 < ui else 0) +
(1 if 0 < uright else 0)), ulo + ui + 1, upar), _n + 1 +
4 *
(ut - 1) +
1, ulo),
_n + 1 +
4 *
(ut - 1) +
2,
ui,
), _n + 1 +
4 *
(ut - 1) +
3, ulo + ui), _n + 1 +
4 *
(ut - 1) +
4, (ufound[1] -
ufound[1] % ucr) /
ucr),
_n + 1 +
4 *
(ut +
(1 if 0 < ui else 0) -
1) +
1,
ulo + ui + 1,
), _n + 1 +
4 *
(ut +
(1 if 0 < ui else 0) -
1) +
2, uright), _n + 1 +
4 *
(ut +
(1 if 0 < ui else 0) -
1) +
3, ulo + ui),
_n + 1 +
4 *
(ut +
(1 if 0 < ui else 0) -
1) +
4,
ufound[1] % ucr,
), _tables[usz - 1 -
ufound[2] +
1]), usz - 1 -
ufound[2]), ufound[2]),
Apply(
(uf_init: list<integer>) => Fold((uf: list<integer>, uj) => Apply(
(uf_next: list<integer>) => uf_next,
uf if uf[3] == 1 else [uf[1], uj, 1] if uf[1] <
_tables[uj + 1] *
_tables[usz - 1 -
uj +
1] else [uf[1] -
_tables[uj + 1] *
_tables[usz - 1 -
uj +
1], uj, 0],
), uf_init, Range(0, usz - 1, 1)),
[us[_n + 1 +
4 *
(ut - 1) +
4], 0, 0],
),
), us[_n + 1 +
4 *
(ut - 1) +
3]),
us[_n + 1 +
4 *
(ut - 1) +
2],
), us[_n + 1 +
4 *
(ut - 1) +
1]), us[1]),
), us_init, Range(1, _n, 1)),
Join(
[1],
Map(Function(0, pz), Range(1, _n, 1)),
[1, _n, 0, _r],
Map(Function(0, pz), Range(1, 4 * (_n + 1), 1)),
),
),
)rank(_n, _x)
Apply(
(rs_init: list<integer>) => Fold((rs: list<integer>, rk) => Apply(
(rs_next: list<integer>) => rs_next,
Apply((rt: integer) => Apply((rlo: integer) => Apply(
(rhi: integer) => Apply((rm: integer) => Apply(
(rv: integer) => Apply(
(rbase: integer) => ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(rs, 1, rt - 1 +
(1 if rlo < rv else 0) +
(1 if rv < rhi else 0)), 2, rs[2] +
rm * rbase), 2 +
3 *
(rt - 1) +
1, rlo),
2 +
3 *
(rt - 1) +
2,
rv - 1,
), 2 +
3 *
(rt - 1) +
3, rm *
_tables[rhi - rv +
1]),
2 +
3 *
(rt +
(1 if rlo < rv else 0) -
1) +
1,
rv + 1,
), 2 +
3 *
(rt +
(1 if rlo < rv else 0) -
1) +
2, rhi),
2 +
3 *
(rt +
(1 if rlo < rv else 0) -
1) +
3,
rm,
),
Fold(Function(ra +
_tables[rj + 1] *
_tables[rhi - rlo -
rj +
1], ra, rj), 0, Range(0, rv - rlo -
1, 1)),
),
Fold(Function(rj if _x[rj] < rlo ||
rhi < _x[rj] else rf, rf, rj), 0, Range(rlo, rhi, 1)),
), rs[2 +
3 *
(rt - 1) +
3]),
rs[2 +
3 *
(rt - 1) +
2],
), rs[2 +
3 *
(rt - 1) +
1]), rs[1]),
), rs_init, Range(1, _n, 1)),
Join([1, 0, 1, _n, 1], Map(Function(0, pz), Range(1, 3 * (_n + 1), 1))),
)[2]valid(_n, _x)
(Apply(
(cs_init: list<integer>) => Fold((cs: list<integer>, ck) => Apply(
(cs_next: list<integer>) => cs_next,
Apply((ct: integer) => Apply(
(clo: integer) => Apply(
(chi: integer) => Apply((cq: integer) => Apply(
(cn: integer) => Apply(
(cr: integer) => Apply((cv: integer) => ReplaceAt(ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(cs, 1, ct - 1 +
(1 if clo < cv else 0) +
(1 if cv < chi else 0)), 2, cs[2] if cn == 1 &&
_x[cv] == cq else 0), 2 +
3 *
(ct - 1) +
1, clo),
2 +
3 *
(ct - 1) +
2,
cv - 1,
), 2 +
3 *
(ct - 1) +
3, cv),
2 +
3 *
(ct +
(1 if clo < cv else 0) -
1) +
1,
cv + 1,
), 2 +
3 *
(ct +
(1 if clo < cv else 0) -
1) +
2, chi), 2 +
3 *
(ct +
(1 if clo < cv else 0) -
1) +
3, cv), clo if cr == 0 else cr),
Fold(Function(cj if _x[cj] < clo ||
chi < _x[cj] else cf, cf, cj), 0, Range(clo, chi, 1)),
),
Fold(Function(cc +
(1 if _x[cj] < clo ||
chi < _x[cj] else 0), cc, cj), 0, Range(clo, chi, 1)),
), cs[2 +
3 *
(ct - 1) +
3]),
cs[2 +
3 *
(ct - 1) +
2],
),
cs[2 +
3 *
(ct - 1) +
1],
), cs[1]),
), cs_init, Range(1, _n, 1)),
Join([1, 1, 1, _n, 0], Map(Function(0, pz), Range(1, 3 * (_n + 1), 1))),
)[2] == 1 if Fold(
Function(
ok_vi && 0 <= _x[vi] && _x[vi] <= _n,
ok_vi,
vi,
),
True,
Range(1, _n, 1),
) else False) if Length(_x) == _n else Falsetables(_n)
Apply((ct_init: list<integer>) => Fold(
(ct: list<integer>, ck) => Apply(
(ct_next: list<integer>) => ct_next,
ReplaceAt(
ct,
ck + 2,
Fold(
Function(cs +
ct[ci + 1] *
ct[ck - ci +
1], cs, ci),
0,
Range(0, ck, 1),
),
),
),
ct_init,
Range(0, _n - 1, 1),
), Join([1], Map(
Function(0, pz),
Range(1, _n, 1),
)))Maps
Into and out of BinaryTreeParentArray, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.
From BinaryTreeParentArray
- BinaryTreeBinaryTreeParentArray → BinaryTreeinverseThe binary tree an in-order parent array describes: a node below its parent goes left, above it right.
To BinaryTreeParentArray
- BinarySearchTreeParentArrayPermutation → BinaryTreeParentArrayThe binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.
- BinaryTreeParentArrayBinaryTree → BinaryTreeParentArrayinverseA binary tree as its parent array: its nodes numbered in order, entry k the number of the k-th node's parent, 0 at the root.
Enumeration
Examples
About
| Examples | 3 |
|---|
See also: BinaryTrees, BinarySearchTreeParentArray