Better than both a linked list and a deque!
Moderators: phlip, Moderators General, Prelates
Better than both a linked list and a deque!
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.
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 =~
 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!
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
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you
Re: Better than both a linked list and a deque!
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++.
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 =~
Re: Better than both a linked list and a deque!
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.
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.
Re: Better than both a linked list and a deque!
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 =~
 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!
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(e^{n!}) randomaccess 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 randomaccess, 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) worstcase (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.
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) worstcase (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)⚠);}
Re: Better than both a linked list and a deque!
phlip wrote:Incidentally: if I'm understanding right, iteration is O(log n) worstcase (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).
 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!
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 perfectlybalanced 2^{n}leaf tree) is moving from node 2^{n1}1 to 2^{n1}, 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 perfectlybalanced 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?
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 perfectlybalanced 2^{n}leaf tree) is moving from node 2^{n1}1 to 2^{n1}, 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 perfectlybalanced 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)⚠);}
Re: Better than both a linked list and a deque!
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.
Re: Better than both a linked list and a deque!
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 (2n1)*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 =~
Re: Better than both a linked list and a deque!
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.
 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!
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)⚠);}
Re: Better than both a linked list and a deque!
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.
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.
~= scwizard =~
Re: Better than both a linked list and a deque!
scwizard wrote:No, the entire data structure takes up (2n1)*sizeof(wood) + sizeof(Shrub).
But yeah, my bad, should really learn to not think before coffee. Size of data structure is (n + (2n1)) 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.
Re: Better than both a linked list and a deque!
0xBADFEED wrote:scwizard wrote:No, the entire data structure takes up (2n1)*sizeof(wood) + sizeof(Shrub).
Size of data structure is (n + (2n1)) 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 =~
Re: Better than both a linked list and a deque!
This actually has some structural similarities to a skiplist. It's sort of like a skiplist 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?
Re: Better than both a linked list and a deque!
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 =~
Re: Better than both a linked list and a deque!
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, skiplists actually work based on storing multiple sorted lists and have an element of probability involved. I meant a jumplist.
Re: Better than both a linked list and a deque!
I don't know much about jump lists. What is the point of them anyway? What are they good at?
~= scwizard =~
Re: Better than both a linked list and a deque!
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 leapfrog 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 jumpnetwork that take you to the index that you requested. It's not really that close structurally just the idea.
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 jumpnetwork that take you to the index that you requested. It's not really that close structurally just the idea.

 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!
I think that this is roughly "what people did before they had skiplists".
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) worstcase 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.
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) worstcase 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.
Re: Better than both a linked list and a deque!
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.
A shrub is a unsorted sequence container with index based access.
~= scwizard =~
Re: Better than both a linked list and a deque!
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.
#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 =~
 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!
*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.
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Better than both a linked list and a deque!
Insertion and Deletion are more expensive than [imath]O(\log{n})[/imath]. You are forgetting the cost to maintain the "shrub's" balance.
 Byron
 Byron
 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!
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.
Re: Better than both a linked list and a deque!
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.
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.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.
~= scwizard =~
Re: Better than both a linked list and a deque!
I think we could do better. We could probably get some of those things down to O(1) if we thought about it enough.
Re: Better than both a linked list and a deque!
Isn't what you've described just an AVLTree?
Edit: Okay, it's not, I missed a kinda important detail
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.
Edit: Okay, it's not, I missed a kinda important detail
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 { } \ ; )
Re: Better than both a linked list and a deque!
akashra wrote:Isn't what you've described just an AVLTree?
What is an AVLTree?
Re: Better than both a linked list and a deque!
( find / name \*base\* exec chown us : us { } \ ; )
Re: Better than both a linked list and a deque!
Duh, my bad. When you mentioned it I tried searching Wikipedia for it, but I didn't have the space.
That's pretty cool.
That's pretty cool.
Re: Better than both a linked list and a deque!
akashra wrote:Isn't what you've described just an AVLTree?
OOPS: Okay, it's not, I missed a kinda important detail
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 =~
 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!
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.
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Better than both a linked list and a deque!
Well the way I do it is thus:
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.
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 =~
 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!
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).
(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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Better than both a linked list and a deque!
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 redblack trees, but perhaps not as simple as splay trees.
Re: Better than both a linked list and a deque!
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 =~
 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!
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.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Better than both a linked list and a deque!
Huh? I don't follow. What do you mean by "append the counter" for instance?
~= scwizard =~
Who is online
Users browsing this forum: No registered users and 5 guests