Embedding Complete Ternary Tree in Hypercubes Using AVL Trees

摘要

A complete ternary tree is a tree in which every non-leaf vertex has exactly three children. We prove that a complete ternary tree of height h, TTh, is embeddable in a hypercube of dimension. This result coincides with the result of 'Embedding Complete Ternary Trees into Hypercubes', an earlier work. However, in this paper, the embedding utilizes the knowledge of AVL trees. We prove that a subclass of AVL trees is a subgraph of hypercube. The problem of embedding AVL trees in hypercube is an independent emerging problem.