This is an archived post. You won't be able to vote or comment.

all 16 comments

[–]TheSageMage 4 points5 points  (4 children)

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

[–]chrisforbes 0 points1 point  (3 children)

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

[–][deleted]  (1 child)

[deleted]

    [–]stevefolta 0 points1 point  (0 children)

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

    [–]TheSageMage 0 points1 point  (0 children)

    Red/Black are Evil, go for AVL :D

    [–]jarito 2 points3 points  (0 children)

    Red black trees might be another option.

    [–]robkinyon 2 points3 points  (0 children)

    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.

    [–][deleted] 0 points1 point  (6 children)

    Are we allowed to post code?

    [–]CookieOfFortune 1 point2 points  (1 child)

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

    [–][deleted] 0 points1 point  (0 children)

    Thanks for the idea.

    [–][deleted] 0 points1 point  (0 children)

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

    [–][deleted] 0 points1 point  (2 children)

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

    [–][deleted] 0 points1 point  (1 child)

    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.

    [–]alanwj 1 point2 points  (0 children)

    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.

    [–]munificent 0 points1 point  (0 children)

    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.

    [–]pbewig 0 points1 point  (0 children)

    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!