Binary Search Trees

[xcessive]

Red-Black, AVL, B or Splay.

This is the computer science equivalent of the "OS" war threads.

Splay trees with immutable tree nodes gets my vote.

[Jordan]

It depends on what you are doing to be honest. I've only coded an AVL Tree, but the STL in C++ uses Red-Black trees since the balancing isn't quite as strict. B-Trees are good for storing data on disc, and splay trees are obviously the best when you are using the same data over and over. So...I don't have a favorite.

[xcessive]

Jun 14, 2011 2:36:07 GMT Jordan said:

It depends on what you are doing to be honest. I've only coded an AVL Tree, but the STL in C++ uses Red-Black trees since the balancing isn't quite as strict. B-Trees are good for storing data on disc, and splay trees are obviously the best when you are using the same data over and over. So...I don't have a favorite.

Boring pointless rant part of post:
Most people tend to say this, but its only true to an extent. AVL trees and red-black trees do exactly the same thing, using a different algorithm. They both give the same time and memory complexity, its a matter of what you'd rather code. Splay trees are slightly different, and if you wanted to use a subset over and over, why wouldn't you just use a hashtable? Splay trees are more a sacrifice between speed and concurrency, with the added bonus of having commonly used items in O(1) time. B-Trees are block based, so they always win for storing to disc since they can be read byte by byte, but they can compete with AVL and RB trees if you only ever use left (or right) complete trees - in which case you often get amortized O(1) time for some things.

Relevant part of post:
But I digress, the point of this thread is which do you find more interesting not much useful, since in computer science thats context dependent 99% of the time.

[Jordan]

Hmmm, hard to say since they are all interesting. ;P

Honestly, I'd have to say the splay trees are the most interesting since the most used items rise to the top. It's just a really cool idea and if implemented and used correctly could probably be useful, although hash tables are usually going to be a better choice like the quote above said. I just like the idea of trying to be as clever and efficient as possible.

[xcessive]

Jun 17, 2011 2:06:52 GMT Jordan said:

Hmmm, hard to say since they are all interesting. ;P

Honestly, I'd have to say the splay trees are the most interesting since the most used items rise to the top. It's just a really cool idea and if implemented and used correctly could probably be useful, although hash tables are usually going to be a better choice like the quote above said. I just like the idea of trying to be as clever and efficient as possible.

That was just me ranting, not a quote.

In my opinion people use hash tables way too much. As a great programmer once told me "Hash can be addictive". I actually did an implementation of a splay tree with immutable tree nodes as an experiment. It gives the same performance as a normal splay tree, but cloning is O(1), meaning it can be used concurrently by many threads/users.

[xcessive]

Why can't more people here talk about computer science..?

[Jordan]

I think we are the only ones on here who are computer science majors. I also took my data structures class last year (I'm assuming you are taking yours now), so not everything is fresh on my mind.

[xcessive]

Nope, took it last year. Its just very salient at the moment since I am training to compete in the ICFP (although I doubt I'll even qualify since Australia only gets 1 entry slot and the other team at my uni came 2nd in the world last year, which is fucking ridiculous).

[Jordan]

Jun 25, 2011 0:53:58 GMT xcessive said:

Nope, took it last year. Its just very salient at the moment since I am training to compete in the ICFP (although I doubt I'll even qualify since Australia only gets 1 entry slot and the other team at my uni came 2nd in the world last year, which is fucking ridiculous).

Wow, that is fucking ridiculous and I really mean that. You guys must all be pretty smart, though, I've noticed that you are much smarter than the average student where I'm from (and I consider myself slightly above average).

[xcessive]

Jun 25, 2011 3:08:02 GMT Jordan said:

Jun 25, 2011 0:53:58 GMT xcessive said:

Nope, took it last year. Its just very salient at the moment since I am training to compete in the ICFP (although I doubt I'll even qualify since Australia only gets 1 entry slot and the other team at my uni came 2nd in the world last year, which is fucking ridiculous).

Wow, that is fucking ridiculous and I really mean that. You guys must all be pretty smart, though, I've noticed that you are much smarter than the average student where I'm from (and I consider myself slightly above average).

Without a doubt, its the lecturers! For example one of them was involved in writing the optimizer portion of the G++ compiler, and another came up with the non-exponential solution to the traveling salesman problem. When you have people like that educating you, it makes you want to enter these competitions and train really hard.

[Cam]

I would be interested to learn what this is

[xcessive]

We're talking about specialized implementations of binary search trees.

Binary search trees a like family trees, but every "node" only has two "descendants". In typical implementations theses descendants can be valid nodes, or null points for the "end nodes". The special thing about binary search trees is that for each node, the left child is "less" than the node, and the right child is "greater" than the current node. This makes searching really fast. In fact it makes it ~log n time where n is the number of non-external (null) nodes.

EDIT: Damn whitespace striping.

What we're talking about are special versions of these that rebalance themselves after you add or delete items, making sure you dont get an inefficient tree, that only has left children - for example.
en.wikipedia.org/wiki/Binary_search_tree

[Cam]

I'll read up on it, thanks for clarifying what it is for me