binary tree c++ insert and update?

Question

I want to make a binary tree in c++ that perform insert operation the inserted values are 4 on a node that is

 name,  type ,  order, and color

The use will enter these 4 as INSERT corn oil 3 yellow. It create a new node with name as corn and 3 child node as type ,order and color.

If again user enter same thing but change any other except name that exists like INSERT corn oil 4 red as corn name exist this will update node

preorder and postorder traversal with remove and find any node

Here is how i am going ?

     struct TreeNode {
          string itemname;  // The data in this node.
          TreeNode *left;   // Pointer to the left subtree.
          TreeNode *right;  // Pointer to the right subtree.
       };

1- Name node will have 2 values left right where 4th will be place

2- The hierarchy of tree is like root have only names that have 2 left right node so root have many nodes with names that have only 2 further node but no more node will be added to child node of names is it really a tree

A hash table would be more efficient in that case, but it depends what else you are using that tree for — FamZ, Jan 25 '17 at 08:36
if you are only inserting/updating and searching data a hash table is the better solution — FamZ, Jan 25 '17 at 08:40
You should go with a hash table if you are not strictly bound to using binary tree. — clzola, Jan 25 '17 at 08:40
with a tree, there's a tree search which is unnecessary, since you need a list of elements for each node as in a hash table because you are using a string as a key — FamZ, Jan 25 '17 at 08:42

score 0 · Answer 1 · edited May 23 '17 at 12:24

Since you are using binary tree, I am not sure you can use string as a key for TreeNode (well I have always used intigers). So what I suggest is that you have structure like this:

// I am not sure about types, but I assumed them by name
struct Element {
    char* name;
    int type;
    int order;
    char* color;
};

struct TreeNode {
    int key;
    Element *element;
    TreeNode *left, *right;
};

Then you would somehow calculate hash of Element::name to get a numeric value, which a is key. Now you would just traverse tree from root to the left or right depending on key. You would check on each node if key you are inserting is same as one in current node and if answer is yes, then you would swap values in that node, otherwise continue traversing the tree to the left or right. If you get to the bottom it means you haven't find a node with that key, so you create a new one and attach it as a leaf.

You can look this link to generate hash. However, keep in mind that for some string you can get same hash value, so you may need to keep more than one element at the current tree node.

UPDATE

Here is the code, however you can optimize it more by using pointers. But as mentioned in comments, if you are not strictly bound to use binary tree, you should use HashTable or std::map.

std::map<std::string, struct Element*> elements

and for retrieving element:

Element *e = elements["corn"]

Binary Tree implementation:

#include <iostream>
#include <vector>

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */



struct Element {
    std::string name;
    std::string type;
    int order;
    std::string color;
};

struct TreeNode {
    int key;
    std::vector<Element> values;
    struct TreeNode *left;
    struct TreeNode *right;
};

/**
 * see: https://stackoverflow.com/questions/8317508/hash-function-for-a-string
 */
int calculateHash(const char *s)
{
    int h = FIRSTH;
    while (*s) {
        h = (h * A) ^ (s[0] * B);
        s++;
    }
    return h; // or return h % C;
}

void printElement(Element element)
{
    std::cout
            << element.name
            << " "
            << element.type
            << " "
            << element.order
            << " "
            << element.color
            << std::endl;
}

void preOrder(TreeNode* node)
{
    if( node == NULL )
        return;

    for(size_t i=0; i<node->values.size(); i++) {
        printElement(node->values[i]);
    }

    preOrder(node->left);
    preOrder(node->right);
}

void insert(TreeNode** root, Element element, int key)
{
    if( *root == NULL ) {
        TreeNode* node = new TreeNode();
        node->key = key;
        node->values.push_back(element);
        *root = node;
        return;
    };

    if( key == (*root)->key ) {
        for(size_t i=0; i<(*root)->values.size(); i++) {
            if( (*root)->values[i].name == element.name ) {
                (*root)->values[i].type = element.type;
                (*root)->values[i].order = element.order;
                (*root)->values[i].color = element.color;
                break;
            }
        }
    }

    else if( key < (*root)->key ) {
        insert( &((*root)->left), element, key );
    }

    else {
        insert( &((*root)->right), element, key );
    }
}

int main()
{
    TreeNode *node = NULL;
    insert(&node, {"corn1", "oil", 3, "yellow"}, calculateHash("corn1"));
    insert(&node, {"corn2", "oil", 3, "yellow"}, calculateHash("corn2"));
    insert(&node, {"corn3", "oil", 3, "yellow"}, calculateHash("corn3"));

    insert(&node, {"corn2", "aaa", 32, "blue"}, calculateHash("corn2"));

    preOrder(node);
    return 0;
}

Not at the moment, but I can write it later. – clzola Jan 25 '17 at 08:39 — clzola, Jan 25 '17 at 08:39
please if you by today , – Ahsan Bhatti Jan 25 '17 at 08:40 — Ahsan Bhatti, Jan 25 '17 at 08:40
or similar link with hash so i modify it – Ahsan Bhatti Jan 25 '17 at 08:40 — Ahsan Bhatti, Jan 25 '17 at 08:40
`node->value` to string how? – Ahsan Bhatti Jan 25 '17 at 11:31 — Ahsan Bhatti, Jan 25 '17 at 11:31

binary tree c++ insert and update?

1 Answers1