C Board  

Go Back   C Board > General Programming Boards > C Programming

Reply
 
LinkBack Thread Tools Display Modes
Old 08-11-2008, 02:59 PM   #1
Dr Dipshi++
 
mike_g's Avatar
 
Join Date: Oct 2006
Location: On me hyperplane
Posts: 1,219
Balancing A Binary Tree

I came up with some code for a simple binary tree. I want to balance it but I am having trouble figuring out how to do this.

My idea was to create a malloced array of pointers to nodes then qsort them and rebuild the tree from that. The problem with this is that (AFAIK) I will need to use recursion to get at all the nodes which makes it tricky to keep track of the array index to place to node.

Heres my code:
Code:
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	struct node *left;
	struct node *right;1
	int num;
}Node;

Node *CreateHeadNode(int num) // Creates a new tree
{
	Node *head = malloc(sizeof(Node)); 
	head->left = NULL;
	head->right = NULL;
	head->num = num;
	return head;
}

void AddNode(Node *head, int num)
{
	Node *new_node = malloc(sizeof(Node)); 
	new_node->left = NULL;
	new_node->right = NULL;
	new_node->num = num;

	Node *here = head;
	Node *next = (num < here->num)? here->left: here->right; 
	while(next)
	{
		here = next;
		next = (num < here->num)? here->left: here->right;	
	}
	//'here' will be the last node
	if(num < here->num)
		here->left = new_node;
	else
		here->right = new_node;
}

void PrintTree(Node *head)
{
	printf("Node: %2d\tL:%p \tR:%p\n", head->num, head->left, head->right);
	if(head->left) PrintTree(head->left);
	if(head->right)PrintTree(head->right); 
}

void TreeSize(Node *node, int *count)
{
	(*count)++;
	if(node->left)TreeSize(node->left, count);
	if(node->right)TreeSize(node->right, count);
}


void BalanceTree(Node *head)
{
	int size = 0;
	TreeSize(head, &size);
	Node **temp = malloc(size * sizeof(Node*));	
	// Stuck here
	free(temp);
}

int main()
{
	Node *head = CreateHeadNode(10);

	AddNode(head, 15);
	AddNode(head, 12);
	AddNode(head, 18);
	AddNode(head, 11);
	AddNode(head, 1);
	AddNode(head, 6);
	PrintTree(head);
	int count = 0;
	TreeSize(head, &count);
	printf("Node Count: %d\n", count);
	return 0;
}
Anyone got any suggestions as to the best way to go about this?

Cheers.
__________________
Senior highbrow doctor of authority.
mike_g is online now   Reply With Quote
Old 08-11-2008, 03:20 PM   #2
*
 
noops's Avatar
 
Join Date: Jun 2008
Posts: 108
My idea when I was going to do this was to create a new tree and insert the nodes in such a way that the tree would be balanced.

So

1 2 3 4 5 6 7 8 9

Insert the middle number, 5, which creates two halves: 1 2 3 4 and 6 7 8 9

Now insert the middle of each halve, 3, 8 which also creates more halves 1 2 and 4 -- 6 7 and 9

Repeat.

Not sure if that made sense or if that results in a truly balanced binary tree.
noops is offline   Reply With Quote
Old 08-11-2008, 03:28 PM   #3
Dr Dipshi++
 
mike_g's Avatar
 
Join Date: Oct 2006
Location: On me hyperplane
Posts: 1,219
Well thats basically what I was planning to do once had the address of all the nodes in a flat array. Maybe I'm missing something here but I cant see a simple way of going about this w/o first converting the tree to an array or list.
__________________
Senior highbrow doctor of authority.
mike_g is online now   Reply With Quote
Old 08-12-2008, 05:21 AM   #4
Registered User
 
Join Date: Jul 2008
Posts: 133
Somewhere i read that either you must "convert" tree to array to balance it, OR use self-balancing tree from start (and of course, insert/delete functions are a bit more complex then).

Example of self-balanced tree:
http://en.wikipedia.org/wiki/Red-black_tree
(I even heard kernel hackers are playing with this "toy" too)
rasta_freak is offline   Reply With Quote
Old 08-12-2008, 12:26 PM   #5
Code Goddess
 
Prelude's Avatar
 
Join Date: Sep 2001
Posts: 9,664
>Somewhere i read that either you must "convert" tree to
>array to balance it, OR use self-balancing tree from start
That's not quite right. It's possible to globally balance a tree in-place without adding extra complexity to the base tree. One such algorithm is DSW.
__________________
My best code is written with the delete key.
Prelude is offline   Reply With Quote
Old 08-12-2008, 04:01 PM   #6
Dr Dipshi++
 
mike_g's Avatar
 
Join Date: Oct 2006
Location: On me hyperplane
Posts: 1,219
Hey prelude, I managed to find your site again. The self balancing trees look cool, but I'll try get this version working first. Still not sure how I'll flatten it; guess maybe I should start with deleting nodes first and think about it later.
__________________
Senior highbrow doctor of authority.
mike_g is online now   Reply With Quote
Reply

Thread Tools
Display Modes

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
binary interface to binary search tree giving me SUCH A HEADACHE!! tms43 C++ Programming 0 11-04-2006 11:07 AM
Binary Search Trees Part III Prelude A Brief History of Cprogramming.com 16 10-02-2004 03:00 PM
Tutorial review Prelude A Brief History of Cprogramming.com 11 03-22-2004 09:40 PM
Request for comments Prelude A Brief History of Cprogramming.com 15 01-02-2004 10:33 AM
BST/Red and Black Tree ghettoman C++ Programming 0 10-24-2001 10:45 PM


All times are GMT -6. The time now is 06:29 PM.


Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2010, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.3.2

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