0

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 3

Comment deleted8 years ago

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 2

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

level 2

// 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

// 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

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

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

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

- Do you have a question? Check out /r/learnprogramming, /r/cscareerquestions, or Stack Overflow.
- Do you have something funny to share with fellow programmers? Please take it to /r/ProgrammerHumor/.
- For posting job listings, please visit /r/forhire or /r/jobbit.
- Check out our faq. It could use some updating.
- Are you interested in promoting your own content? STOP! Read this first.

**Related reddits**