2002.10.29 ~04 Splay tree, a more complex tree structure OK, because of this q3asm thing, I'm suddenly in a tree mood. Apparently in my textbook, three chapters after the one on R-B and A-A trees, is splay tree. This may be a(n overkill) solution for my opcodes worries. Basically the idea of a splay tree is to repeatedly split apart the tree and glue them back together in different ways such that more frequently-accessed elements rise towards the root (and thus cheaper for *future* accesses), while still maintaining the tree's order. The penalty here is that worst-case scenario is much much worse than RB/AA tree, on the hopes that average-case, for the more frequent nodes, gets better. And all that splitting/splaying also costs. The idea is to spread out the cost of the few worst-case accesses across many very-good-case accesses (this is where the term "amortize" comes in, but I'm still not sure exactly what the definition of the word is). Of course, this depends on there being *some* "frequent nodes". Apparently the cost of splay trees is horrendous for purely-random accesses. Fortunately, (functioning) assembly doesn't involve throwing together random opcodes in random sequences. The splay tree, in some ways, reminds me of Huffman coding, where the more frequent sequences use fewer bits than less-frequent sequences. Or of caches, scoring big wins for frequently accessed memory. Splay tree would dynamically re-arrange itself so that the more freqently sought node cost less to find than less frequently sought nodes. Splay tree may also be a good idea for the symbols tree, as there are likely to be some symbols accessed more frequently than others. For example, g_entities[], the list of all entities in the game world.