1
$\begingroup$

Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time.

For a specific problem I was musing about a balanced tree that would allow for an zero-based array implementation with logarithmic time for all of the following operations: insertion, removal and finding the next and previous element.

I'm reasonably sure it should be straight-forward to implement: The non-leaf nodes would have to store the count of elements in their left branch respectively.

Such a data structure should be useful in text editors, as the user obviously can insert text anywhere in the document and yet the editor is supposed to render a screenfull of text around a given location quickly as well.

My question: What's this data structure called? Is there a buzzword I can google? (Such as "B-tree", "red-black tree", etc. for key-ordered search trees?)

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I'm confused. To me, "zero-based" just means "the index of the first element is zero rather than, say, one". And when you say that you want to implement an array as a tree, to me that's not implementing an array: it's implementing a tree, which is a completely different data structure. It's a bit like saying that you're going to implement a bicycle that has four wheels and an engine. Well, fine, but that's not a bicycle any more. $\endgroup$
    – David Richerby
    Jun 21, 2016 at 19:19
  • $\begingroup$ I don't think the nomenclature is a precise as you claim it to be. Even dictionaries are sometimes called "arrays". I meant array as in "keyed by consecutive integers, designed for efficient lookup by index". $\endgroup$
    – John
    Jun 21, 2016 at 19:25
  • $\begingroup$ What he said (@David) and the title is not only not the best one, but adresses the part of question. Also question is about data structure with given properties and the second one is about the best fitting structure for the text editor, which might be the same, but looking at the answers it isn't. $\endgroup$
    – Evil
    Jun 21, 2016 at 19:26
  • $\begingroup$ @EvilJS Why? A rope has the properties I described. It's also a fitting buzzword, even though it's associated with characters. $\endgroup$
    – John
    Jun 21, 2016 at 19:28
  • $\begingroup$ Mhm. Ok, it is very good that it helps. $\endgroup$
    – Evil
    Jun 21, 2016 at 19:31

3 Answers 3

Reset to default
4
$\begingroup$

All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-1$ to represent NULL.

In general, the best kind of structure to look for (and to arrayify if that is what you want to do) is a rope, which is a stronger kind of string (see Wikipedia). Ropes are designed for exactly this purpose.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I remember having heard about ropes before now, thanks a bunch. $\endgroup$
    – John
    Jun 21, 2016 at 19:20
2
$\begingroup$

The simplest approach is this: Take any search tree data structure (be it AVL trees, Red-Black trees, even B-trees), and store in each node one additional piece of information: The "size" of the node, that is, the number of elements stored in the node and its children. It's trivial to find the nth element in a tree if you have that information.

Since you're storing that information anyway, you may as well use some variant of weight-balanced trees, which have the nice property that the size information is precisely what they need to maintain their balance conditions. Two birds, one stone.

Having said that, I think Martin is correct that something like ropes, gap buffers, or enfilades would be better if you were actually implementing a text editor, because that's what they're designed for.

Improve this answer
$\endgroup$
0
$\begingroup$

The structure that performs given operations in logarithmic time would be AVL tree or RB (red-black) tree with additional pointers for next and previous, which will be called augmented tree, more precisely doubly threaded.
The choice between AVL and RB depends on dominating operations or size (if dominating operation is search or the size of data is hige then AVL is better).
Left thread keeps inorder predecessor and right keeps inorder successor. The memory footprint will increase and insert operation will take more time, but prev/next will be constant time.
Alternative that you may find is tempting - keeping you might keep root pointer from node and traversing up and then performing search, it decreases memory footprint but in return you have to compare with root everytime and for example access to roots predecessor is just search from root.

About keeping element index in the sorted list count of elements i this will be Order statistic tree.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Just picking a nit here: The choice between AVL, Red-Black trees, or any other balanced tree implementation is interesting theoretically, but almost completely arbitrary from a practical point of view. When you actually measure the difference between them, it's sampling error. So the purpose of balancing a BST, it would seem, is to avoid pathological behaviour. $\endgroup$
    – Pseudonym
    Jun 23, 2016 at 22:39
  • $\begingroup$ @Pseudonym well, I have tested such "nits" and I have encountered such behavior - for small data negligible, for bigger it makes a big difference. BTW besides the ropes we have quite similar answer. $\endgroup$
    – Evil
    Jun 23, 2016 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.