# zbMATH — the first resource for mathematics

Embedding height balanced trees and Fibonacci trees in hypercubes. (English) Zbl 1193.68187
Summary: A height balanced tree is a rooted binary tree $$T$$ in which for every vertex $$v\in V(T)$$, the difference $$\mathbf b_T(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 $$T_h$$ of height $$h$$ is a subtree of the hypercube $$Q_{h+1}$$ of dimension $$h+1$$, if $$T_h$$ contains a path $$P$$ from its root to a leaf such that $$\mathbf b_{T_{h}}(v)=1$$ , for every non-leaf vertex $$v$$ in $$P$$. A Fibonacci tree $$\mathbb{F}_{h}$$ is a height balanced tree $$T_h$$ of height $$h$$ in which $$\mathbf{b}_{\mathbb{F}_{h}}(v)=1$$, for every non-leaf vertex. $$\mathbb{F}_{h}$$ has $$f(h+2)-1$$ vertices where $$f(h+2)$$ denotes the $$(h+2)$$th Fibonacci number. Since $$f(h)\sim 20.694h$$, it follows that if $$\mathbb{F}_{h}$$ is a subtree of $$Q_n$$, then $$n$$ is at least $$0.694(h+2)$$. We prove that $$\mathbb{F}_{h}$$ is a subtree of the hypercube of dimension approximately $$0.75h$$.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 65Y05 Parallel numerical computation 05C05 Trees
Full Text:
##### References:
  Adelson-Velskii, G.M., Landism, E.M.: An algorithm for the organization of information. Sov. Math. Dokl. 3, 1259–1262 (1962)  Andersson, A.: General balance trees. J. Algorithms 30, 1–18 (1999) · Zbl 0918.68077  Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan, London (1976)  Crescnzi, P., Piperno, A.: Optimal-area drawings of AVL trees. In: Proceedings of the DIMACS International Workshop on graph Drawings. Lecture Notes in Computer Science, vol. 894, pp. 307–317. Springer, Berlin (1994)  Das, S.K., Min, K.B.: A unified approach to parallel construction of search trees. J. Parallel Distrib. Comput. 27, 71–78 (1995) · Zbl 0833.68063  Dvorak, T.: Dense sets and embedding binary trees into hypercubes. Discrete Appl. Math. 155, 506–514 (2007) · Zbl 1111.05023  Ellis, C.S.: Concurrent search and insertion in AVL trees. IEEE Trans. Comput. 29(9), 811–817 (1980) · Zbl 0441.68071  Foster, C.C.: Information storage and retrieval using AVL trees. In: Proc. ACM 20th Nat. Conf., 192–205 (1965)  Georgakopoulos, G.F.: Splay trees: a reweighing lemma and a proof of competitiveness vs. dynamic balanced trees. J. Algorithms 50, 64–76 (2004) · Zbl 1078.68022  Havel, I.: On Hamiltonian circuits and spanning trees of hypercubes. Čas. Pěst. Mat. 109, 135–152 (1984) · Zbl 0544.05057  Havel, I.: On certain trees in hypercubes. In: Topics in Combinatorics and Graph Theory, pp. 353–358. Physica-Verlag, Heidelberg (1990) · Zbl 0743.05016  Hsu, W.J.: Fibonacci cubes–a new interconnection technology. IEEE Trans. Parallel Distrib. Syst. 4(1), 3–12 (1993) · Zbl 05106518  Hsu, W.J., Page, C.V., Liu, J.: Parallel contraction of Fibonacci trees and prefix computations on a family of interconnection topologies. In: Lecture Notes in Computer Science CAAP ’92, vol. 581, pp. 182–202. Springer, Berlin (1992)  Karlton, P.L., Fuller, S.H., Scroggs, R.E., Kaehler, E.B.: Performance of height-balanced trees. Commun. ACM 19(1), 23–28 (1976) · Zbl 0317.68044  Klavžar, S.: On median nature and enumerative properties of Fibonacci-like cubes. Discrete Math. 299, 145–153 (2005) · Zbl 1073.05007  Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3, Addison-Wesley, Reading (1973) · Zbl 0302.68010  Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo (1992) · Zbl 0743.68007  Liu, J., Hsu, W.-J., Chung, M.J.: Generalized Fibonacci cubes are mostly Hamiltonian. J. Graph Theory 18(8), 817–829 (1994) · Zbl 0816.05041  Medidi, M., Deo, N.: Parallel dictionaries using AVL-trees. J. Parallel Distrib. Comput. 49, 146–155 (1998) · Zbl 0914.68043  Plandowski, W., Rytter, W., Szymacha, T.: Parallel tree-contraction and Fibonacci numbers. Inf. Process. Lett. 59, 267–271 (1996) · Zbl 0900.68239  Rodeh, O., Birman, K.P., Dolev, D.: Using AVL trees for fault-tolerant group key management. Int. J. Internet Sci. 1, 84–99 (2002) · Zbl 1047.68068  Taranenko, A., Vesel, A.: Fast recognition of Fibonacci cubes. Algorithmica 49, 81–93 (2007) · Zbl 1131.68075  Wu, J.: Extended Fibonacci cubes. IEEE Trans. Parallel Distrib. Syst. 8(12), 1203–1210 (1997) · Zbl 05108029  Zelina, I., Moldovan, G., Sitar, P.P.: Some communication aspects in extended Fibonacci cubes. In: International Symposium on Application and the Internet, SAINT 2008, pp. 245–248 (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.