login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

George Tanev, Table of n, a(n) for n = 1..10000

Stevo Bozinovski, Adrijan Bozinovski, Brain Rhythms, Pascal Triangle, and Brain-Computer Interface, ICEST (Ohrid, North Macedonia 2019), 191-193.

NIST, Height-balanced tree

NIST, Complete-binary tree

NIST, Full-binary tree

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 sub-tree 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 sub-tree up to and including level h = 2 is full. 2^h - 1 nodes will form the full sub-tree, 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

a(n) = n - 1 - A279521(n). - Alois P. Heinz, Nov 16 2020

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)):

seq(a(n), n=1..100);  # Alois P. Heinz, Dec 20 2016

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;

    } // George Tanev, Oct 07 2016

(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

Cf. A056971, A279521.

Sequence in context: A025782 A120506 A327041 * A246262 A275974 A052288

Adjacent sequences:  A277264 A277265 A277266 * A277268 A277269 A277270

KEYWORD

nonn

AUTHOR

Adrijan Božinovski and George Tanev, Oct 07 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 15 04:03 EDT 2021. Contains 343909 sequences. (Running on oeis4.)