article · 2007

A Logarithmic Random Access Tree

Tom Morgan

Cited by 0Abstract and details only

Abstract

Making a data structure that performs like a dynamic array but functions in logarithmic time for all operations is the goal, but is by no means a trivial one. The obvious solution is to use a tree of some sort, but how? By using a binary tree in which values are stored at the leaf nodes and each node keeps track of how many leaves there are below it, we can quickly achieve logarithmic random access, insertion and deletion in the average case but all operations are linear on the worst case. To balance the tree, a self-balancing binary search tree like a Red Black Tree or a Splay Tree is used. These trees are always balanced and by using their balancing mechanisms and changing them to use the random access system described above, the goal is reached.

Cite this paper

APA 7

Morgan, T. (2007). A Logarithmic Random Access Tree.

MLA 9

Morgan, Tom. “A Logarithmic Random Access Tree.” 2007.

Chicago

Morgan, Tom. 2007. “A Logarithmic Random Access Tree.”

Harvard

Morgan, T. (2007) ‘A Logarithmic Random Access Tree’.

BibTeX

@article{morgan2007logarithmic,
  title = {{A Logarithmic Random Access Tree}},
  author = {Morgan, Tom},
  year = {2007}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.