> Now there is something i don't understand with these AVL trees. To insert a
> NODE into the tree, it has to have a KEY. I'm not sure what my KEY IS, in
> this case though.
A key is a value you associate with a piece of data.
For example, in a database of employee information, you could
create a unique employee ID number and then use it to look up the data
associated with that key.
In english, I'd issue a command like "give me the data for
Employee 12".
The only requirements of a key are that it be unique; whether it's
a pointer, or a string, or a number. A room number would work for this
......
> For example. If I was at a node that was the #40. and the Right->#55 and
> Left->#43. I'm trying to insert a new node, #47. I assume with an AVL tree
> (lets keep it simple, it's not a balanced one), i would decend down one
> level to the LEFT #43, and add it there (to the left or right, i don't
> know).
>
This would also involve rebalancing the tree nodes to insure an
optimal search time.
I don't think anyone recommened that you know how to use the
specifics of it, just that you understand how it functions, and why it is
better or worse for a given set of circumstances. You may want to not
worry so much about how it does it, and just use it as an add-on library -
at least at first. There's alot of datastructures that you don't fully
understand until you use/write them yourself.
> I'm assuming my key is the PRIORITY. Ie. Key#1 == most common / accessed
> room == top of tree. But you are saying -> forget that! the KEY is the
> RNUM / VNUM / Room Num (however you impliment your room system), and that u
> just place it into the tree normally, and that on average you most common
> rooms will only be a few levels down. The most common room might not be at
> the top / head of the tree ... but it will be just a few jumps to it. As
> opposed to a priority queue which i was thinking of originally, the most
> common room would be at the very top BUT the rest are already a few jumps
> to get to ... so on AVERAGE, the AVL kicks arse all over the priorty list.
Once again, it depends what you're using it for.
An AVL tree is simple; it's a way to organize data so that any one
given piece of data will be found in some guarenteed short time (compared
to many other data structures). The search time is optimized at the
expense of the insertion and deletion time - this isn't bad if we're
talking about rooms; insertion and deletion only cause a significant
impact at boot-up time, and that's still negligable.
I'm not sure of your definition of 'priority' queue, but insertion
is not too hard, except that you're not popping a queue stack, you're
keeping a static list size and reshuffling it around each time. A very
expensive process.
Of course, using an AVL tree for the same thing is similarly
expensive, and not recommended.
That's why everyone who's responded has asked what you're using it
for; do you want to have a slow, difficult way to keep track of which room
is important, or more likely, do you just want to provide speedy access to
rooms?
While it's true that an AVL tree won't take kindly to any sort of
re-ordering or continual shuffling anymore than ... well anything else
will, you're guarenteed a least-time search regardless of which room. A
linked list (call it what ever you like) will require searches and
resorting and a guarenteed 1 sort (aka, 1 searches and 2 relinks) per
access(*), it will suck like never before seen.
* - if a character moves in a room, that room we can assume to be at the
top of the list (by magic, best case). 1 search, finished. Each time he
takes a step into a different room, it needs to search for the new room,
and then break the links, and replace it. 1 search down 2 links (best
case), and two relinks. With multiple people, you'll have a rotating list
based on how quickly users move for each user that are all intertwined.
Chances are you'll have a search for a room you've already been in around
2-30 rooms down, unless your users like speedwalking (which may up that by
a factor of 3 or 4). Either way though, it's going to end up to be WAY
more searching for the average case than AVL, which will scale with both #
of rooms, and # of users.
> So this AVL thingo isn't the best solution after all? There are more
> effecient solutions?
Solutions to searching rooms quickly? I can think of a few, but
this one is pretty good. Solutions to seeing which room is the most
popular? I'd just put a static count of 'people entered' in the struct
and increment it on 'char_to_room' :)
PjD
--
+---------------------------------------------------------------+
| FAQ: http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html |
| Archives: http://post.queensu.ca/listserv/wwwarch/circle.html |
| Newbie List: http://groups.yahoo.com/group/circle-newbies/ |
+---------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 06/25/03 PDT