The Super-B-Tree Algorithm.

Abstract

In the traditional literature concerning AVL 2-3, bounded balance or multiway B-trees, it has been assumed that a pointer-changing operation would require approximately one unit of runtime. This approximation is inapplicable to the augmented trees of BS77, Lu78b, Wi78a and Wi78c, because these threes associate an auxiliary data structure to each interior node, which complicates the cost of pointer-changing operations. Such an operation will consume 1 + Jw units of runtime in an augmented three application (where J denotes the number of records that gain a new ancestor as a result of the pointer-changing operation, and w is a coefficient depending on the particular application). The purpose of this paper is to propose an algorithm which is a generalization of traditional B-trees designed to possess an O(wlog N) worst-case insertion and deletion runtime in an augmented tree environment. This algorithm is significant because it has the optimal runtime order of magnitude.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1979
Accession Number
ADA110391

Entities

People

  • Dan E. Willard

Organizations

  • Harvard University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Coefficients
  • Computations
  • Continents
  • Contracts
  • Equations
  • Geographic Regions
  • Intervals
  • Military Research
  • New Jersey
  • Procedures (Computers)
  • Rotation
  • Security
  • Sequences
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Software Engineering.
  • Theoretical Analysis.