# On Counting and Embedding a Subclass of Height-Balanced Trees

Authors: Indhumathi Raman
Journal: Modelling and Simulation in Engineering
 (2014)

---

## Abstract

A height-balanced tree is a rooted binary tree in which, for every vertexv, the difference in the heights of the subtrees rooted at the left and right child of v (called the balance factor of v) is at most one. In this paper, we consider height-balanced trees in which the balance factor of every vertex beyond a level is 0. We prove that there are 22t-1 such trees and embed them into a generalized join of hypercubes.


---

## Body

## 1. Introduction

The problem of efficiently implementing parallel algorithms on parallel computers has been studied as a graph embedding problem, which is to embed the communication graphGA (underlying a parallel algorithm A) within the network topology HN of a parallel computer N with minimum communication overhead. The working of the parallel algorithm A when implemented on N can be described by embedding GA into HN. Mathematically, an embedding ϕ of a (guest) graph G(V, E) into a (host) graph H(W, F) is a one-one function ϕ:V→W such that if (u, v) is an edge in G, then ϕ(u) and ϕ(v) are connected by a path in H. We use ϕ:V→W and ϕ:G→H analogously. The following are two of the parameters that measure the quality of an embedding.(i)
Dilation(ϕ):=max⁡{distH(ϕ(u),ϕ(v)):(u,v)∈E}. By distH(x,y) we mean the shortest distance between x and y in graph H. The dilation of an embedding measures the maximum time required to route a message in the host graph, between any two vertices. If dilation(ϕ)=1, then G is isomorphic to a subgraph of H and we write G⊆H. If dilation(ϕ)=2, then in this paper we denote it by G↪H.(ii)
Expansion(ϕ):=|W|/|V|.This parameter measures the relative number of unutilized processors in the host graph. Since ϕ is a one-one function, expansion(ϕ) is at least 1.A goal of a parallel algorithm designer is to map (or embed) the algorithm graphG into an interconnection network H with dilation and expansion kept as minimum as possible. However, for most embedding problems, it is very difficult to obtain an embedding that minimizes these parameters simultaneously. Therefore, some tradeoffs among the parameters must be made; see Leighton [1].Trees generally form the underlying data structure for several parallel algorithms that employ divide-and-conquer rule, branch-and-bound technique, and so on. A self-balancing binary search tree that ensures a logarithmic running time (in both average and worst case) on operations such as insertion, deletion, and rotation, regardless of the order of the data inserted, is a height-balanced tree. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. However, these rotations take constant time. The height-balanced trees are also called AVL trees, named after their inventors Adelson-Velskii and Landis [2], and their computational aspects are discussed in [3–5]. The computational efficiency of height-balanced data structures has motivated a vast study in parallel computations too. They have been used for concurrent search, concurrent insertion, and information storage and retrieval and implement parallel dictionary routines; see [4–7]. A formal definition of height-balanced trees is given in the next section.On the other hand, among the interconnection networks of parallel computers, the binaryhypercube has received much attention. Ann-dimension hypercube (denoted by Qn) has 2n vertices each labelled with a binary string of length n and two vertices are adjacent if and only if their labels differ in exactly one position. The hypercube topology has several attractive features. Its popularity is due to the fact that the nodes of a hypercube are symmetrically placed and the number of interprocessor connections per node is small. Another important property of a hypercube is its ability to efficiently simulate the message routings of other interconnection networks. An extensive survey of embedding various graphs into hypercubes is given in [1, 8–10].In this paper, we consider a subclassHB(h, t) of height-balanced trees and we analyse the size of the subclass by counting the number of trees in it. We also prove that every height-balanced tree Th∈HB(h, t) is embeddable in a generalized join of hypercubes with dilation 2.


## 2. Preliminaries

