Better than both a linked list and a deque!

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Better than both a linked list and a deque!

Postby scwizard » Thu Feb 19, 2009 11:10 pm UTC

I've discovered that if you take a (self balancing) tree, put the data on its leaves and then make the forks keep track of how many leaves are below to each side of them, then you get a sequence container with the following efficiencies:
Get data by index: O(log n)
Insert data by index: O(log n)
Delete data by index: O(log n)
Iterate over the elements in forward or reverse order: O(1)
Insertion or deletion by iterator is also O(log n), but is slightly faster than by index.

NEW: The complete (I think), but of course imperfect, implementation is here: http://codepad.org/4IB8UtH9

Now for a inserting data by index, you need to both "access an element in the middle using only its index" and "insert into the middle of the deque." Now according to wikipedia for both implementations of a deque, at least one of these will be O(n).
In fact I don't know of any other sequence container that allows for O(log n) insertion by index, this might be the only one.

Now the biggest disadvantage of this data structure, is that push_front, push_back, pop_front and pop_back all take O(log n).

I suggest we call this data structure a shrub (or a shrubbery if you're coding in python). Also I wonder why the C++ standard library doesn't provide a data structure like this.
Last edited by scwizard on Sun Mar 01, 2009 4:23 am UTC, edited 2 times in total.
~= scwizard =~

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Better than both a linked list and a deque!

Postby headprogrammingczar » Fri Feb 20, 2009 1:31 am UTC

scwizard wrote:I've discovered that if you take a (self balancing) tree, put the data on its leafs and then make the forks keep track of how many leafs are below to each side of them, then you get a sequence container with the following efficiencies:
Get data by index: O(log n)
Insert data by index: O(log n)
Delete data by index: O(log n)
Iterate over the elements in forward or reverse order: O(1)
Insertion or deletion by iterator is also O(log n), but is slightly faster than by index.

Now for a inserting data by index, you need to both "access an element in the middle using only its index" and "insert into the middle of the deque." Now according to wikipedia for both implementations of a deque, at least one of these will be O(n).
In fact I don't know of any other sequence container that allows for O(log n) insertion by index, this might be the only one.

Now the biggest disadvantage of this data structure, is that push_front, push_back, pop_front and pop_back all take O(log n).

I suggest we call this data structure a shrub (or a shrubbery if you're coding in python). Also I wonder why the C++ standard library doesn't provide a data structure like this.

I like this idea. Also, iteration would be O(n), I think.
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 2:21 am UTC

O(1) per iteration. If you perform n iterations (iterating over the entire structure) then you have O(1) * n = O(n).
What I'm saying is that the leaves are linked at the bottom in the fashion of a linked list, so you don't need to start at the top of the tree to get the next element.
Anyways, I've attached a proof of concept for this written in C++.
Attachments
shrub.zip
(2.07 KiB) Downloaded 61 times
~= scwizard =~

Shriike
Posts: 127
Joined: Mon Jan 26, 2009 3:27 am UTC
Location: Ohio

Re: Better than both a linked list and a deque!

Postby Shriike » Fri Feb 20, 2009 2:56 am UTC

I'm sorry, maybe it's just me but I fail to see how this would be more useful then a deque or a linked list.

Pushing onto either side of a deque (or popping off) should be O(1) if I'm not mistaken. Accessing a point in the middle should be impossible.

A List adding by index should be O(log n), getting dat aby index should be O(log n), deleting data by index should be O(log n).

Maybe I'm just mis informed though.

Edit:
Sorry I forgot to mention, what I said would only hold to be true about a linked list if it's double linked.

One more Edit:
Ok I may be on crazy pills or something, go ahead and replace every time I said O(log n) with O(n).
somehow I confused log n, with n/2.....I haven't slept enough recently.
Image

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 4:57 am UTC

Shriike wrote:I'm sorry, maybe it's just me but I fail to see how this would be more useful then a deque or a linked list.

Pushing onto either side of a deque (or popping off) should be O(1) if I'm not mistaken. Accessing a point in the middle should be impossible.

You sound very confused here...
~= scwizard =~

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Better than both a linked list and a deque!

Postby phlip » Fri Feb 20, 2009 5:26 am UTC

He's just saying, if you want it to use some data structure as a deque, having push and pop be constant time is more important than any of the other things you've given a time for... hell, if you're using it as a deque, an implementation that has O(1) pushes and pops, but O(en!) random-access or something (essentially impossible, something you'd want to never have to do), is still often going to be better, since you'll often never use the random-access, but you'll use pushes and pops all the time.

In short: In certain situations, your data structure is better than the standard deque implementations... but the situations you'd usually use a deque are not among them. Certainly, if you have some situation where you want to do a lot of inserting by index, this data structure could be very useful... but to call it "better than a deque" in general is simply not the case.

Incidentally: if I'm understanding right, iteration is O(log n) worst-case (and you will have at least one worst case while iterating through the whole tree), though I'm pretty sure it's amortised constant time over a full iteration.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Better than both a linked list and a deque!

Postby Carnildo » Fri Feb 20, 2009 10:04 am UTC

phlip wrote:Incidentally: if I'm understanding right, iteration is O(log n) worst-case (and you will have at least one worst case while iterating through the whole tree), though I'm pretty sure it's amortised constant time over a full iteration.


I think iterating through the whole tree is O(n log n), which makes the amortized cost of a single step O((log n)/n).

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Better than both a linked list and a deque!

Postby phlip » Fri Feb 20, 2009 11:16 am UTC

scwizard's sample implementation doesn't seem to have an iterate function (I don't see one, at least, maybe I'm missing it...) but consider this algorithm:

The iterator stores a pointer to the current leaf node. iterator++ is:
Move to the parent node
If we came to the parent node from the right child, then continue travelling up the tree until either we come to a parent node from the left child, or reach the root. If we reach the root from the right child, then we're at the end of the tree (move the iterator to some special invalid value that'd be returned by end()). Otherwise, go on to the next step.
From the first parent we approached from the left, move to the right child. Then continually move to left child until we reach a leaf node. That leaf node holds our next value.

