Balancing a binary tree

How does one do that if one doesn't have a field in the node structure which keeps track of it's "balancedness"?

Well, there are lots of ways to balance a binary tree. The simplest procedure is to make sure it never becomes unbalanced, i.e. every new element added to the tree must be inserted in such a way as to preserve balancedness. There are several algorithms for this: red-black trees and AVL trees are just two of them. For example, red-black trees mark each node as either "red" or "black" (which can be stored in a boolean value, a single bit, if you're careful), and due to various manipulations, you can never have a black child of a black parent. This can guarantee that the "lowest" leaf node is never more than twice as deep as the "highest" leaf.

Be warned: it can be a lot more complicated than it seems. Anyway, you can read Wikipedia if you're interested in knowing more.

Lets make it complicated, the tree is already given. All the nodes are inserted. How then?

Quote:

---

Originally Posted by budala

Lets make it complicated, the tree is already given. All the nodes are inserted. How then?

---

The easiest way is to create a new tree that is balanced. Take all the node values, and sort them into an array. Then start at the median, and make that the root node. The two medians on either side of the root node are the 2 children of the root node. Keep following this algorithm of choosing the medians on either side of the current leafs, and making those the new leafs.

Quote:

---

Originally Posted by bithub

The easiest way is to create a new tree that is balanced. Take all the node values, and sort them into an array. Then start at the median, and make that the root node. The two medians on either side of the root node are the 2 children of the root node. Keep following this algorithm of choosing the medians on either side of the current leafs, and making those the new leafs.

---

I like this approach, but I'm having trouble grasping the logic of copying a tree into an array.

Just "flatten" the tree. Or if you prefer to think of it this way, find the leftmost leaf, and then the number just to the right of that, and the number to the right of that, etc. It's kind of like the "right-hand" rule for solving mazes (always turn right and you'll end up at the exit eventually).

Wait, here's a better explanation. You want to access all of the elements in order, so that you can start in the middle of that to pick the root node and build another, balanced tree. But fortunately, it's very easy to access all of the elements of a binary tree in order. It goes something like this:

Code:

---

void inorder_traversal(Node *tree) {
    if(tree->left) inorder_traversal(tree->left);
    printf("%d\n", tree->data;
    if(tree->right) inorder_traversal(tree->right);
}

---

Then once you have all of the data from the tree (in an array or whatever), say this,

Code:

---

1 4 5 7 8

---

you can make a balanced binary tree out of it. Just do something like

Code:

---

Tree *create_balanced_tree(int data[], int start, int end) {
    int middle = (start + end) / 2;
    Tree *tree;

    if(start >= end) return empty_tree();

    tree = new_tree();
    tree->left = create_balanced_tree(data, start, middle - 1);
    tree->right = create_balanced_tree(data, middle + 1, end);
    tree->data = data[middle];

    return tree;
}

---

Hmm, I should have been on earlier.

Your options are: Scapegoat Tree and Splay Tree
I have already implemented both myself.

thanks dwks

now i'm stuck on transforming a binary tree into an array. i am puzzled with passing the array into an inorder traversal and keeping track of the array index

You don't have to copy it into an array. You can just turn the tree into a linked list where the left and right tree pointers are your prev and next pointers of the list, and then do the reverse in such a way as to make it balanced.

Code:

---

// Converts a tree to a doubly-linked list
TNode *Tree2ListHelper(TNode *list, TNode *tree) {
        for (;;) {
                if (tree->right) {
                        list = Tree2ListHelper(list, tree->right);
                        list->left = tree;
                } else if (list)
                        list->left = tree;
                tree->right = list;
                if (!tree->left)
                        return tree;
                list = tree;
                tree = tree->left;
        }
}

TNode *Tree2List(TNode *tree) {
        if (!tree)
                return NULL;
        return Tree2ListHelper((TNode*)NULL, tree);
}

// Converts doubly-linked list into a tree
TNode *List2Tree(TNode **head, int count) {
        if (count == 1) {
                TNode *last = (*head)->right;
                head->left = (*head)->right = NULL;
                return last;
        }
        int leftCount = count/2;
        TNode *newhead = List2Tree(*head, leftCount), *last;
        if (count > 2)
                last = List2Tree(newhead->right, count-leftCount-1);
        else {
                last = newhead->right;
                newhead->right = NULL;
        }
        newhead->left = head;
        *head = newhead;
        return last;
}

---