|
| |
|
|
A277267
|
|
Minimum number of single-direction edges in leveled binary trees with n nodes.
|
|
2
|
|
|
|
0, 0, 1, 1, 1, 2, 3, 3, 3, 3, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
A leveled binary tree is a binary tree where every level, except possibly the last, is completely filled.
Unlike a complete binary tree, where nodes in the last level are always stacked linearly from left to right, insertion in a leveled binary tree can be done in any order.
The formula for obtaining this integer series counts the minimum number of single-direction edges in a leveled binary tree of an arbitrary size n, and is presented alongside its proof. The same formula gives the minimum number of right, as well as the minimum number of left, edges in any leveled binary tree. The proof is analogous for both cases.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = 2^(h-1) - 1 + (n - 3*2^(h-1) + 1) * H(n - 3*2^(h-1) + 1), where h = log_2(n) and is the height of the binary tree, and H is the Heaviside function (i.e., H(x) = 1 if x >= 0 and H(x) = 0 if x < 0).
Proof:
If n = 2^k - 1 (for any k > 0), i.e., if n = {3, 7, 15, ...}, the binary tree is full, and, as any tree, contains n-1 edges (1 fewer than the number of nodes). Any n = 2^k - 1 is an odd number, so the number one less than that is always even. In a full binary tree, every internal (i.e., non-leaf) node has both a left and a right sub-node, so there will be equally as many left as right edges in such a tree. Thus, half of that number will be the number of strictly left or strictly right edges. In this proof, strictly left edges will be viewed (the proof is analogous for strictly right edges). The proof will treat both terms in the addition in separate sections.
1) If n != 2^k - 1, the leveled binary tree is not full. More precisely, the last level (level h) isn't full, but the subtree consisting of the root and all the levels of the tree up to (and including) level h-1 is. As in one of the examples, the leveled tree with n = 8 is not full and has a height of h = 3, but its subtree up to and including level h = 2 is full. 2^h - 1 nodes will form the full subtree, which will have 2^h - 2 edges, and half of those edges, i.e., 2^(h-1) - 1, will be strictly left.
2) The last level of the leveled binary tree can contain at most 2^h nodes. If it is filled with right sub-nodes first, the number of left edges will not increase, up to a point when all of the right sub-nodes have been inserted and the next node to be inserted will have to be a left sub-node. As is evident in the given examples, it is possible to insert only right sub-nodes in the last level of the leveled binary trees with n = 4 and n = 5, but in a leveled binary tree with n = 6 a left sub-node must be inserted in the last level (h = 2), since there is no more room to insert right sub-nodes. This forces an increase in the number of left edges. It can be observed that the moment when the number of left edges in a leveled binary tree must increase is when a node is entered after half of the possible positions to insert nodes in the last level, i.e., 2^h / 2 = 2^(h-1), have been occupied. Furthermore, the number of nodes in the leveled binary tree must be greater than the sum of the nodes already present in the previous levels of the tree and half of the nodes in the last level, in order for the minimum number of left edges to increase; otherwise the minimum number of left edges will remain 2^(h-1) - 1. Therefore, the number of strictly left edges will increase only when n > 2^h - 1 + 2^(h-1), i.e., n > 3*2^(h-1) - 1, or, stated differently, n - 3*2^(h-1) + 1 > 0. This condition can be expressed with the Heaviside step function as H(n - 3*2^(h-1) + 1), and the minimum number of left edges will increase by the difference between the total number of nodes and the number of nodes already present, which is n - 3*2^(h-1) + 1.
The sum of the terms in sections (1) and (2) leads to the final formula: a(n) = 2^(h-1) - 1 + (n - 3*2^(h-1) + 1)*H(n - 3*2^(h-1) + 1).
Also a(n) = sum(b2(i),i=1..n), where b2(i) is the 2nd significant bit in the binary expansion of i. - Jeffrey Shallit, May 09 2019
|
|
|
EXAMPLE
|
In a leveled binary tree with 1 node, there are at least 0 strictly left edges: n=1 => a(n)=0.
o
In a leveled binary tree with 2 nodes, there are at least 0 strictly left edges: n=2 => a(n)=0.
o
\
o
In a leveled binary tree with 3 nodes, there is at least 1 strictly left edge: n=3 => a(n)=1.
o
=> / \
o o
In a leveled binary tree with 4 nodes, there is at least 1 strictly left edge: n=4 => a(n)=1.
o
=> / \
o o
\
o
In a leveled binary tree with 5 nodes, there is at least 1 strictly left edge: n=5 => a(n)=1.
o
=> / \
o o
\ \
o o
In a leveled binary tree with 6 nodes, there are at least 2 strictly left edges: n=6 => a(n)=2.
___o
=> / \
o o
=> / \ \
o o o
In a leveled binary tree with 7 nodes, there are at least 3 strictly left edges: n=7 => a(n)=3.
___o___
=> / \
o o
=> / \ => / \
o o o o
In a leveled binary tree with 8 nodes, there are at least 3 strictly left edges: n=8 => a(n)=3.
___o___
=> / \
__o o
=> / \ => / \
o o o o
\
o
In a leveled binary tree with 9 nodes, there are at least 3 strictly left edges: n=9 => a(n)=3.
_____o___
=> / \
__o o
=> / \ => / \
o o o o
\ \
o o
And so on.
G.f. = x^3 + x^4 + x^5 + 2*x^6 + 3*x^7 + 3*x^8 + 3*x^9 + 3*x^10 + 3*x^11 + 4*x^12 + ...
|
|
|
MAPLE
|
a:= n-> (b-> max(n-b, b/2-1))(2^ilog2(n)):
|
|
|
MATHEMATICA
|
Table[Function[h, 2^(h - 1) - 1 + Boole[# >= 0] # &@ (n - 3*2^(h - 1) + 1)]@ Floor[Log2@ n], {n, 71}] (* Michael De Vlieger, Oct 12 2016 *)
|
|
|
PROG
|
(Java)
static int a(int n) {
double h = Math.floor(Math.log(n) / Math.log(2));
double k = Math.pow(2, h - 1);
return (int) (k - 1 + (n - 3*k + 1) * Heaviside(n - 3*k + 1));
}
static int Heaviside(double x) {
return x>=0 ? 1 : 0;
(PARI) a(n)=my(h=logint(n, 2), k=2^(h-1), t=n - 3*k + 1); return(k-1+if(t>=0, t, 0)); \\ Joerg Arndt, Oct 11 2016
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
