Sequence_Kernel_4 With Balanced Binary Trees

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

Sequence is one of the more useful objects in programming. However, the reliance on linked lists for an implementation can mean that some algorithms don't run as well as they could. The goal of this project is to try to create an implementation of sequence that could access a character in O(lg n) time in the worst case, while sacrificing some time during insertion or deletion due to balancing the tree.

Calendar:

February 2003: Started project. Looked at balancing schemes, defined the correspondence.

March 2003: Worked on Convention. Looked at using the Symmetric_Compose Extension of the Binary_Tree object.

April 2003: Convention/Correspondence completed. Presented at Europa Meeting.

Project Development:

As it turns out, the convention is not difficult to define at all. To define the mapping between a binary tree and a sequence, all you have to do if find the middle point of the sequence. Every position less than the middle point is in the left subtree and everything greater than the middle is in the right subtree. This is a recursive definition that lets you see very easily how the tree is generated.

In my initial design, there was one minor problem; because all of the algorithms for sequence will now have to be defined recursively, the accessor is going to cause trouble. When the function finds the correct position, it's going to want to return the value immediately without recomposing the tree. The solution to this is to put the return value in a cache first. The cache will store the value, along with its proper position in the tree.

The design in its final form makes extensive use of the Symmetric_Compose extension to Binary_Tree. Symmetric_Compose_2, in particular, implements the balancing scheme used in AVL trees (Described in Knuth) In addition to the balancing that Symmetric_Compose does, it also includes a function, SYMMETRIC_ORDER, which was very useful in defining the convention and the correspondence.

Findings and Contributions:

The correspondence between the Kernel and the Abstract type is that the binary tree in symmetric order must equal the desired sequence. If there is something in the cache, then the element should be included in the correct place in the sequence. The convention maintains the fact that the tree must remain balanced. This is accomplished using the Symmetric_Compose algorithm, which turns out to be a very useful component and idea. That is, to encapsulate an algorithm and use it in lieu of an existing kernel component. This implementation of Sequence is useful in some cases because lookups for a particular location are done in O(lg n) time.

Links and References:

The Symmetric Compose Object.

  Return to Europa