Acorn Arcade forums: Programming: Binary Trees
| |
Binary Trees |
| |
Phlamethrower (01:16 2/3/2004)
Paolo Zaino (17:40 18/3/2004)
Phlamethrower (17:55 18/3/2004)
|
| |
|
Jeffrey Lee |
Message #52381, posted by Phlamethrower at 01:16, 2/3/2004 |
 Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
For the past few months I've been using my own binary tree algorithim in various programs. This algorithm is fairly simple, is based around items with fixed size keys, and due to its design the tree depth is limited to log2(max_key_value) - so no balancing is required (Or in fact possible). Due to its simplicity, I'm sure that someone else must have come up with a similar system before me - but the closest thing I can find on the Internet is the bit tree. So the question is, does anyone recognise the following?
* All data items are stored in the leaves of the tree
* All data items must have key values of the same size
* Each interior node must have two children, while leaf nodes can have one or two (i.e. the data items)
* The decision of which child node to head down when searching for an item is based around the value of a certain bit in the key being searched for. If this bit is set then the child called 'one' is searched, else the child called 'zero' is searched.
* Rather than checking every single bit of the key one at a time, some bits can be skipped if their values are constant for a particular (sub) tree: A per-node mask is used, which contains only the bits for which decisions have been made (assumed or otherwise). Hence if the mask value AND the key being looked up doesn't match an 'expected position' indicator, then the data item doesn't exist.
As an example, values 0, 3, 6, 9 and 12 stored using 4 bit keys would be represented by:
A-----------------------|
B-----------| C-----------|
D-----| |.....| | |
E--| F--| G--| H--| I--|
XX XX XX XX XX
0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15
(Using the XX's to denote where the data items are, and the number scale to show the different positions possible with 4 bit keys)
The nodes would have the following attributes:
Node | Mask | Twiddle | Pos | Zero | One
-----+------+---------+------+------+----
A | 0000 | 1000 | 0000 | B | C
B | 1000 | 0100 | 0000 | D | G
C | 1000 | 0100 | 1000 | H | I
D | 1100 | 0010 | 0000 | E | F
E | 1110 | 0001 | 0000 | '0' |
F | 1110 | 0001 | 0010 | | '3'
G | 1110 | 0001 | 0110 | '6' |
H | 1110 | 0001 | 1000 | | '9'
I | 1110 | 0001 | 1100 | '12' |
(Where mask is the binary bitmask to check the search key against, twiddle is a bitmask containing just the bit of the key to check, and pos is the expected value of (mask AND key) when performing a search)
The children of each node is either more nodes (If twiddle > 1), or data item(s) if twiddle = 1.
If you were to try searching for the value 11 (1011 binary), then you would head from node A to C (because 1011 AND 1000 <> 0), then from C to H (because 1011 AND 0100 = 0), and then abort because 1011 AND 1110 <> 1000 (the 'pos' value).
If you were to search for 8 though, then you'd still go from A to C to H, but then fail because there is no 'zero' child (Which you have to go down because 1000 AND 0001 = 0). Searching for 9 would succeed though, because the 'one' child exists.
Does this seem familiar to anyone, or have I stumbled across something new? |
| |
 [ Log in to reply ] |
| |
|
Paolo Fabio Zaino |
Message #53137, posted by Paolo Zaino at 17:40, 18/3/2004, in reply to message #52381 |
Member
Posts: 61
|
Jeffry i never saw that but, honestly, i am not a tree structures expert so just take my words easy lol 
Best luck for your new technology
________
RISC OS Projects: https://github.com/RISC-OS-Community
RISC OS Blog: https://paolozaino.wordpress.com/category/risc-os/
Cheers! |
| |
[ Log in to reply ] |
| |
|
Jeffrey Lee |
Message #53140, posted by Phlamethrower at 17:55, 18/3/2004, in reply to message #53137 |
Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff
Posts: 15100
|
I did try to find a simple way of explaining it, but, well, you've seen the results  |
| |
[ Log in to reply ] |
| |
|
Acorn Arcade forums: Programming: Binary Trees |
