Saturday, April 14, 2007

Binary trees.

Today I was working on a small replacement for std::map, that I am not allowed to use. I ended up doing something like this:

/** the [] random access method will return the Node that
* has that key, or create a new one.
*/

Node* NodeTable::operator[](std::string key){
TreeNode** tmp = &root_of_three;

while (*tmp) {
if (key > (*tmp)->key_) {
tmp = &(*tmp)->rNext_; // right branch
} else if (key < (*tmp)->key_) {
tmp = &(*tmp)->lNext_; // left branch
} else { //key == tmp->key,
return (*tmp)->getVal(); found!
}
}

*tmp = new TreeNode(key);
return (*tmp)->getVal();
}

I am not sure this is the fastest possible solution...
Post a Comment