All,
I have done preliminary research into various different types of binary trees and none of them seem to fit all my requirements without modification. Since raw speed is also a necessity, anything I prototype in Perl will ultimately be ported to C. Here are my requirements:

• Can be traversed forwards and backwards
• Can be traversed starting at either end
• Keep items in order (ascending numerically)
• Add and remove items in the middle fast
• Find an element (or nearest match) using a binary search
• Determine the distance between 2 items

Amazingly enough, Perl arrays fit all of these requirements except that splice is O(N). Balanced trees are faster but are also more complex and wouldn't meet some of the other requirements without some modification.

I also have a derived requirement. I will be finding two items using separate binary searches. If the distance between the two items fits a certain criteria, I will be traverse between the two items. I do not want to have to perform the first binary search again so I would like to be able to remember it and start there.

What I am looking for is a specific suggestion on a datastructure that you are confident that can be modified to fit all my requirements. As I indicated above, I have done surface research on various different datastructures and none fit the bill out of the box. They are complicated enough that I don't want to spend my time unraveling their mysterious unless I am confident they are worth the effort.

One final note - the number of items will never exceed 1000.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.