×

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adelson-Velskii, G.M., Landism, E.M.: An algorithm for the organization of information. Sov. Math. Dokl. 3, 1259–1262 (1962)
[2] Andersson, A.: General balance trees. J. Algorithms 30, 1–18 (1999) · Zbl 0918.68077
[3] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan, London (1976)
[4] 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)
[5] 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
[6] Dvorak, T.: Dense sets and embedding binary trees into hypercubes. Discrete Appl. Math. 155, 506–514 (2007) · Zbl 1111.05023
[7] Ellis, C.S.: Concurrent search and insertion in AVL trees. IEEE Trans. Comput. 29(9), 811–817 (1980) · Zbl 0441.68071
[8] Foster, C.C.: Information storage and retrieval using AVL trees. In: Proc. ACM 20th Nat. Conf., 192–205 (1965)
[9] 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
[10] Havel, I.: On Hamiltonian circuits and spanning trees of hypercubes. Čas. Pěst. Mat. 109, 135–152 (1984) · Zbl 0544.05057
[11] Havel, I.: On certain trees in hypercubes. In: Topics in Combinatorics and Graph Theory, pp. 353–358. Physica-Verlag, Heidelberg (1990) · Zbl 0743.05016
[12] Hsu, W.J.: Fibonacci cubes–a new interconnection technology. IEEE Trans. Parallel Distrib. Syst. 4(1), 3–12 (1993) · Zbl 05106518
[13] 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)
[14] 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
[15] Klavžar, S.: On median nature and enumerative properties of Fibonacci-like cubes. Discrete Math. 299, 145–153 (2005) · Zbl 1073.05007
[16] Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3, Addison-Wesley, Reading (1973) · Zbl 0302.68010
[17] Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo (1992) · Zbl 0743.68007
[18] 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
[19] Medidi, M., Deo, N.: Parallel dictionaries using AVL-trees. J. Parallel Distrib. Comput. 49, 146–155 (1998) · Zbl 0914.68043
[20] Plandowski, W., Rytter, W., Szymacha, T.: Parallel tree-contraction and Fibonacci numbers. Inf. Process. Lett. 59, 267–271 (1996) · Zbl 0900.68239
[21] 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
[22] Taranenko, A., Vesel, A.: Fast recognition of Fibonacci cubes. Algorithmica 49, 81–93 (2007) · Zbl 1131.68075
[23] Wu, J.: Extended Fibonacci cubes. IEEE Trans. Parallel Distrib. Syst. 8(12), 1203–1210 (1997) · Zbl 05108029
[24] 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.