[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: <penguinplay@sunsite.auc.dk>,<warewolf@mayn.de>*Subject*: Sv: Sv: Sv: Strangest thing happened; ...*From*: "Bjarke Hammersholt Roune" <asmild@post6.tele.dk>*Date*: Fri, 6 Aug 1999 02:04:19 +0200*Reply-To*: penguinplay@sunsite.auc.dk

>I'm mainly interested in how you just store a static complete tree. No >adding/removing, just read accesses. > Oh, that's quite easy. Well, ok, I didn't figure it out by myself, so that's easy for me to say... :) As you probably have figured out, nodes are kept track of by their offset into the array. Offset 0 is the root, and offset size-1 is the last node in the tree. for every offset i, (i * 2) + 1 is the offset of i's left child. for every offset i, (i * 2) + 2 is the offset of i's right child. for every offset i, (i - 1) / 2 is the offset of i's parent, except for offset 0. Trying to obtain a non-existant left or right child will yield a value that is greater than the size of the tree. I've made adding work now. Removing should be quite easy to implement now. Adding to a complete binay search tree is, it turns out, quite alot slower than adding to a non-complete one. In complete trees, every entry has one, and only one, correct location. Changing a node at the higest position (ie, the root) when adding can make it nessecary to move every node in a straight line (well, not literally straight, but conseptually) from the root to the leftmost leaf descendant of the root. If something like that happends, that changes the root of n subtrees of the tree where n is the number of nodes from the root to its leftmost leaf descendant. If we're really unlucky, then the same thing happends to every one of these subtrees, and to all of their subtrees on the right/left side (depends on wheter the leftmost unused location in the array was on the right or left side of the root), and so on. [self-pity mode on] Now, in the block of text above, there are some errors. Try if you can find it ;) That's what its like debugging the implementation for a complete binary search tree... [self-pity mode off] The performance shouldn't matter too much, though, atlesat not if we can avoid any merging/unmerging of the trees when loading paks. When we're writing them, then it'll either be format 1 paks, which are to be kept small, or format 0 ones, which its ok for to take a little while to write, as usually that will only happen when the developer is creating the release version of the paks, and then it really doens't matter. It took my computer something like 1-2½ second to add 500 entries one at a time to an empty tree, as percieved by me. This was a debug version with no optimizations, though. I'll get around to profile it tomorrow and get a little more precise time on a release build. The current implementation is not very optimized, so performance should get alot better. I haven't checked it (and I'm not going to!), but I think the worst-case performance for adding to and removing from this kind of tree is actually O(n) rather than O(log n). Don't know about average-case. Best case is definately O(log n). I think :) Performance for finding entries in this kind of tree, of course, is the same as an ordinary binary search tree that is balanced: O(log n) There're some things that's really nagging me: how the "¤#%!& do you specify member functions as template parameters to a template? This doesn't work: template<class ENTRY_TYPE, class KEY_TYPE, KEY_TYPE (someClass::*KEY_METHOD)()> class ppBinarySearchTree; Well, ok, it kinda works because it doesn't generate any errors or warnings, but then if you do this: ppBinarySearchTree<TestEntry, int, TestEntry::GetKey> tree; the compiler generates an error saying "const parameter expected". No amount of playing around with const will get you anywhere. Why on earth isn't TestEntry::GetKey const? I mean, you can't assign to it, because then you get an ambiguity error, which is even more confusing. Assigning TestEntry::GetKey to a function pointer works fine, though. You might ask if it's really nessecary to do it like this (with the templates). It's well worth it, as it makes it extremely easy to add hashing capability to a derivation with only a couple of lines of code. I'll come up with some default values so you won't have to specify all those parameters every time you want to use suchs a tree (could we add a non-virtual inline do-nothing member to ppBase named GetKey() and anohter one named GetHash() for this porpuse?). I was wondering if there aren't any good free open-source container class libraries that will do these kinds of classes? Does anybody know how to implement effecient external pre-order, in-order and post-order iterators to binary trees without creating an array to keep track of what has already been iterated over? Does anybody know how to compute the level of a node based on its offset into an array representing a binary tree without using base 2 logarithms or stepping through the levels, searching for it? If not, does anybody how to compute base 2 logarithms in C++? How expensive is this operation?

- Prev by Date:
**Re: back again** - Next by Date:
**The tree's working** - Prev by thread:
**Re: Sv: Sv: Strangest thing happened; ...** - Next by thread:
**Re: Sv: Sv: Sv: Strangest thing happened; ...** - Index(es):