Definition 1.
A rooted binary treeT is said to be height-balanced if, 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.A classical example of a height-balanced tree is the complete binary tree. Figure1 shows a few small height-balanced trees.Figure 1
Examples of height-balanced trees.In this paper, without loss of generality, we assume that the height of the left subtree is not less than the height of the right subtree for everyv∈V(T). With any height-balanced tree T, we associate a function bT:V(T)→{0, 1} defined by bT(v):= the difference between the heights of left and right subtrees of v, for every vertex v∈V(T). This difference bT(v) is called the balance factor of v. The balance condition, being binary, ensures that the height of a height-balanced tree is logarithmic of its size; refer to [11].It is usually assumed that the height of an empty tree is-1 and that of a single-vertex tree is 0. Consequently, for a leaf l∈V(T), bT(l)=0. Clearly,
(1)bT(v)=0,foreveryv∈V(T)iiiffTisacompletebinarytree.
If Th is a height-balanced tree of height h, we denote its levels by L0, L1,…,Lh, where Li={v∈V(Th):dist⁡(v,root)=i},0≤i≤h. It is shown in [2] that the(2)subtreeofThinducedbyverticesinL0∪L1⋯∪L⌊h/2⌋iscomplete.LetHB(h,t)(where0≤t≤h) denote the subclass of height-balanced trees T with height h such that
(3)bT(v)={0ifv∈Lt∪Lt+1∪⋯∪Lh0or1ifv∈VLt∪Lt+1∪⋯∪Lh.
So HB(h,0)⊂HB(h,1)⊂⋯⊂HB(h,h). While HB(h,0) contains only one element, namely, the complete binary tree of height h, HB(h,h) is the class of all height-balanced trees of height h. Let v(t,j) be the jth vertex from left at level t; then it follows from (1) and from the definition of HB(h,t) that
(4)thesubtreeofTrootedatv(t,j)∈Ltisacompletebinarytree.
By (2) and (4), the number of vertices in T∈HB(h,t), for 0≤t≤⌊h/2⌋, is
(5)|V(T)|=(2t-1)+∑v(t,j)∈Lt(2hj+1-1)=∑j=12t‍(2hj+1)-1.


## 3. Counting Trees of HB(h,t)

Theorem 2.
The classHB(h,t) of height-balanced trees contains exactly 22t-1 trees.Proof.
The idea of the proof is to establish a one-to-one correspondence betweenHB(h,t) and Z22t-1. That is, for every T∈HB(h,t), we will prove that there exists a sequence (x1,x2,…,x2t-1),xi∈{0,1},1≤i≤2t-1, such that bT(v(j,k))=x2j+k-1,0≤j≤t-1,1≤k≤2j, and vice versa.
We first assume the existence of a treeT∈HB(h,t) and associate an element of Z22t-1 to T. Given the tree T, we order the vertices of L0∪L1∪⋯∪Lt-1 according to the breadth first search (BFS), say, (v1,v2,…,v2t-1). For 1≤i≤2t-1, let xi=bT(vi). Then the sequence (x1,x2,…,x2t-1) is the required sequence.
We next prove the converse. For a given sequence(x1,x2,…,x2t-1) of 0’s and 1’s, we construct a tree T (Figure 2) such that (1) T∈HB(h,t) and (2) bT(v(t,j))=x2t-j+1 as follows. Consider a complete binary tree Ct of height t. Let lj denote the jth leaf (where 1≤j≤2t) from left in level t. For every j,1≤j≤2t, we root a complete binary tree Chj to lj (i.e., lj becomes the root of Chj). The height hj of Chj is calculated as follows:
(6)hj={h-t,ifj=1hj-2sj-x[2t-sj-1+⌈(j-1)/2sj+1⌉-1],
where
(7)sj={0,ifjisevengreatestpowerof2thatdividesj-1,ifjisodd.
Claim1(T∈HB(h,t)).From (6), we note that hj≤h-t. Therefore, the height of Tis height of Ct+max⁡1≤j≤2thj=t+(h-t)=h. In T, for all i≥t, every vertex u∈Li is a vertex of some Chj,1≤j≤2t. Hence, bT(u)=0 for all u∈(Lt∪Lt+1∪⋯∪Lh). This implies that T∈HB(h,t).
Claim2(for0≤j≤t-1and1≤k≤2j,bT(v(j,k))=x2j+k-1). Let Tj,k denote the subtree rooted at the vertex v(j,k) of T. Hence by definition, the balance factor bT(v(j,k)) of the vertex v(j,k) is the difference between the heights of the left subtree Tj+1,2k-1 and the right subtree Tj+1,2k of v(j,k). That is,(8)bT(v(j,k)):=HeightofTj+1,2k-1-HeightofTj+1,2k=[(t-j-1)+HeightofTt,k2t-j-2t-j+1]-[(t-j-1)+HeightofTt,k2t-j-2t-j-1+1].
Let m1 and m2 denote the integers k2t-j-2t-j+1 and k2t-j-2t-j-1+1, respectively. Since the subtree rooted at a vertex in level t is a complete binary tree, we have Tt,m1≃Chm1andTt,m2≃Chm2 and bT(v(j,k))=hm1-hm2. In order to calculate the difference hm1-hm2, we consider two cases.
Case
1
(
0
≤
j
<
t
-
1
). On rewriting the values of m1 and m2 we have m1=2t-j(k-1)+1 and m2=2t-j(k-1)+2t-j-1+1. We note that the greatest powers of 2 that divides m1-1 and m2-1 are t-j and t-j-1. Hence, by following (6), we have sm1=t-j and sm2=t-j-1, hm1=hm1-2t-j-x[2j-1+⌈(m1-1)/2t-j+1⌉-1], and then,
(9)hm2=hm2-2t-j-1-x[2t-(t-j-1)-1+⌈(m2-1)/2t-j⌉-1]=hm1-x[2j+⌈(k2t-j-2t-j-1)/2t-j⌉-1]=hm1-x2j+k-1.
Case
2
(
j
=
t
-
1
).In this case, m1=2k-1 and m2=2k. Since m2 is even, sm2=0 and
(10)hm2=hm2-1-x[2t-1+⌈(m2-1)/2⌉-1]=hm1-x2j+k-1.
Hence in both cases, bT(v(j,k))=hm1-hm2=x2j+k-1. We have proved the claims and hence the theorem.Figure 2
T
∈
HB
(
h, t). The circles represent the vertices of the induced CBT from level 0 to t. The text inside the circle v(i, j) for 0≤i≤t,1≤j≤2i denotes the jth vertex from left at Li. The vertex v(t, j) is also denoted by lj.


## 4. Embedding Trees of HB(h,t)

In this section, we embed every treeT∈HB(h,t) into a generalized join of hypercubes. Before we proceed to the result, we define the join of graphs and prove certain preliminary lemmas.Definition 3.
The join (denoted byG1+G2) of two graphs G1 and G2 is defined as follows:
(11)V(G1+G2)=V(G1)∪V(G2)E(G1+G2)=E(G1)∪E(G2)∪{(u,v):u∈V(G1),v∈V(G2)},
that is, joining each vertex of G to every vertex of H. Figure 3 shows the join Q1+Q2 of the hypercubes Q1 and Q2.The graph joinQ1+Q2.
(a)
Q
1
(b)
Q
2
(c)
Q
1
+
Q
2Hence from the definition of graph join we have|V(G1+G2)|=|V(G1)|+|V(G2)| and |E(G1+G2)|=|E(G1)|+|E(G2)|+|V(G1)||V(G2)|. We denote the generalized join (G1+(G2+⋯(Gn-1+Gn))) of graphs G1,G2,…,Gn by ∑i=1n‍Gi. We note that |V(∑i=1n‍Gi)|=∑i=1n‍|V(Gi)|.Lemma 4.
LetCh† be a supertree of the complete binary tree Ch of height h with root A formed by adding a new vertex B and the edge (A,B). Let DRCBT(h+1) be the double rooted complete binary tree on 2h+1 vertices. Then Ch†↪DRCBT(h+1).Proof.
Figure4 shows the tree Ch†. We call B as thedeep root of Ch†. Consider an embedding f:V(Ch†)→V(DRCBT(h+1)) as shown in Figure 4. Such an embedding f has dilation 2 since the edge (A,D)∈E(Ch†) is mapped onto a path of length 2 in DRCBT(h+1) and this is the maximum shortest distance. The embedding f has expansion 1 since both Ch† and DRCBT(h+1) have 2h+1 vertices. Hence, in short, Ch†↪DRCBT(h+1).Figure 4
C
h
+
↪
DRCBT
(
h
+
1
).It is known thatDRCBT(h+1) is a subgraph of Qh+1; see Nebeský [12]. Hence, this fact along with Lemma 4 implies the following.Lemma 5.
One hasCh†↪Qh+1.In the next theorem, we give an embedding of every tree ofHB(h,t) into a generalized join of hypercubes.Theorem 6.
LetT∈HB(h,t) and let hj be the height of the complete binary tree rooted at thejth vertex from left at a level t(0≤t≤⌊h/2⌋) of T. Then T↪∑j=12t‍Qhj+1.Proof.
ConsiderT∈HB(h,t). Let v(i,j) denote the ith vertex from left in level j. Decompose the tree into a forest of trees by deleting the set of edges {(v(t-1,k),v(t,2k-1)),(v(t-1,k),v(t,2k))} for 1≤k≤2t-1. Such a forest consists of complete binary trees Chj rooted at v(t,j) (for 1≤j≤2t) and a complete binary tree Ct-1 induced by the vertices of T from levels 0 to t-1. For 1≤j≤2t-1, let v(a,b) where 2a+b-1=j be the deep root of Chj. Consider the embeddings fj:Chj†↪Qhj+1 (such embeddings exist by Lemma 5). For j=2t, consider fj:Chj↪Qhj+1 (such an embedding exists by [12]). The vertices v(i,j) for 0≤i≤t and 1≤j≤2i form a complete graph (a graph in which every pair of distinct vertices is connected by a unique edge) in ∑j=12t-1‍Qhj+1 and hence contain as subgraph the deleted set of edges of T. Such an embedding technique is depicted in Figure 5. The dilation of the embedding is clearly 2 and hence T↪∑j=12t‍Qhj+1. The number of vertices of ∑j=12t‍Qhj+1 is ∑j=12t‍2hj+1 and by (5), we have |V(T)|=∑j=12t‍(2hj+1)-1. Hence the expansion of the embedding is almost 1 and is optimal.Figure 5
Embedding ofT∈HB(h, t) in ∑j=12t‍Qhj+1. The intermediate edges between every pair of vertices are not shown for clarity purpose.


## 5. Conclusion

In this paper, we have considered a subclassHB(h,t) of height-balanced trees and have analysed the size of this subclass. We have also embedded every tree in this subclass into a generalized join of hypercubes.



---

*Source: 748941-2014-05-26.xml*