Create a balanced (not BST) tree

Hi, I would like to learn an algorithm to create a balanced tree.
I don't mean a Binary Search Tree (lowerThanRoot values go to left, HigherThanRoot go to right), I just want the tree to fill completely. Before creating a new level in the tree, all the nodes of the current level must be filled.

I've been trying to do it, but it seems more complex than i tought.

I've tought about using a queue data structure, filling it with visited nodes of the same level and then visit all their discendents when needed. Is it right?

If you got an algorithm for it (or better ideas, always appreciated), I'd like to take a look at it.

Thank you, Bye!

You probably will find some value in reading through Prelude's Tutorials on data structures. They are pretty comprehensive and easy to follow.

Quote:

Before creating a new level in the tree, all the nodes of the current level must be filled.

So you want a perfect tree.

Quote:

I've been trying to do it, but it seems more complex than i tought.

Not especially. Look into level order searches and incorporate that process into your insertion procedure. In the absence of any ordering method, making a perfect tree is indeed harder if you use a depth first search for finding the next insertion point while a level order search makes it almost trivial.

You are describing filling a tree breadth-first. That is actually quite easy. The trick is to look at the count of the number of nodes that will be in the tree, in binary.

Then look at the bits from the second leftmost bit set (ignoring the first 1 in other words) to the rightmost bit. If the bit is a zero go left, and if it is a one go right.

So say you had 5 nodes currently in the tree and you want to insert the sixth one. What you have:

Code:

A / \ B C / \ D E

First take the nunber of nodes plus 1 in binary. It's 5+1 = 6 which is 110 in binary. So ignoring the leftmost 1 gives us 10. That means go right, then left, and then insert there:

Code:

A / \ B C / \ / D E F

Now if you want to insert another, the current tree count is 6 and 6+1 = 7 which is 111 in binary, so dropping the leading 1 you get 11 and go right twice:

Code:

A / \ B C / \ / \ D E F G

Next insert there are 7 nodes already. 7+1 = 8 and that's 1000 in binary.
Skip the leading one and you get 000 which means go left three times and as you can see that cleary places the node on the start of the next level down.

Edit:
The other easy and more efficient way is to put a pointer to each node you insert onto the back of a queue. You repeatedly pop the first node from the queue, attach a left and right child onto it and then put the left and right child onto the back of the queue. When you've filled the tree with enough nodes, just throw away your queue and you're done.

Second edit: Oh and that'll be the "Level Order Search" Prelude referred to.

Quote:

Originally Posted by AndrewHunter

You probably will find some value in reading through Prelude's Tutorials on data structures. They are pretty comprehensive and easy to follow.

I don't care to keep the tree balanced, I only need to fill a tree by using a struct like this:

Code:

struct node { int data; struct node *left; struct node *right; };

I've seen some informations about AVL but it talks about rotating values to keep the tree balanced (and ordered, like a BST).

But I don't need all that, I only want all my left and right nodes to be filled before creating a new level in the tree. This is where i got difficults.

In the AVL page of that link, I found it talking about an auxiliary structure (like an array), I quote it:

Quote:

Unfortunately, forcing such perfect balance is very expensive because it requires a global restructuring that visits almost every node in the tree and guarantees balance at each subtree. Alternatives for global balancing use an auxiliary array, which isn't much better. So we have to settle for less than perfect by only making local changes that meet a well chosen invariant. However, with the AVL invariant, these local changes result in a structure that is still very close to perfect.

source: Eternally Confuzzled - AVL Tree Tutorial

Could this be my solution? Using a queue (made by an array or by linked lists)? Or you got better ideas?

Thank you!

@Prelude: Almost, I want a Complete Binary Tree. (yay I found how to call it :D ) Binary tree - Wikipedia, the free encyclopedia

@iMalc: That's how I wanted the tree to look like, sorry if i wasn't clear in the first post.

That algorithm is awesome :D

Is the queue implementation possible/useful/easier? Which would you prefer?

I found a way to implement it with a queue.

I should make the code better (at least the level_insert() function), but I'll post it anyway just for someone who could need it.

Tree level insert with a queue: [C] level_insert - Pastebin.com

If you got any advice for me, I'll appreciate it.

Bye!

Quote:

Originally Posted by kr0n1x

I found a way to implement it with a queue.

I should make the code better (at least the level_insert() function), but I'll post it anyway just for someone who could need it.

Tree level insert with a queue: [C] level_insert - Pastebin.com

Thanks for posting your solution; let's just move that into the page so we don't loose that link in the future.

Code:

