Balancing a binary tree

This is a discussion on Balancing a binary tree within the C Programming forums, part of the General Programming Boards category; How does one do that if one doesn't have a field in the node structure which keeps track of it's ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    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"?

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    Lets make it complicated, the tree is already given. All the nodes are inserted. How then?

  4. #4
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    Quote Originally Posted by budala View Post
    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.
    bit∙hub [bit-huhb] n. A source and destination for information.

  5. #5
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    Quote Originally Posted by bithub View Post
    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.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    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;
    }
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Hmm, I should have been on earlier.

    Your options are: Scapegoat Tree and Splay Tree
    I have already implemented both myself.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    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

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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;
    }
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21