Thread: Balancing A Binary Tree

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    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.

  2. #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.

  3. #3
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

  4. #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)

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11: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, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM