Certain height-balanced subtrees of hypercubes. Issue 1 (2nd January 2016)

• Record Type: Journal Article
• Authors: Raman, Indhumathi
• Is Part Of: International journal of computer mathematics. Volume 1:Issue 1(2016)
• Page Start: 32
• Page End: 41
• Publication Date: 2016-01-02
• Subjects: Height-balanced tree -- embedding -- subgraph -- hypercube; 05C78 -- 05C85 -- 68R10; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2016.1181671
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: A height-balanced tree is a desired data structure for performing operations such as search, insert and delete, on high-dimensional external data storage. Its preference is due to the fact that it always maintains logarithmic height even in worst cases. It is a rooted binary tree in which for every vertex the difference (denoted as balance factor) in the heights of the subtrees, rooted at the left and the right child of the vertex, is at most one. In this paper, we consider two subclasses of height-balanced trees and . A tree in is such that all the vertices up to (a predetermined) level t has balance factor one and the remaining vertices have balance factor zero. A tree in is such that all the vertices at alternate levels up to t has balance factor one and the remaining vertices have balance factor zero. We prove that every tree in the classes and is a subtree of the hypercube.