A height-balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the heights of the left and right subtrees of v, differ by at most one. In this paper, we embed two subclasses of height-balanced trees into hypercubes with unit dilation. We also prove that for certain values of p and for all m≥1, a complete pm-ary tree of height h is embeddable into a hypercube of dimension O(mh) with dilation O(m) using the embedding results of the above height-balanced trees. These results improve and extend the results of Gupta et al. (2003) [10]. © 2013 Elsevier B.V.

Indhumathi R

Choudum S.A.

embedding

HEIGHT-BALANCED TREES

HYPER-CUBES

Hypercube

K-ARY TREE

SUBTREES

Combinatorial mathematics

Computational methods

geometry

Fulltext

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Journal of Discrete Algorithms

International Journal of Computer Mathematics: Computer Systems Theory

Certain height-balanced subtrees of hypercubes

Information Sciences

Long paths in hypercubes with conditional node-faults

A height balanced tree is a rooted binary tree T in which for every vertex v ∈ V(T), the difference bT (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree Th of height h is a subtree of the hypercube Qh+1 of dimension h + 1, if Th contains a path P from its root to a leaf such that bTh(v) = 1, for every non-leaf vertex v in P. A Fibonacci tree Fh is a height balanced tree Th of height h in which bFh(v) = 1, for every non-leaf vertex. F h has f(h + 2) - 1 vertices where f(h + 2) denotes the (h + 2)th Fibonacci number. Since f(h) ∼ 20.694h, it follows that if F h is a subtree of Qn, then n is at least 0.694(h+2). We prove that Fh is a subtree of the hypercube of dimension approximately 0.75h. © 2008 Korean Society for Computational and Applied Mathematics.

Journal of Applied Mathematics and Computing

Embedding height balanced trees and Fibonacci trees in hypercubes

A height-balanced tree is a rooted binary tree T in which for every vertex v ∈ V (T), the heights of the subtrees, rooted at the left and right child of v, differ by at most one; this difference is called the balance factor of v. These trees are extensively used as data structures for sorting and searching. We embed several subclasses of height-balanced trees of height h in Qh + 1 under certain conditions. In particular, if a tree T is such that the balance factor of every vertex in the first three levels is arbitrary (0 or 1) and the balance factor of every other vertex is zero, then we prove that T is embeddable in its optimal hypercube with dilation 1 or 2 according to whether it is balanced or not. © 2009 Elsevier Inc. All rights reserved.

On embedding subclasses of height-balanced trees in hypercubes

Longest fault-free paths in hypercubes with vertex faults

Journal of Parallel and Distributed Computing

Efficient embeddings of ternary trees into hypercubes

Embedding certain height-balanced trees and complete pm-ary trees into hypercubes

Journal	Journal of Discrete Algorithms
ISSN	15708667
Open Access	Yes