How does one do that if one doesn't have a field in the node structure which keeps track of it's "balancedness"?
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 ...
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.
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.
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.
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:
Then once you have all of the data from the tree (in an array or whatever), say 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); }
you can make a balanced binary tree out of it. Just do something likeCode:1 4 5 7 8
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.
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"
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; }
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"