#include <stdio.h> #include <stdlib.h> /* this is going to contain the queue, made of pointers to tree's nodes */ struct queue { struct node *pointer; struct queue *next; }; /* this represents the tree's nodes */ struct node { int inf; struct node *left; struct node *right; }; void level_insert(struct node **); // enter a new node into the tree keeping it a "complete tree" void inQueue(struct queue **, struct queue **, struct node *); // push a node into the queue struct node *outQueue(struct queue **, struct queue **); // pop a node out of the queue void preorder(struct node *); // tree's preorder visit (just for test purpose) void level_visit(struct node *); // tree's level visit int main(void) { struct node *Tree = NULL; int i; /* I'm making the tree this way to be sure it's made how I want xD */ Tree = (struct node *)malloc(sizeof(struct node)); Tree->inf = 5; Tree->left = (struct node *)malloc(sizeof(struct node)); Tree->left->inf = 3; Tree->right = (struct node *)malloc(sizeof(struct node)); Tree->right->inf = 7; Tree->left->left = (struct node *)malloc(sizeof(struct node)); Tree->left->left->inf = 10; Tree->left->left->left = NULL; Tree->left->left->right = NULL; Tree->left->right = (struct node *)malloc(sizeof(struct node)); Tree->left->right->inf = 8; Tree->left->right->left = NULL; Tree->left->right->right = NULL; Tree->right->left = (struct node *)malloc(sizeof(struct node)); Tree->right->left->inf = 4; Tree->right->left->left = NULL; Tree->right->left->right = NULL; Tree->right->right = NULL; /* preorder visit to be sure the tree is made correctly */ preorder(Tree); printf("\n\n"); level_insert(&Tree); // entering a new node level_visit(Tree); // showing the new tree level_insert(&Tree); // entering another new node level_visit(Tree); // level visit test again :D for(i = 0; i < 10; ++i) { level_insert(&Tree); level_visit(Tree); } return 0; } void level_visit(struct node *a) { struct queue *testa = NULL, *coda = NULL; struct node *aus = a; if(a != NULL) { inQueue(&testa, &coda, aus); while(testa != NULL) { aus = outQueue(&testa, &coda); printf("%d ", aus->inf); if(aus->left != NULL) inQueue(&testa, &coda, aus->left); if(aus->right != NULL) inQueue(&testa, &coda, aus->right); } } } void level_insert(struct node **a) { struct queue *testa = NULL, *coda = NULL; struct node *aus = *a; int flag = 0; if(*a != NULL) { inQueue(&testa, &coda, aus); while(testa != NULL && flag == 0) { aus = outQueue(&testa, &coda); if(aus != NULL) { if(aus->left == NULL || aus->right == NULL) { if(aus->left == NULL) { aus->left = (struct node *)malloc(sizeof(struct node)); printf("\nEnter a number: "); scanf("%d", &(aus->left->inf)); aus->left->left = NULL; aus->left->right = NULL; flag = 1; } else { aus->right = (struct node *)malloc(sizeof(struct node)); printf("\nEnter a number: "); scanf("%d", &(aus->right->inf)); aus->right->left = NULL; aus->right->right = NULL; flag = 1; } } else { inQueue(&testa, &coda, aus->left); inQueue(&testa, &coda, aus->right); } } else { aus = (struct node *)malloc(sizeof(struct node)); printf("\nEnter a number: "); scanf("%d", &(aus->inf)); aus->left = NULL; aus->right = NULL; flag = 1; } } } else { *a = (struct node *)malloc(sizeof(struct node)); printf("\nEnter a number: "); scanf("%d", &((*a)->inf)); (*a)->left = NULL; (*a)->right = NULL; } } void inQueue(struct queue **head, struct queue **tail, struct node *ele) { struct queue *nuovo = NULL; nuovo = (struct queue *)malloc(sizeof(struct queue)); nuovo->pointer = ele; nuovo->next = NULL; if(*tail != NULL) (*tail)->next = nuovo; else *head = nuovo; *tail = nuovo; } struct node *outQueue(struct queue **head, struct queue **tail) { struct node *aus = NULL; aus = (*head)->pointer; if(*head != NULL) { *head = (*head)->next; if(*head == NULL) *tail = NULL; } return aus; } void preorder(struct node *p) { if(p != NULL) { printf("%d ", p->inf); preorder(p->left); preorder(p->right); } }

You could simplify your tree enqueue and dequeue routines somewhat by making the assumtion that the queue never becomes empty. Then you can ensure that this remains true by placing the first node in the queue explicitly, only peeking at the top node each time, and putting the children on the back prior to doing a pop-front.
Each operation is then very short:

Code:

//enqueue: tail->next = newNode; tail = newNode; //peek: return head; //dequeue: temp = head; head = head->next; free(temp);

When peeking at the top node you should never encounter a NULL because you would never put a NULL into the queue.

level_insert is also way more complicated than it needs to be. Every node that reaches the head of the queue and gets peeked at will have no children at that point. Without even examining them you can just immediately create both new children and assign these to the left and right pointers, nulling the grandchild pointers of course. Something like the following pseudocode:

Code:

add first item to head of tree while more items to add create left child assign new child to peek()->left put left child onto queue tail if more items to add create right child assign new child to peek()->right put right child onto queue tail pop from the head of the queue destroy queue

This will just build your whole tree for you and would be suited to building the tree as it is read in from file for example.

The whole code seems too complicated for me. You can make a heap (which is a complete) tree in an array just by filling it up from 0 to N-1, where N is the number of nodes in the "tree." You can ignore the heap property.

Say that

Code:

{ A, B, C, D, E, F }

is the set of nodes. Then your array looks like this: ABCDEF, and your tree looks like this:

Code:

A / \ B C / \ / D E F

To find the left child of a node (at index i) its index is

Code:

2i + 1

, and the right child is

Code:

2i + 2

(if it exists). The parent of a node at index i is also

Code:

(i - 1) / 2

(floor div).

To add a node, just add it to the end of the array. To remove a node, replace it with the last node so that the tree is still complete.