I hope BST means Binary Search Tree. I tend to be acronism(sp?) impaired. :(
If not, well, what I'm saying is still valid and is my own not so humble opinion. :)
On Wed, 6 Jan 1999, George said
>On Wed, 6 Jan 1999, Invincibill wrote the >
>>I hope you arent confusing doing a binary search on an array with
>>implementing a BST with an array. they are quite different. at least if
>>i remember correctly. its been awhile. yes, the routine to search an
>>array by a binary search is quite simple (about 30 lines or so). So is
>>the function so search a BST array(recursive, about 6 lines). but the
>>BST array is nasty nasty to setup(not to be confused with hard, just
>>ugly)in an array.
>
>/* returns the real number of the room with given virtual number */
>int real_room(int vnum)
>
>22 lines, counting the comments and without hyper-compacting. Not too hard
>to follow either... Of course, you have to ensure sorting.
Well, no one is saying real_room/object/mobile is hard to read. But, consider
when you add olc. You no longer have a guarantee that the array is ordered.
You have to solutions:
1. Rebuild the array to be sorted, extremely ugly.
2. Modify the functions to cope with the last portion of the array being unsorted.
With BSTs, you always have a sorted collection of objects. Plus, if the BST library is robust,
you don't see any added points of crashing. Add to this more flexibility (a dynamic structure),
good timing for searches (always binary search) and the possibility of reusing the code (you
have collections so you don't replicate the code to have new arrays) and I think it shows that
BSTs are o good thing... for Circle 4.0 of course.
I have a library stored away somewhere that was a balanced BST, that i made and used in my
university years.
I once had a project where I made a graph structure (similar to the rooms structure of the
MUD), that had hash tables for the nodes, where the collision lists where in fact BSTs, and the
links from each node to the others where also kept in BSTs.
Looking back I think I went a little overboard in the use of BSTs in that project, but the
point is: if it worked in that mess (which it did) it is robust enough. I can go through the
spider webs in my HD to find it if anyone wants it.
>
>ftp://ftp.gtk.org/pub/gtk/v1.1/glib-1.1.12.tar.gz
>
>It's still in development (get v1.0.x for stable) but has many useful
>functions and portability aids. Including single and doubly linked list
>implementations and hash tables. There's more, but it's best to just go
>read it.
>
I don't know that library, but if it's portable and robust, why not use it for Circle 4.0?
By the way, I still think we should move on to yacc and lex.
I hope you all had a Merry Christmas and an Happy New Year.
Luis Carvalho
Ps: Eh! You should have seen me trying to draw the graph monster to explain it to the teacher.
If you think it's easy, try drawing hash tables of BSTs of BSTs. Sheesh!
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST