Press J to jump to the feed. Press question mark to learn the rest of the keyboard shortcuts
0
Posted byu/[deleted]8 years ago
Archived

Binary Tree Balancing

Hello Reddit,

I'm learning basic algorithms for the hell of it, and I am hoping you guys could help me. I'll be using recursion.

So I am wanting to balance an ordered, fully right-balanced tree where for every node n, n.right = n.d+1 (from 1 to 15). I have 15 nodes.

I have two methods that I think I should use. Rotate left and rotate right. Both work as intended. I also know that because I have 15 nodes, the number of levels I need is ceiling(log2(15)), so in this case four.

The trouble I'm having is if I have an odd number of nodes, I need to, in this case since the heightRight(root) > heightLeft(root), rotate left until the heights are equal. Then here is my problem with the recursive procedure. Passing (n.left), then n.right (where the base n would be the root. The case would be different with an even number of nodes (then the height difference from the left of root and right of root can differ by at most 1.)

I'm not sure if I am accurately describing my problem or not.

16 comments
50% Upvoted
This thread is archived
New comments cannot be posted and votes cannot be cast
level 1

Look at AVL tree, it's basically what you are describing...

level 2

AVL trees are evil. Go for red-black trees.

level 3
Comment deleted8 years ago
level 4

Or AA-trees, which I believe are slightly simpler still.

level 3

Red/Black are Evil, go for AVL :D

level 1
3 points · 8 years ago

Red black trees might be another option.

level 1

The key concept which you're missing is that a binary tree is nothing more than a doubly-linked list with an entry point that isn't the left-most node. The best thought-form for this is a string with weights tied to it representing the various nodes. So, just find the correct head, lift it up, and everything falls out from there.

Once you have the thought-form, then coding is extremely simple.

level 1
[deleted]
1 point · 8 years ago

Are we allowed to post code?

level 2

If you are going to post code, perhaps you can try StackOverflow.

level 3
[deleted]
1 point · 8 years ago

Thanks for the idea.

level 2
[deleted]
1 point · 8 years ago

// left rotation around node public node rotateL(node n) { if (n == null) return null; else { node newRoot = n.RCN; n.RCN = newRoot.LCN; newRoot.LCN = n; return newRoot; } }

// right rotation around node
public node rotateR(node n) {
    if (n == null)
        return null;
    else {
        node newRoot = n.LCN;
        n.LCN = newRoot.RCN;
        newRoot.RCN = n;
        return newRoot;
    }
}
level 2
[deleted]
1 point · 8 years ago

// balancing public node balance(node n) { if(n != null) { if (heightR(n) > heightL(n)) { if(height(n.LCN) > height(n.RCN)) { n = rotateL(n); n = rotateR(n); } else { n = rotateL(n); } } else { if(height(n.LCN) < height(n.RCN)) { n = rotateR(n); n = rotateL(n); } else { n = rotateR(n); } } } return n; }

level 3
[deleted]
1 point · 8 years ago

The obvious thing here is that I'm not calling balance again, but I'm getting a stack overflow error. I don't think I'm stopping it.

level 4
2 points · 8 years ago

Unless I'm missing something, none of the code you've actually posted could cause a stack overflow. You don't have any recursion, or even looping. Check heightL, heightR, and height and make sure their recursion is properly bounded.

level 1

What you're looking for is a self-balancing binary tree. There are a bunch of different algorithms for doing so. The two most common are AVL trees and red-black trees. (For example, I believe most implementations of the STL use a red-black tree to implement maps.)

Another related data structure is a heap which is in effect an ordered binary tree in a contiguous chunk of memory.

level 1

I do algorithmic exercises at my blog Programming Praxis. You might be interested in my exercises on binary search trees, red-black trees, treaps, and ternary search tries. And there's lots of other good stuff there. Check it out!

Community Details

1.4m

Subscribers

3.4k

Online

Computer Programming

Create Post
r/programming Rules
1.
Keep submissions on topic and of high quality
2.
No surveys
3.
No résumés/job listings
4.
/r/programming is not a support forum
5.
Spam
Info

Related reddits

Specific languages

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.