The running time for this is proportional to the height of the subtree navigated... that is, the distance between leaf i and leaf i+1, and their common root. The worst case (for a perfectly-balanced 2n-leaf tree) is moving from node 2n-1-1 to 2n-1, which has to go through the root node... n steps up and n down. Linear on the height, so logarithmic on the number of leaves.

However, not all of the steps will take that full time... indeed, half of them will only require going one step up, and one step down. Around a quarter (exactly a quarter for a perfectly-balanced tree, though less if the tree is imbalanced, if the number of leaves isn't a power of 2) will take two steps up and two down. Around 1/8 will take 3 steps each way. And so on. So our amortised time is proportional to 1/2 + 2/4 + 3/8 + ... with log n terms. This sequence is bounded... in the limit, it tends to 2. So it's O(1). Iterating through the whole tree should be O(n).

Incidentally, I'm not sure how you went from O(n log n), your value for the full iteration, to O (log n / n), your value for one step... surely you should only divide by n once? And surely log n / n decreases with n?

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Better than both a linked list and a deque!

Postby 0xBADFEED » Fri Feb 20, 2009 2:21 pm UTC

There is also an O(n log n) memory requirement for the datastructure. This makes it quite hefty compared to most other generic collection types.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 3:09 pm UTC

phlip wrote:scwizard's sample implementation doesn't seem to have an iterate function

The nodes at the bottom are stored in the fashion of a linked list. If you have a Leaf named CurrentLeaf, then the next leaf is stored in CurrentLeaf->Right.Leaf and the previous leaf is stored in CurrentLeaf->Prev.Leaf. No need to go up and down the shrub.

I will add in iterator functionality once I figure out the proper way to implement custom C++ iterators. However even though there is no function to do it yet, when there is, iteration will be just as fast as it is in a double linked list.

0xBADFEED wrote:There is also an O(n log n) memory requirement for the datastructure. This makes it quite hefty compared to most other generic collection types.

No, the entire data structure takes up (2n-1)*sizeof(wood) + sizeof(Shrub).
This can be seen because the insert function goes:
Wood* LeafToInsert = new Wood;
Wood* ForkToInsert = new Wood;
In the general case, and:
Wood* InitialLeaf = new Wood;
When you add the first element.

phlip wrote:Certainly, if you have some situation where you want to do a lot of inserting by index, this data structure could be very useful... but to call it "better than a deque" in general is simply not the case.

Of course it's not strictly better than a deque or a linked list, that was just me exaggerating.
~= scwizard =~

Shriike
Posts: 127
Joined: Mon Jan 26, 2009 3:27 am UTC
Location: Ohio

Re: Better than both a linked list and a deque!

Postby Shriike » Fri Feb 20, 2009 3:26 pm UTC

phlip wrote:He's just saying, if you want it to use some data structure as a deque, having push and pop be constant time is more important than any of the other things you've given a time for


Thanks for defending me Phlip, you got what I was saying perfectly.
Image

User avatar
phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Better than both a linked list and a deque!

Postby phlip » Fri Feb 20, 2009 3:38 pm UTC

scwizard wrote:The nodes at the bottom are stored in the fashion of a linked list. If you have a Leaf named CurrentLeaf, then the next leaf is stored in CurrentLeaf->Right.Leaf and the previous leaf is stored in CurrentLeaf->Prev.Leaf. No need to go up and down the shrub.

Ah, I didn't spot that (I haven't looked at your code that closely... just skimmed it, looking for some iterating function). That makes sense, and, yes, is clearly O(1).

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 3:40 pm UTC

