Binary Trees Revisited

In a previous post, I said that my array-ed BT would only work on a balanced tree. I realize now this is false. It works on any type of tree, there just needs to be checking to make sure a 'node' exists there first.

Also, I've been thinking about how to make a binary tree balance itself. I know that there are probably plenty of data structures and other things already in existence,  but why ruin the fun when I can just think about it first?

So this is how I think it would work:
In the case of a completely skewed tree, you grab the 'middle' node, then from there, you assign that as the root. from the nodes that were higher than that node, you grab the middle of that, and from the lower nodes, the middle of that, those are it's right and left nodes respectively.

In other words, recursively grab the middle of the tree. If you had this:
5
6       this is the left of the middle node
7
8        this is the middle node.
9
10       this is the right of the middle node
11

can you picture it? It's not too hard to code either. The matter is, that that example was a completely skewed tree. But what about if you have a more normal tree? like:
     5
  2     8
1  3      9
               10

I really hope that formats correctly... Anyway, OBVIOUSLY you grab the 9 and throw it where the 8 is and you get a perfectly balanced tree. But what exactly is the thought process?

As a matter of fact, it's the same thing we were doing before, just part of our tree is already balanced, and if you take a look, our tree contains a high value of 10, half of that is 5, our root! In other thoughts, that means that if our tree already has the proper root we shouldn't bother changing it, but continue onward and examine the branches of that root. You'll notice that once again, the left sub tree of our root is balanced already, so no need to check it, but the right side is skewed. In fact, if you ignore the root and left sub tree, you'd just have the skewed tree of 8,9,10. and if you ran our algorithm on that? Well, there are 3 nodes in our tree, and it so happens, that the middle one of those is 9 and to balance our tree? We need that 9 to be the root. Tada.

Now you may have noticed a bit of... entropy creeping into my arguments for example, when we look at our middle, I've used both the value of the node, and the node themselves. So which should our algorithm take on? Obviously, the value side of this. So in that case, how do we select 9? Well, we can look at tree depth? But once again that's more of our nodes really. 10 + 8 divided by 2 gets us it, but is this just a happy coincidence?

If we look at our left tree we see it's already balanced, but what if it were like our right side? it'd go 3 2 1. The last node, and the first node added together and then divided by two? get's us 2. Which happens to be the value we need to balance! Seems nice right?

What if you don't have the right value? How do you find the closest? If two values are the same distance away, then how do you choose? I'm going to think about these more and get back to you. Maybe even with some code to show!

Dakota POtatoes

Ok, so before I begin let's just start with this.

Last week, I hung out with a few friends and we were on ChatRoulette and having a good time. We met a couple people who were cool, but not as entranced with us as two girls from Ohio. The girls were both the same age (16) and were from a military family. One of them was adopted and that was pretty neat. They wrestled on camera and we egged them on, and we sung songs and played music for them.

Last night, I watched an episode of the IT Crowd with some friends, from the 4th season, and Roy was trying to build a Sea Parks park out of mash potatoes.

Alright, so somehow, my subconscious decided to mix these things together. And I dreamt about Dating one of the girls and making her laugh by sticking my face in mash potatoes, blowing really hard and making potatoes come out of a hole in the mash. Then we made out....

Sooo yeah, I woke up and my blankets were everywhere and so were my pillows. My bed was a total mess, so somehow I must have had the best makeout session ever. In my dreams. Ugh.  I just thought'd write about it because, one it's weird because I barely know this girl and two potatoes? Really?

Alright, I have work to do but just needed to get that off my stack.

First Week 2nd Semester Over

Good beejeebeez that was a long week.

Starting your day at 7:15 ish in the morning after an entire semester of waking up at 10:30 is a bit of a pain. And boy, does it make your day's feel longer. And it also definitely cuts into the social life.

Going to bed by 11 everyday, and waking up at 7 is pretty easy, but I feel like I've no time to myself anymore. Not like I did last semester anyway. Last semester I would stay up til 3 coding away and doing fun things, this semester, I'm in bed, I'm sleeping, and nothing is happening. Even now, Freitag! Friday night no less! And I'm back here, getting ready to go to sleep, granted about an hour later than the usual 11, but it's because I have work tomorrow and I want to be ready. That's right, Mr. Responsible is right here Ladies and Gents!

