Like Tree1Likes
  • 1 Post By MacNilly

Create a balanced (not BST) tree

This is a discussion on Create a balanced (not BST) tree within the C Programming forums, part of the General Programming Boards category; Hi, I would like to learn an algorithm to create a balanced tree. I don't mean a Binary Search Tree ...

  1. #1
    Registered User
    Join Date
    Aug 2011
    Location
    Italy
    Posts
    13

    Question 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!

  2. #2
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    You probably will find some value in reading through Prelude's Tutorials on data structures. They are pretty comprehensive and easy to follow.
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Before creating a new level in the tree, all the nodes of the current level must be filled.
    So you want a perfect tree.

    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.
    My best code is written with the delete key.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    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.
    Last edited by iMalc; 09-10-2011 at 03:27 PM.
    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"

  5. #5
    Registered User
    Join Date
    Aug 2011
    Location
    Italy
    Posts
    13
    Quote Originally Posted by AndrewHunter View Post
    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:
    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 ) Binary tree - Wikipedia, the free encyclopedia

  6. #6
    Registered User
    Join Date
    Aug 2011
    Location
    Italy
    Posts
    13
    @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

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

  7. #7
    Registered User
    Join Date
    Aug 2011
    Location
    Italy
    Posts
    13
    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!

  8. #8
    Registered User
    Join Date
    May 2011
    Location
    Around 8.3 light-minutes from the Sun
    Posts
    1,866
    Quote Originally Posted by kr0n1x View Post
    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);
        }
    }
    Quote Originally Posted by anduril462 View Post
    Now, please, for the love of all things good and holy, think about what you're doing! Don't just run around willy-nilly, coding like a drunk two-year-old....
    Quote Originally Posted by quzah View Post
    ..... Just don't be surprised when I say you aren't using standard C anymore, and as such,are off in your own little universe that I will completely disregard.
    Warning: Some or all of my posted code may be non-standard and as such should not be used and in no case looked at.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    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.
    Last edited by iMalc; 09-12-2011 at 12:48 AM.
    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"

  10. #10
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    311
    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.
    anduril462 likes this.
    GCC on Fedora Core 10

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 04-28-2011, 01:27 PM
  2. Weight Balanced Tree - Implementation
    By paulovitorbal in forum C Programming
    Replies: 1
    Last Post: 10-31-2007, 02:28 PM
  3. how to create a tree of object
    By winsonlee in forum C++ Programming
    Replies: 1
    Last Post: 08-25-2004, 01:20 AM
  4. How do you create a balanced binary tree?
    By Mr_Jack in forum C++ Programming
    Replies: 3
    Last Post: 01-13-2004, 02:02 PM
  5. Code to test if a tree is balanced
    By rahuls in forum C Programming
    Replies: 1
    Last Post: 03-20-2003, 01:41 PM

Tags for this Thread


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