You were saying the same thing as him? It sounded like you were saying something different and wrong, while he was saying something correct and that I was already aware of.

Anyways the correct title of this topic is "Better than both a linked list and a deque at inserting and deleting elements by index." (Should I change it to be less provocative and more correct phlip?) If you're not going to insert or delete elements by index, then there are better data structures out there for your purposes. However a shrub is better than any sequence containers I know of out there at inserting and deleting elements by index (and it does it without introducing any operations that take O(n)), and that should count for something.

Re: phlip, glad to see that that's cleared up.

Also here's a pretty picture of the structure.
Image
~= scwizard =~

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Better than both a linked list and a deque!

Postby 0xBADFEED » Fri Feb 20, 2009 4:00 pm UTC

scwizard wrote:No, the entire data structure takes up (2n-1)*sizeof(wood) + sizeof(Shrub).

But yeah, my bad, should really learn to not think before coffee. Size of data structure is (n + (2n-1)) for fully populated tree. That was just embarrassing. My brain must be taking the day off.
Last edited by 0xBADFEED on Fri Feb 20, 2009 4:18 pm UTC, edited 2 times in total.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 4:16 pm UTC

0xBADFEED wrote:
scwizard wrote:No, the entire data structure takes up (2n-1)*sizeof(wood) + sizeof(Shrub).

Size of data structure is (n + (2n-1)) for fully populated tree.

Well all shrubs are "fully populated" meaning each parent has two children.

The size of a shrub in this implementation is exactly: 56n - 25 bytes for n > 0 and 3 bytes for n = 0 (assuming 32 bit ints and pointers)
Last edited by scwizard on Fri Feb 20, 2009 4:26 pm UTC, edited 2 times in total.
~= scwizard =~

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Better than both a linked list and a deque!

Postby 0xBADFEED » Fri Feb 20, 2009 4:19 pm UTC

This actually has some structural similarities to a skip-list. It's sort of like a skip-list but with a skip network built on top. I would be surprised if this not already a standard data structure whose name is escaping everyone. Does anyone know?

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 4:23 pm UTC

I'm pretty sure that skip lists work using key value pairs (like a traditional binary search tree) instead of being accessed by index.
~= scwizard =~

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Better than both a linked list and a deque!

Postby 0xBADFEED » Fri Feb 20, 2009 5:02 pm UTC

scwizard wrote:I'm pretty sure that skip lists work using key value pairs (like a traditional binary search tree) instead of being accessed by index.


Sorry I misspoke, skip-lists actually work based on storing multiple sorted lists and have an element of probability involved. I meant a jump-list.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 6:18 pm UTC

I don't know much about jump lists. What is the point of them anyway? What are they good at?
~= scwizard =~

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Better than both a linked list and a deque!

Postby 0xBADFEED » Fri Feb 20, 2009 7:59 pm UTC

Mostly the same things that linked lists are good for in general. It just maintains extra forward links in geometrically increasing intervals to speed up searching and retrieval. Basically that let you leap-frog over large portions of the list to find the index that you want.

I've never actually had cause to use them. I was just thinking if you view the shrub as starting from the head node at the bottom then its parent links are like a jump-network that take you to the index that you requested. It's not really that close structurally just the idea.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

