13 May, 2013, SteveThing wrote in the 1st comment:
Votes: 0
So I've been bashing my head against my keyboard for the last week. I've read quite a few articles on google:code and MSDN. There are quite a few that are very descriptive but use terminology that is beyond me (been out of school for almost a decade). Wiki has some good articles too, but the links to terminology have me even more confused.

Long story short. I see TONS of info on how to handle trees with data already in them. I have yet to come across an example that shows how to start a tree from root or they start from the bottom which makes my brain bleed. Every time I run my code, I end up with a worst-case (linked list) tree. I haven't tried randomizing the key for my data structure, but that's because I don't want to end up with a collision (at least 1K monsters, 4K rooms, areas, players, etc). Can anyone point me in the direction of a dummies guide to self-balancing binary trees?

</rant>

Thanx for listening!
13 May, 2013, Tyche wrote in the 2nd comment:
Votes: 0
C++? It's called std::map. :-)
13 May, 2013, Rarva.Riendf wrote in the 3rd comment:
Votes: 0
in C you can look how vnum are handled.
Creating map in C are annoying, there are many implementations you can find around though.

http://linux.die.net/man/3/hsearch
http://www2.informatik.hu-berlin.de/~web...

(yay I looked into that recently as well…dam I wish I had the courage to turn my code in C++ if only for that…)
13 May, 2013, quixadhal wrote in the 4th comment:
Votes: 0
Here's one I wrote, very simple… of course, for production you'd also want to have equivalent delete functions to let you free up memory. In my case, it was all read-only so I had no need to change or free anything.

But yes, use C++ std::map. There's no need to roll your own these days.

#define BUCKETS 100

struct s_stringMap;

typedef struct s_stringMap {
const char *key;
const char *value;
struct s_stringMap *next;
} stringMap;

unsigned int hashmap( const char *s );
void hash_init( stringMap *map );
void hash_add( stringMap *map, const char *k, const char *v );
const char * hash_find(stringMap *map, const char *k);

unsigned int hashmap( const char *s )
{
unsigned int hash = 0;

if(!s || !*s) return 0;
do {
hash += *s;
hash *= 13;
s++;
} while (*s);

return hash % BUCKETS;
}

void hash_init( stringMap *map )
{
int i;

for(i = 0; i < BUCKETS; i++)
{
map[i].key = NULL;
map[i].value = NULL;
map[i].next = NULL;
}
}

void hash_add( stringMap *map, const char *k, const char *v )
{
unsigned int hashcode;
stringMap *p;

hashcode = hashmap(k);
p = &map[hashcode];
while(p->key && strcmp(p->key, k) && p->next)
p = p->next;

if(!p->key) {
/* First node? */
p->key = (const char *)strdup(k);
p->value = (const char *)strdup(v);
p->next = NULL;
} else if(!strcmp(p->key, k)) {
/* Found our match! */
if(p->value)
free((void *)p->value);
p->value = (const char *)strdup(v);
} else {
/* New key */
p->next = (stringMap *)calloc(1, sizeof(stringMap));
p = p->next;
p->key = (const char *)strdup(k);
p->value = (const char *)strdup(v);
p->next = NULL;
}
}

const char * hash_find(stringMap *map, const char *k)
{
unsigned int hashcode;
stringMap *p;

hashcode = hashmap(k);
p = &map[hashcode];
while(p->key && strcmp(p->key, k) && p->next)
p = p->next;

if(!p->key)
return NULL;

if(!strcmp(p->key, k))
return p->value;

return NULL;
}
21 Jan, 2014, HeZkeZl wrote in the 5th comment:
Votes: 0
If you insert sequential numbers into a standard binary tree, it's going to end up as a list. Because every new value is larger than all of the previous ones, it's always going to choose the right-hand node at each branch.

To avoid this, you can put all of your keys into an array, and "shuffle" the items in the array, and then iterate the array, inserting each item into the tree in random order. This uses probability to keep the tree balanced.

Or you can use a self balancing tree structure, like a red-black tree, which readjusts pivot nodes if one side gets too "heavy".
21 Jan, 2014, alteraeon wrote in the 6th comment:
Votes: 0
The string allocator in Alter Aeon uses a binary tree and is set to rebalance itself if it reaches a depth of more than 40 nodes. It doesn't balance on the fly, just when the depth check fails. Doing true rebalancing on the fly tends to make insert operations a lot more expensive.

Alter Aeon MUD
http://www.alteraeon.com
22 Jan, 2014, HeZkeZl wrote in the 7th comment:
Votes: 0
If you are rebalancing at a depth of 40, you might actually get better performance using an RBtree. Inserts do cost a bit more, but it's still O(log n). If you had a billion strings, the depth of a balanced tree would only be 10 nodes. The extra time used to iterate those 30 extra nodes each access in that balance-on-demand model may very well end up costing more CPU cycles in the long run. It really depends on the implementation, though, and how the tree is being used. Few inserts, many accesses, and self balancing is a no-brainier; constant deletion and insertion, and it may not be as viable.

For the OPs mobile vnum scenario, I would assume that insertions would be fairly few and far between, and so RBTree would be appropriate.
22 Jan, 2014, Tyche wrote in the 8th comment:
Votes: 0
C++ std::map is most often implemented as a RedBlack Tree.
Also popular is the AVL tree which has a slightly better lookup time, but slightly longer insert time.
23 Jan, 2014, Viriato wrote in the 9th comment:
Votes: 0
Hail.
Oddly enough, noone asked about the purpose of the map. To the OP: do you a) just want to learn a bit more about algorithms, b) a functional and optimized data structure to solve a specific problem?
If b), considering what you want to store (and how many objects) and the most common operations you expect to execute in said data structure, then an appropriated data structure should be chosen. In a map are stored key/value pairs, and usually are used when you c) want your objects ordered by a specific condition (alfabetically, for instance; if you want FIFO or LIFO behaviour there are more optimized data structures), or if d) you want to retrieve a specific object from a bunch of objects (example: to store all characters with their name as key and the character object as value, and most common operation to query the map looking for a specific character). If c) a treemap is better (avl, rb, whatever tree), if d) then an hashmap (hashtable or similar).
If a)… ignore this reply :) well, and later I can post some examples about btree behaviour in element addition, removal, seqrch and iteration.
0.0/9