ScholarLens Back to search
1989•Proceedings of the 17th conference on ACM Annual Computer Science ConferenceRequires access

An optimal search tree: complete binary search tree

Narayan Murthy

Open publisher page 1 citations

Abstract

Definitions and properties of a complete binary tree and a binary search tree are well known [1]. This short paper discusses a method to construct a binary search tree which is also a complete binary tree. We call such a tree a Complete Binary Search Tree, a CBS Tree for short. Two basic advantages of a CBS tree are that it is a search tree with minimum height and that it can be placed in an array. The latter allows for implementation of the data structure without the use of pointers.

About this research paper

What this paper is about

Definitions and properties of a complete binary tree and a binary search tree are well known [1]. This short paper discusses a method to construct a binary search tree which is also a complete binary tree. We call such a tree a Complete Binary Search Tree, a CBS Tree for short. Two basic advantages of a CBS tree are that it is a search tree with minimum height and that it can be placed in an array. The latter allows for implementation of the data structure without the use of pointers.

Why it matters

OpenAlex reports 1 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Definitions and properties of a complete binary tree and a binary search tree are well known [1]. This short paper discusses a method to construct a binary search tree which is also a complete binary tree. We call such a tree a Complete Binary Search Tree, a CBS Tree for short. Two basic advantages of a CBS tree are that it is a search tree with minimum height and that it can be placed in an array. The latter allows for implementation of the data structure without the use of pointers.

Key concepts: Optimal binary search tree, Self-balancing binary search tree, K-ary tree, Interval tree, Random binary tree, Ternary search tree, Binary tree, Tree traversal

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
An optimal search tree: complete binary search tree — Research Paper | ScholarLens