BinTree module
BlitzMax Forums/BlitzMax Programming/BinTree module
| ||
| I've written a binary search tree module which I believe affords a significantly more control than the TMap type. Documentation is rather thorough and includes a plethora of examples. TMap is a http://en.wikipedia.org/wiki/Red-black_tree Insertion involves more overhead, but it guarantees that the tree is always more or less balanced. BinTree can either be a http://en.wikipedia.org/wiki/Binary_search_tree or a http://en.wikipedia.org/wiki/Splay_tree In the case of the former: Insertion involves essentially no overhead, but the tree can become imbalanced. Included is the OptimizeTree() function, which reassembles the tree into its most balanced state possible on demand. In the case of the latter: Essentially all operations upon the tree involve some overhead, but in many cases it will be more than made up for in how it helps to keep the tree somewhat balanced, and keeps frequently looked-for nodes on the top. The functionalities are completely interchangeable. Download the module here: http://dl.dropbox.com/u/10116881/blitz/pine.bintree/pine.bintree.mod.zip View the built docs here: http://dl.dropbox.com/u/10116881/blitz/pine.bintree/commands.html List of wrapper commands: CreateTree:BinTree(splay:Int=True) TreeSetSplay(tree:BinTree,splay:Int) TreeGetSplay:Int(tree:BinTree) TreeRoot:BinNode(tree:BinTree) TreeSplayNode(tree:BinTree,node:BinNode) ClearTree(tree:BinTree) CountTree:Int(tree:BinTree) TreeHeight:Int(tree:BinTree) TreeIsEmpty:Int(tree:BinTree) TreeContains:Int(tree:BinTree,key:String) TreeInsert:BinNode(tree:BinTree,key:String,value:Object) TreeRemove:Int(tree:BinTree,key:String) TreeRemoveFirst:BinNode(tree:BinTree,key:String) TreeRemoveNode(tree:BinTree,node:BinNode) TreeFind:Object(tree:BinTree,key:String) TreeFindNode:BinNode(tree:BinTree,key:String) TreeFindAll:TList(tree:BinTree,key:String) TreeToArray:Object[](tree:BinTree,sort:Int=0) OptimizeTree(tree:BinTree) TreeObjects:BinEnum(tree:BinTree) TreeKeys:BinEnum(tree:BinTree) TreeNodes:BinEnum(tree:BinTree) CopyTree:BinTree(tree:BinTree) BinNodeString:String(node:BinNode) BinNodeContents:TList(node:BinNode) BinNodeKey:String(node:BinNode) Last edited 2012 |
| ||
| What algorithm do you use to balance the tree. Also, this is essentially a less optimized version of the TMap that gives you more control, as far as I can see. I'd be more interested if someone implemented a splay tree or something niche like that. Or a hashtable (is there a good hashtable implementation?). Last edited 2012 Last edited 2012 |
| ||
| I have an unpolished hash table implementation, but it doesn't have any fanciness for making dynamic resizing more efficient. Once I've done that I might make that into a module as well. As to being a less optimized version of the TMap, that's really not the case. It's not self-balancing, which means that unless you're making a remarkably large tree with the ability for it to become very imbalanced, this BinTree implementation will probably run faster because of the reduction in overhead for insertion. If you are working with a larger tree, however, and don't have the time spare to balance the tree, then you probably want to use a TMap. Due to its support for multiple entries using the same key and flexibility in handling, if you're initiating the tree on load it would likely be significantly more desirable to insert the values into it and then optimize it. Several of the functions that BinTree has are impractical in a red-black tree like TMap is because they would mess with the node colors (which are what make the self-balancing possible) The algorithm I use: the nodes are arranged onto an array via a recursive in-order traversal, and then the new structure of the tree is made using a binary search. edit: As to splay trees, adding that capability to this existing module is fairly trivial. I'm almost through with an update to add that functionality along with a couple other tweaks, just as soon as I can work out why the hell my remove method stopped working properly. edit again: aaand the module is updated, with support integrated for splayed trees Last edited 2012 |
| ||
| So it is less efficient. That sounds like an nlog(n) algorithm + n for all the insertions. So lets say nlog(n) + n. Using a red-black binary tree has a re-balance step (log(n)) and the insertion is constant time. So to add all the items its nlog(n): theoretically less than nlog(n)+n when getting to the same point. You're tree traversal to build an array is wasting both space and time. Also if you are just using it without balancing, worst case scenario you are looking at n+n (n insertions, n traversal). However with the standard TMap its n+log(n)... The splay tree implementation is a little more interesting. |
| ||
| I fancied up my hash table code. module: http://dl.dropbox.com/u/10116881/blitz/pine.hashtable/pine.hashtable.mod.zip docs: http://dl.dropbox.com/u/10116881/blitz/pine.hashtable/commands.html Last edited 2012 |
   |