Binary Trees make me sick :(

#51scar the 1Posted 2/24/2013 9:12:25 AM
Skel1 posted...
Linked lists are just nodes and pointers though.


That's not entirely correct. That's how the data is structured in a linked list. But um, isn't the interface also part of what a linked list is?
---
Everything has an end, except for the sausage. It has two.
#52ReconditePhreakPosted 2/24/2013 4:41:48 PM
The performance characteristics of a data structure are a part of what that data structure is. Those Data Structure courses are not just teaching the interface, or how to build them, they're also teaching you to understand performance characteristics, when to use one over the other, and what types of algorithms/operations are the degenerate case for said Data Structure.

It is a gross mischaracterization to simply say they're all "basically a linked list" and then move on.
---
Believes the individuals who report to moderators wish they had more control than they do.
#53SnakePawsPosted 2/25/2013 2:42:05 AM
Yeah, that makes sense. Implementation-wise, it's not too far off point to think of them as extending the idea of a linked list.

But the point of abstract data types is that they provide certain functionality independent of their implementations in the first place.

A list just keeps track of records, a tree may impose a more meaningful or useful structure on those records, as would a heap, a hash-table provides us very fast access times, etc.

Conceptually, they are completely different. Like how a cheetah and a giraffe are different even though both have butt-holes.
#54SnakePawsPosted 2/25/2013 2:52:19 AM
Oh, under that view, it is when we abstract away from their implementation, considering them only conceptually, that we see that they're not "basically linked lists" or whatever.

When we zoom in, or become more concrete, down to the level of considering their implementation, then the fact that many data structures can be implemented using a bunch of nodes and pointers becomes relevant. So either I'm not understanding the guys arguing against skel, or this quote is a little off-point, as it seems to imply that HE is the one being too abstract, when in fact he's being less abstract in considering the implementation of data structures:

ReconditePhreak posted...
http://www.joelonsoftware.com/articles/fog0000000018.html

When you go too far up, abstraction-wise, you run out of oxygen. Sometimes smart thinkers just don't know when to stop, and they create these absurd, all-encompassing, high-level pictures of the universe that are all good and fine, but don't actually mean anything at all.
#55PTP2009Posted 2/25/2013 6:29:22 AM
RP loves to wave around that quote whenever anybody mentions that two things are similar or share common properties. There's nothing wrong with observing that at the bottom layer, all we really have are arrays, pointers, and structs. Nobody's suggesting that different data structures are the same or are interchangeable, of course we know that they have different performance characteristics and that's why they're interesting.

I think it's actually a useful revelation to note that everything is made of arrays and pointers, it helps demystify the field a bit.
#56ReconditePhreakPosted 2/25/2013 7:38:34 AM
Performance characteristics are a part of the interface, it just isn't a part of the type system because it's a runtime detail.

This is why Abstraction can break down even when your type system allows it. That interface that allows you to swap out algorithm X for algorithm Y? Algorithm Y might be unusuable due to being slow. The type system will let you swap it out, but reality won't. Or algorithm Y may be screaming fast, but requires a ridiculous amount of memory and so is unusable on a desktop system for the dataset being worked on. Reality strikes again.

This is the important parts of Data Structure courses. This is why they make you implement them, so you intimately understand why a red-black tree is fast to retrieve, but a little slower to insert, or why a hashtable may be fast to retrieve and fast to insert depending on the bucket fill ratio and the hash algorithm.

It isn't just "hurr durr I have a list and I don't care that prepending causes everything to be copied because it's really an array"
---
Believes the individuals who report to moderators wish they had more control than they do.
#57PTP2009Posted 2/25/2013 8:34:28 AM
It isn't just "hurr durr I have a list and I don't care that prepending causes everything to be copied because it's really an array"

Nobody said that.
#58ReconditePhreakPosted 2/25/2013 8:56:16 AM
I'm struggling to understand how you could quote someone saying that and then claim no one said that.

We gots us a genius here folks!
---
Believes the individuals who report to moderators wish they had more control than they do.
#59scar the 1Posted 2/25/2013 11:19:11 AM
PTP2009 posted...
It isn't just "hurr durr I have a list and I don't care that prepending causes everything to be copied because it's really an array"

Nobody said that.


Skel1 posted...
BewmHedshot posted...
Nah dog, searching my List<BTree<Tuple<Map<string, string>, int>>> only takes O(n^n), it's cool.


List is just just nodes with pointers sequentially

BTree is just nodes with two pointers each, with the pointer dependent on the value of the next node

Tuple is just two values together that's used as one.

Map is just a list that uses a hash function to determine node placement.

It's all just pointers pointers to different things. You can argue how "special" a "balanced tree" is, but it's still just a linked list with some special rules for how pointers point to nodes. It's literally all the same thing.


Emphasis mine.
Granted, RP added some stuff like "hurr durr" and twisted it around a little bit, but Skel did say that it's literally the same thing. So someone argued something here.
---
Everything has an end, except for the sausage. It has two.
#60PTP2009Posted 2/25/2013 11:44:16 AM
Context. Skel's talking about what they're made of, not how they perform.