Which sucks, because if he wasn't, I'd still be at a friends dorm, watching Black Swan with them and watching them freak out of Natalie Portman's finally toned ass. Granted, I've already seen Black Swan, and such, but still... Being responsible sucks sometimes, and I have yet to actually see the fruits of my labors. Hopefully they'll grow soon, because honestly, I just want to go get trashed and not have to think anymore. I've been thinking too much lately and it's really obnoxious.

Also, today, as a thought experiment, I figured out how to represent a binary tree as an array, the only requirements tothe recursive algorithm I thought up, is that the tree MUST be balanced. But if it is, then a simple if you want to go left, 2(i)+1, right? 2(i)+2 where i is the index you're currently on, until the 2(i)+LR is greater than the size of the layer you're on.

Also, I've recently started watching 30 Rock. Which is a good show, and now I have a face to go with the name, Tina Fey.

Stuck Up Bitch on a White Horse

Good lord. Who knew that people could change to much in a year? Yesterday I upgraded my aim, and along with that I had it import stuff from facebook for me. So I ended up with some contacts whom I haven't talked to in a while.

Today, I saw my friend Lizzie's aim on. And decided I could talk to her a bit before I went to bed. I did, she seemed cold and kinda snappy the whole conversation. Then after I told her good night. She said something about me having implied sexual passes at her last time we spoke. Which is completely ridiculous. The last time I talked to her was on the phone, with terrible service at a concert. Seriously? She had signed off already when I came back from watching a video. I read her little high horse bullshit and thought for a bit. Then told her to get off her high horse and to piss off. She used to be such a nice person it seemed. But I guess she's just like the rest of the female population. Stupid, arrogant, and thinks that if they're 'pretty' or have a boyfriend they can get away with saying anything.

God, they're so annoying. God, why would anybody even want to date someone like that? It's so irritating trying to find someone who isn't a moron, it really is. All I want to do is find someone who's smart, can hold a conversation, and isn't completely crazy. It really is hard. Especially considering how girls like my 'friend' give the populace a bad name. Ergh.

I really really want to just have the bitch slapped.

Back At School

Well, now that I have internet again I can blog some more!

Right, so, a lot of things happened over my vacation. None of them too life changing or groundbreaking. One of my friends is getting married to someone whom she probably will end up divorcing at some point. But, I wish them the best even if my head tells me it won't work out. They're waiting a few years before actually getting married though, so maybe one of 'em will come to their senses.

I'm all for the "I want to see you happy because I'm your friend" but that really doesnt help people who are actually looking for your opinion on their life choices. So, I try not to sugar coat things too much. So I stayed calm and just told her that, if she feels like it will work out and that's what she wants, then I'm not going to stop it, and I approve of her trying to be happy and whatnot, even if I think it's not the best guy from what I've heard. But one of the main reasons I didn't have an opinion on her choice of hubby was because I've never actually met the guy, and I've only ever heard bad things about him, because when she complains about him. She complains to me, so I only really know one side of the coin.

I discovered a few things over vacation about myself. Mainly from other peoples instigations and other things. Such as what size pants I am when browsing the womens section. Double Zeroes! And they're comfy and I would probably have gotten a pair of them if they weren't so damn expensive. I don't care if someone might get confused because I'm a dude who happens to be wearing pants that make them wanna check out my ass. I'm comfortable with wearing whatever I want to and everyone else can deal with it.

I got drunk at a party and had a good time. My friend vomited, I didn't. She also rolled off the bed a lot, but we got her back on and righted her. I found out why I don't get laid that often (because my brother asked our mutual friend what she thought, and then he told me the next day, and no I didn't ask him to do that), it's apparently because I don't go after what I want, and I guess I'm not 'manly' enough. Which I take as, I'm not forward enough or willing to take a chance on someone when I could just have a friend and not bother with the complicated bullshit of emotions.

Christmas was fun, I got an mp3 player and a good book as well as some clothes and a water filter. So all in all it was a good time. I think I'm going to try to learn slide guitar again. It was something I tried before and didn't quite get working before besides being able to play In my Time of Dying by Led Zeppelin. So yeah, I dunno.

I have a lot of other stuff on my mind, but that can wait. Since I have internet again, I can blog more frequently!

I did have a good profound quote over vacation, well, a few of them, but one of them was: We should strive to never be content.