Re: Better than both a linked list and a deque!

Postby stephentyrone » Fri Feb 20, 2009 8:59 pm UTC

I think that this is roughly "what people did before they had skip-lists".

If I'm remembering things correctly, skip lists give you the same (average) complexities, use less storage and are have smaller constants (but the same complexity) for insertion and deletion at an index, at the cost of being randomized and having O(n) worst-case behavior for some operations.

I could be entirely wrong though, since it's been a very long time since I last had to think about this sort of structure.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 20, 2009 9:23 pm UTC

Skip lists are not sequence containers. Skips lists are sorted containers with key based access.

A shrub is a unsorted sequence container with index based access.
~= scwizard =~

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Wed Feb 25, 2009 5:15 am UTC

A more complete implementation.

#define nullptr 0
#define EVER ;;
#define INHERITS_FROM :

Right now it's unsafe, but if you want to make it safe and throw exceptions and such, all you need to do is make its iterator checked. All the potentially unsafe functions go through the iterator.
Attachments
shrub.7z
(2.52 KiB) Downloaded 42 times
~= scwizard =~

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Better than both a linked list and a deque!

Postby Yakk » Wed Feb 25, 2009 7:14 pm UTC

*nod*, I was looking for an implementation of this from boost a bit ago. boost's multi index fails to provide it as an option, as far as I can tell.

For a practical, common use, this is the ideal data structure to store a model backend for a large scrolled list view.

You have fast random access by index, stable iterators, fast insert and remove from the middle of the list, etc.

If you have ever had an email application 'lock up' when working on a large inbox, you are seeing the O(n) or worse behaviour problem of using a standard data structure for this problem.

scwizard, when did you run into the structure? I was looking for an already implemented one about a month ago.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

byron
Posts: 1
Joined: Thu Feb 26, 2009 12:11 am UTC

Re: Better than both a linked list and a deque!

Postby byron » Thu Feb 26, 2009 12:15 am UTC

Insertion and Deletion are more expensive than [imath]O(\log{n})[/imath]. You are forgetting the cost to maintain the "shrub's" balance.

- Byron

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Better than both a linked list and a deque!

Postby Berengal » Thu Feb 26, 2009 12:54 am UTC

Is that done on each update, is it dependant on n and isn't it amortized away?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Thu Feb 26, 2009 1:08 am UTC

Yakk wrote:scwizard, when did you run into the structure? I was looking for an already implemented one about a month ago.

The idea struck me and I implemented it. I didn't take it from anywhere. I was thinking "how would you go about implementing a tree using indices instead of key value pairs?" and this is the solution I came up with.

byron wrote:Insertion and Deletion are more expensive than [imath]O(\log{n})[/imath]. You are forgetting the cost to maintain the "shrub's" balance.
The UpdateShrub() (which includes balancing) is what takes O(log n). It's the reason insertion to the end is O(log n) time instead of O(1) time. Insertion into the middle is also O(log n). O(log n) to get the leaf in the middle you want to insert behind, O(1) to insert it and O(log n) to update the shrub.
~= scwizard =~

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Better than both a linked list and a deque!

Postby quintopia » Thu Feb 26, 2009 2:47 am UTC

I think we could do better. We could probably get some of those things down to O(1) if we thought about it enough.

akashra
Posts: 503
Joined: Tue Jan 01, 2008 6:54 am UTC
Location: Melbourne, AU
Contact:

Re: Better than both a linked list and a deque!

Postby akashra » Thu Feb 26, 2009 3:21 am UTC

Isn't what you've described just an AVLTree?

Edit: Okay, it's not, I missed a kinda important detail :P
However, probably the reason it's not done is because you're adding n bytes for every node. That might be more data than you want to store, when you're already storing sizeof(void *)*4 for each node.
( find / -name \*base\* -exec chown us : us { } \ ; )

Shriike
Posts: 127
Joined: Mon Jan 26, 2009 3:27 am UTC
Location: Ohio

Re: Better than both a linked list and a deque!

Postby Shriike » Thu Feb 26, 2009 3:33 am UTC

akashra wrote:Isn't what you've described just an AVLTree?


What is an AVLTree?
Image

akashra
Posts: 503
Joined: Tue Jan 01, 2008 6:54 am UTC
Location: Melbourne, AU
Contact:

Re: Better than both a linked list and a deque!

Postby akashra » Thu Feb 26, 2009 3:38 am UTC

( find / -name \*base\* -exec chown us : us { } \ ; )

Shriike
Posts: 127
Joined: Mon Jan 26, 2009 3:27 am UTC
Location: Ohio

Re: Better than both a linked list and a deque!

Postby Shriike » Thu Feb 26, 2009 4:14 am UTC

Duh, my bad. When you mentioned it I tried searching Wikipedia for it, but I didn't have the space.

That's pretty cool.
Image

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Thu Feb 26, 2009 4:29 pm UTC

akashra wrote:Isn't what you've described just an AVLTree?

OOPS: Okay, it's not, I missed a kinda important detail :P
However, probably the reason it's not done is because you're adding n bytes for every node. That might be more data than you want to store, when you're already storing sizeof(void *)*4 for each node.

It seems that it balances itself in a way similar to an AVL tree I think. I'll read over the wikipedia article and see if it gives me any pointers for optimizing my balancing.

Ya, its structure forces the tree to store pointers to data instead of the actual data itself.

Size is an issue, compared to an array it can take up megabytes more in structure for large sets of data. The idea of having this data structure is to increase options though. If while you're profiling you find that speed is an issue for some operations that you're performing, you can use this, and if you find that memory is an issue you can use something else.
~= scwizard =~

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Better than both a linked list and a deque!

Postby Yakk » Thu Feb 26, 2009 8:27 pm UTC

Self balancing part is the rub.

Do you use any of the standard techniques, or do you attempt to balance based off of the element count on the right/left?

I attempted to prove that a naive "keeping things balanced' wouldn't have a blow up in balancing costs, but failed. Am I just screwing up the algorithmics?

I even attempted to do an analysis based on a 'good enough' balanced tree -- where you let the nodes become unbalanced up to a factor of 2 (or G, the golden ratio), and got lost in the algebra before I could prove that it was reasonably efficient.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 27, 2009 2:27 am UTC

Well the way I do it is thus:

Code: Select all

if(Crawler->NumberOfLeavesToTheLeft > Crawler->NumberOfLeavesToTheRight) {
   RotateRight(Crawler);
   Crawler = Crawler->Parent;
}
else if(Crawler->NumberOfLeavesToTheRight > Crawler->NumberOfLeavesToTheLeft) {
   RotateLeft(Crawler);
   Crawler = Crawler->Parent;
}
else {
   continue;
}

That has nothing to do with it being the best balancing technique though, and everything to do with laziness (it was the easiest way). I figure I shouldn't get ahead of myself and try to make balancing particularly efficient. After all you optimize after you profile and not before.
~= scwizard =~

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Better than both a linked list and a deque!

Postby Yakk » Fri Feb 27, 2009 5:07 am UTC

How do you know that both your operation results in things being balanced, and that it takes O(lg n) time?

(What is worse is that you are rebalancing every node from the leaf on up -- so you are balancing lg n nodes, so they have to take an average of O(1) time each).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Better than both a linked list and a deque!

Postby quintopia » Fri Feb 27, 2009 5:40 am UTC

That is the standard (AVL tree) way of balancing and it does use O(lg n) steps, which is why you damn well better only require it in operations which already take O(lg n). It's much simpler than red-black trees, but perhaps not as simple as splay trees.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 27, 2009 5:48 am UTC

quintopia wrote:That is the standard (AVL tree) way of balancing and it does use O(lg n) steps, which is why you damn well better only require it in operations which already take O(lg n). It's much simpler than red-<colour not needed due to Fat Tony's birth> trees, but perhaps not as simple as splay trees.

I only require it in operation that already take O(log n). Insertion (even onto the front) will be O(log n) no matter what in a shrub because it needs to crawl back upwards and update NumberOfLeavesToThe(Left/Right).
~= scwizard =~

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Better than both a linked list and a deque!

Postby Yakk » Fri Feb 27, 2009 2:25 pm UTC

So you implement an AVL tree, use it for balancing, then append the counter and don't use it for anything other than fast lookup by index?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Better than both a linked list and a deque!

Postby scwizard » Fri Feb 27, 2009 3:03 pm UTC

Huh? I don't follow. What do you mean by "append the counter" for instance?
~= scwizard =~


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests