0835: "Tree"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
LucasBrown
Posts: 299
Joined: Thu Apr 15, 2010 2:57 am UTC
Location: Poway, CA

0835: "Tree"

Postby LucasBrown » Fri Dec 17, 2010 5:00 am UTC

Image
Alt text: "Not only is that terrible in general, but you just KNOW Billy's going to open the root present first, and then everyone will have to wait while the heap is rebuilt."

GOOMHR--I have considered doing that.

User avatar
torontoraptor
Posts: 442
Joined: Sun Apr 12, 2009 11:58 pm UTC

Re: 0835: "Tree"

Postby torontoraptor » Fri Dec 17, 2010 5:03 am UTC

And the day of my programming exam too!
Promicin wrote:Now if I can just grab on with my tongue-like foot... wait. I am not a mussel.

pseudoidiot wrote:
You, sir, name? wrote:fucking owls is enjoyable.
Someone should sig this

User avatar
hintss
Posts: 1294
Joined: Wed Nov 25, 2009 7:19 am UTC
Contact:

Re: 0835: "Tree"

Postby hintss » Fri Dec 17, 2010 5:05 am UTC

I kinda get it after a google search

now back to searching for other arduino related stuff

black_hat_guy
Posts: 111
Joined: Tue Jul 20, 2010 8:34 pm UTC

Re: 0835: "Tree"

Postby black_hat_guy » Fri Dec 17, 2010 5:07 am UTC

Recently, I put a tree ornament on our Christmas tree and hung a small bead next to it and resting on it, so it looked like an ornament on the tree-within-a-tree. Later I put up another tree ornament and did the same thing, plus I happened to find one that was a star within a star to put above it.
Billy was a chemist.
He isn't any more.
What he thought was H2O
was H2SO4.

User avatar
glasnt
Posts: 539
Joined: Fri Jan 25, 2008 5:18 am UTC
Location: SQUEE!

Re: 0835: "Tree"

Postby glasnt » Fri Dec 17, 2010 5:10 am UTC

At least his parents didn't think he was on drugs by creating a "hash" table of "gifts"

I'm here all week.

User avatar
cjmcjmcjmcjm
Posts: 1158
Joined: Tue Jan 05, 2010 5:15 am UTC
Location: Anywhere the internet is strong

Re: 0835: "Tree"

Postby cjmcjmcjmcjm » Fri Dec 17, 2010 5:16 am UTC

This one actually made me L.O.L., not lqtm like usual
frezik wrote:Anti-photons move at the speed of dark

DemonDeluxe wrote:Paying to have laws written that allow you to do what you want, is a lot cheaper than paying off the judge every time you want to get away with something shady.

black_hat_guy
Posts: 111
Joined: Tue Jul 20, 2010 8:34 pm UTC

Re: 0835: "Tree"

Postby black_hat_guy » Fri Dec 17, 2010 5:18 am UTC

There is a white triangle underneath the dad's arm. That being said, Randall's stick figures on a gray background are awesome.
Billy was a chemist.
He isn't any more.
What he thought was H2O
was H2SO4.

salynch
Posts: 1
Joined: Fri Dec 17, 2010 5:16 am UTC

Re: 0835: "Tree"

Postby salynch » Fri Dec 17, 2010 5:18 am UTC

cjmcjmcjmcjm wrote:This one actually made me L.O.L., not lqtm like usual


Seconded. I registered to the site just to post in this thread... long time xkcd reader, but I would *love* to see this comic on a Christmas-themed shirt. Absolutely fantastic!

medgno
Posts: 3
Joined: Fri Oct 30, 2009 4:17 pm UTC

Re: 0835: "Tree"

Postby medgno » Fri Dec 17, 2010 5:19 am UTC

I'm just really upset the ornaments don't form a valid red-black tree (or red-green tree, as the case may be). Maybe this is a sign I've been studying too hard for my algorithms test tomorrow.

raj.k
Posts: 3
Joined: Mon Dec 06, 2010 9:44 am UTC

Re: 0835: "Tree"

Postby raj.k » Fri Dec 17, 2010 5:21 am UTC

Brilliant. LOL'd after about 10 seconds of studying it. The gray background is beautifully done.

User avatar
Vnend
Posts: 60
Joined: Thu Oct 30, 2008 5:34 pm UTC

Re: 0835: "Tree"

Postby Vnend » Fri Dec 17, 2010 5:27 am UTC

The alt-text makes this one, for me.

Rilian
Posts: 496
Joined: Mon Sep 10, 2007 1:33 pm UTC

Re: 0835: "Tree"

Postby Rilian » Fri Dec 17, 2010 5:33 am UTC

Someone explain.
And I'm -2.

User avatar
CorruptUser
Posts: 10550
Joined: Fri Nov 06, 2009 10:12 pm UTC

Re: 0835: "Tree"

Postby CorruptUser » Fri Dec 17, 2010 5:34 am UTC

So, are the edges with an unequal number of lights of each side the negative edges?

dtilque
Posts: 150
Joined: Sat Oct 11, 2008 5:53 am UTC
Location: Nogero

Re: 0835: "Tree"

Postby dtilque » Fri Dec 17, 2010 5:39 am UTC

Last edited by dtilque on Fri Dec 17, 2010 5:43 am UTC, edited 1 time in total.
“This world is a strange madhouse. Currently, every coachman and every waiter is debating whether relativity theory is correct. Belief in this matter depends on political party affiliation.”
-- Albert Einstein, 12 September 1920

warspite
Posts: 15
Joined: Fri Mar 19, 2010 5:11 pm UTC

Re: 0835: "Tree"

Postby warspite » Fri Dec 17, 2010 5:42 am UTC

They should have left that child. He isn't the right sibling.

Please someone turn off my internet connection:

-davekov.com

Rilian
Posts: 496
Joined: Mon Sep 10, 2007 1:33 pm UTC

Re: 0835: "Tree"

Postby Rilian » Fri Dec 17, 2010 5:53 am UTC

That doesn't explain how all that stuff is floating or why the parents are pissed off.
And I'm -2.

pegasos989
Posts: 52
Joined: Wed Apr 16, 2008 7:14 am UTC

Re: 0835: "Tree"

Postby pegasos989 » Fri Dec 17, 2010 5:54 am UTC

I stared at the comic for about 5 seconds, before... Well, I didn't lol but I did do all the expressions assosciated with the situations where someone tells so horrible pun that it is awesome. I think that this was good enough to make up for the wikileaks comic.

medgno wrote:I'm just really upset the ornaments don't form a valid red-black tree (or red-green tree, as the case may be). Maybe this is a sign I've been studying too hard for my algorithms test tomorrow.


Are you sure they don't still follow some pattern? If you look at the tree, there is no istance where only the left child would be red: It's always just the right child or both children. Hmm... Perhaps it's just a coincidence.

typo
Posts: 33
Joined: Wed Jun 16, 2010 4:12 pm UTC
Location: East of the Don and west of the Rouge

Re: 0835: "Tree"

Postby typo » Fri Dec 17, 2010 5:55 am UTC

I hope Billy is planning to GC all the dereferenced wrappers later....

Rilian
Posts: 496
Joined: Mon Sep 10, 2007 1:33 pm UTC

Re: 0835: "Tree"

Postby Rilian » Fri Dec 17, 2010 5:58 am UTC

I hope geeks majoring in CS die in a fire.

...jk.
And I'm -2.

pegasos989
Posts: 52
Joined: Wed Apr 16, 2008 7:14 am UTC

Re: 0835: "Tree"

Postby pegasos989 » Fri Dec 17, 2010 5:59 am UTC

Rilian wrote:That doesn't explain how all that stuff is floating or why the parents are pissed off.


Well, I don't think that those are part of the joke. But technically, I guess that trees (and thus also heaps) must float. By definition, the root element (the star or the biggest present) don't have a parent, so they can't be hanging from anything. Then again, the leaf elements can't really accept the floor as their child either. All elements are connected only to their parent and/or children so the tree must float... I believe this is just overthinking it though Randall might actually have gone through a similar thought process when drawing this ("Where do I connect the... Oh, I can't.")

User avatar
Icalasari
Posts: 107
Joined: Wed May 26, 2010 5:11 am UTC

Re: 0835: "Tree"

Postby Icalasari » Fri Dec 17, 2010 6:05 am UTC

...I want to try this now

Duban
Posts: 352
Joined: Fri May 01, 2009 1:22 pm UTC

Re: 0835: "Tree"

Postby Duban » Fri Dec 17, 2010 6:05 am UTC

Oh man, as a CS major I burst into laughter with this one. My side felt like it was about to split. Hilarious lol.

I give it five stars out of five.
It is not the gods I fear. No, It is those who claim to speak for them that concern me.

Uninfinity
Posts: 64
Joined: Wed Aug 25, 2010 8:25 am UTC
Contact:

Re: 0835: "Tree"

Postby Uninfinity » Fri Dec 17, 2010 6:06 am UTC

So THAT'S how anti-gravity works!

taj_mutthall
Posts: 4
Joined: Wed Jul 07, 2010 6:37 pm UTC

Re: 0835: "Tree"

Postby taj_mutthall » Fri Dec 17, 2010 6:08 am UTC

I nearly strangled trying to groan and laugh at the same time, and then went through it all over again with the rollover comment. I'd buy christmas cards with this on it! Of course, not too many--only certain people on my list would truly get the same, er, groan-laugh reaction out of it.

User avatar
Tantarian
Posts: 8
Joined: Sun Mar 30, 2008 4:25 pm UTC
Contact:

Re: 0835: "Tree"

Postby Tantarian » Fri Dec 17, 2010 6:09 am UTC

I love it. Simply hilarious.

Silk_Sk
Posts: 1
Joined: Fri Dec 17, 2010 6:17 am UTC

Re: 0835: "Tree"

Postby Silk_Sk » Fri Dec 17, 2010 6:18 am UTC

Lol nice pentagram at the top.

Kiirani
Posts: 38
Joined: Sat Apr 07, 2007 10:48 am UTC

Re: 0835: "Tree"

Postby Kiirani » Fri Dec 17, 2010 6:27 am UTC

You know, I don't have a lot of space in my apartment, but decorations like this could be attached to the wall...

User avatar
connorsname
Posts: 30
Joined: Wed Sep 05, 2007 7:59 pm UTC

Re: 0835: "Tree"

Postby connorsname » Fri Dec 17, 2010 6:31 am UTC

After just finishing my CSE 232 class yesterday I can fully appreciate this comic. Laughed out loud even.

jpk
Posts: 607
Joined: Sat Nov 13, 2010 7:33 am UTC

Re: 0835: "Tree"

Postby jpk » Fri Dec 17, 2010 6:32 am UTC

I'll never understand how people who don't get this joke find their way to xkcd in the first place.
Shouldn't you folks be off reading Dennis the Menace or something?

premchai21
Posts: 2
Joined: Fri Dec 17, 2010 6:37 am UTC

Re: 0835: "Tree"

Postby premchai21 » Fri Dec 17, 2010 6:52 am UTC

I actually made an implementation of one of these on a MUCK for Generic Winter Holidays a year or two ago!

It was an AA tree, and the ornaments were sorted either lexicographically or lexicographically with the strings reversed. You could add an ornament to the top and it would fall down the branches until it fell into place, or you could search for an ornament to remove. (Duplicates were not allowed; the new one would fall off.) Then if the tree became unbalanced, it would start to sway and ornaments would swing up and down until it was stable again.

All textually, of course, since that was what the environment allowed.

The crazy part was that it was on a Fuzzball MUCK, so I had to write in Fuzzball MPI (imagine an unholy combination of early MUD languages, Tcl, and a dash of Scheme) for it to be portable, and plain MPI used a C-recursive interpreter and wasn't multitasked so it had very strict instruction count limits, but you could schedule strings to be evaluated in the future, so I wrote a small preprocessor that would put a list of MPI snippets on the object and then a little engine that would run N of them at a time (including evaluating jumps between parts of the instruction stream and keeping a call stack in another list and so forth) and be able to pause execution by scheduling the engine to run again one second later, then quitting to let other things execute before it ran out of instructions and got itself killed by a hard error (akin to SIGKILL).

So, uh, yeah. A snippet:

Code: Select all

INSERT:
%% X = new value, Y = tree.
if {eq:nil,{&y}} {jmp:INSERT_HERE}
%% Z = old value
set z {rd:{&y}.VALUE}
if {eq:{&x},{&z}} {jmp:INSERT_NOP}
%% W = direction.
if {lt:{&x},{&z}} {set:w,LEFT} {set:w,RIGHT}
%% INSERT_DIR:
xtell {$}
$ It falls to the {-dir:{&w}}, past {-aan:{-value:{rd:{&y}.VALUE}}}.
%% Z = tree, Y = subtree.
set z {&y}
set y {rd:{&z}.{&w}}
push {&w}
call INSERT {&x}
set w {pop}
%% X = new subtree.
wr {&z}.{&w} {&x}
set x {&z}
%% X = new tree.
INSERT_TAIL:
%% X = tree.
call SKEW {&x}
call SPLIT {&x}
ret {&x}

Wubbles
Posts: 3
Joined: Tue Sep 15, 2009 2:43 am UTC

Re: 0835: "Tree"

Postby Wubbles » Fri Dec 17, 2010 6:56 am UTC

Well, I guess the joke is adequate, as far as contrived puns go.

Rilian
Posts: 496
Joined: Mon Sep 10, 2007 1:33 pm UTC

Re: 0835: "Tree"

Postby Rilian » Fri Dec 17, 2010 7:23 am UTC

jpk wrote:I'll never understand how people who don't get this joke find their way to xkcd in the first place.
Shouldn't you folks be off reading Dennis the Menace or something?

A webcomic of romance,
sarcasm, math, and language

Where does it say "for computer programmers only"?
And I'm -2.

Landak
Posts: 8
Joined: Mon Mar 10, 2008 8:23 am UTC

Re: 0835: "Tree"

Postby Landak » Fri Dec 17, 2010 7:28 am UTC

I quite literally applauded this comic, whilst laughing like a drain. Brilliant. Utterly brilliant.

User avatar
Higgs Boson
Posts: 3
Joined: Mon Mar 15, 2010 4:11 am UTC

Re: 0835: "Tree"

Postby Higgs Boson » Fri Dec 17, 2010 7:35 am UTC

jpk wrote:I'll never understand how people who don't get this joke find their way to xkcd in the first place.
Shouldn't you folks be off reading Dennis the Menace or something?


That's not fair. I didn't get this comic, but I do get and appreciate the overall joke now I've done a few moments of reading. I've been here for years because there are plenty of other comics I do get straight away and enjoy. Not every worthwhile joke in the world is about computer programming. Similarly, not everyone who happens not to be a computer programmer is a simpleton.

jesselong
Posts: 5
Joined: Mon Sep 13, 2010 8:08 am UTC

Re: 0835: "Tree"

Postby jesselong » Fri Dec 17, 2010 7:41 am UTC

The left subtree is horribly unbalanced, as well as the left subtree of the right subtree of root. This makes all operations really slow. Next Christmas, please implement AVL rules. Thanks.

NotAllThere
Posts: 146
Joined: Fri Aug 06, 2010 12:54 pm UTC

Re: 0835: "Tree"

Postby NotAllThere » Fri Dec 17, 2010 7:50 am UTC

I'm still experiencing physical pain from this one.

ow. ow. ow.
yangosplat wrote:So many amazing quotes, so little room in 300 characters!

User avatar
tetsujin
Posts: 426
Joined: Thu Nov 15, 2007 8:34 pm UTC
Location: Massachusetts
Contact:

Re: 0835: "Tree"

Postby tetsujin » Fri Dec 17, 2010 7:53 am UTC

OK, what's up with the heap? The second level has four nodes, and the third level is sparse... It's not a binary heap, I guess... What's that, a skew heap or something? Is there a 4-way variant of that?
---GEC
I want to create a truly new command-line shell for Unix.
Anybody want to place bets on whether I ever get any code written?

jesselong
Posts: 5
Joined: Mon Sep 13, 2010 8:08 am UTC

Re: 0835: "Tree"

Postby jesselong » Fri Dec 17, 2010 7:56 am UTC

pegasos989 wrote:
Rilian wrote:That doesn't explain how all that stuff is floating or why the parents are pissed off.


Well, I don't think that those are part of the joke. But technically, I guess that trees (and thus also heaps) must float. By definition, the root element (the star or the biggest present) don't have a parent, so they can't be hanging from anything. Then again, the leaf elements can't really accept the floor as their child either. All elements are connected only to their parent and/or children so the tree must float... I believe this is just overthinking it though Randall might actually have gone through a similar thought process when drawing this ("Where do I connect the... Oh, I can't.")


Actually, the tree structure should hang off a handle. You should never directly reference the root node, but the handle at which the root node is hung. Why? Because of tree rotation during rebalancing and deleting. Root may change, but the handle/hook off which the root is hung doesn't.

StiKerZ
Posts: 1
Joined: Fri Dec 17, 2010 7:45 am UTC

Re: 0835: "Tree"

Postby StiKerZ » Fri Dec 17, 2010 8:09 am UTC

tetsujin wrote:OK, what's up with the heap? The second level has four nodes, and the third level is sparse... It's not a binary heap, I guess... What's that, a skew heap or something? Is there a 4-way variant of that?

I was going to ask the same thing. I'm only used to working with binary heaps, not really familiar with the other types of heaps. I thought it could be a 4-heap, but that third level isn't complete. Are d-ary trees supposed to be complete?

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: 0835: "Tree"

Postby Max2009 » Fri Dec 17, 2010 8:14 am UTC

jesselong wrote:
pegasos989 wrote:
Rilian wrote:That doesn't explain how all that stuff is floating or why the parents are pissed off.


Well, I don't think that those are part of the joke. But technically, I guess that trees (and thus also heaps) must float. By definition, the root element (the star or the biggest present) don't have a parent, so they can't be hanging from anything. Then again, the leaf elements can't really accept the floor as their child either. All elements are connected only to their parent and/or children so the tree must float... I believe this is just overthinking it though Randall might actually have gone through a similar thought process when drawing this ("Where do I connect the... Oh, I can't.")


Actually, the tree structure should hang off a handle. You should never directly reference the root node, but the handle at which the root node is hung. Why? Because of tree rotation during rebalancing and deleting. Root may change, but the handle/hook off which the root is hung doesn't.

But he clearly isn't doing any tree rotation here, because of the gross imbalance.
Anyway, I once again tested the coffee-proofing of my monitor on this one.
I guess I should hold off on the coffee until after xkcd...
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Google [Bot] and 99 guests