For example, if the index "1010" or 10 holds data, then starting at the root of the tree, we would recursively move in this order: right, left, right, left. Since the tree is 8 bits, we would have to take four more steps to reach our destination (four more lefts).
Binary trees can be created to hold max indices that aren't a power of 2, but for simplicity's sake, it's easiest to think in these terms.
///////////////////////
// 8-BIT BINARY TREE //
///////////////////////
/*
Supports up to 256 values.
(indexes 0-255).
This works like an array except in memory the
data can be spread across multiple places.
Data indices can be represented in binary form.
*/
// The type.
// This can also be represented as a list of two values if needed.
bintree8
var/l
var/r
// Command which creates a fresh 8-bit binary tree.
// Returns the root node.
proc/BinTree8_Create()
var/bintree8/b = new()
for (var/i = 0 to 255)
BinTree8_Set(b, i, 0, 0)
return b
// Sets an index of the binary tree to a value.
// ONLY PASS THE ROOT NODE AS THE FIRST PARAMETER.
// Also ignore R. It's only used for recursion purposes.
proc/BinTree8_Set(bintree8/T, N=0, V, R=0)
N = Clamp(N,0,255)
if (R < 7)
R += 1
if ((N & 1) == 1)
N = (N-1)/2
if (!T.r) T.r = new/bintree8()
BinTree8_Set(T.r, N, V, R)
else
N = N/2
if (!T.l) T.l = new/bintree8()
BinTree8_Set(T.l, N, V, R)
else
if (N==0)
T.l = V
else
T.r = V
// Same as the Set function except it returns the value at index
// N. R is ignored by the user as it is only used for recursive
// purposes.
proc/BinTree8_Get(bintree8/T, N=0, R=0)
N = Clamp(N,0,255)
if (R < 7)
R += 1
if ((N & 1) == 1)
N = (N-1)/2
return BinTree8_Get(T.r, N, R)
else
N = N/2
return BinTree8_Get(T.l, N, R)
else
if (N==0)
return T.l
else
return T.r
// Returns a giant formatted string containing character data
// which shows binary tree B's data.
proc/BinTree8_ToString(bintree8/B)
var/s = ""
for (var/i = 0 to 255)
s += "[i]: [BinTree8_Get(B, i)]"
s += "\n"
return s
// Helper Clamp function.
// Keeps value N in the range L to H.
proc/Clamp(N,L,H)
return max(min(N,H),L)
// Helper function to turn a decimal value to a binary string.
// returns the string.
proc/DecToBin(N=0)
var/s = ""
while (N > 0)
if ((N & 1) == 1)
N = (N-1)/2
s = "1" + s
else
N = N / 2
s = "0" + s
return s
//////////
// MAIN //
//////////
// Cut this section out if using this snippet in your own projects.
client/New()
..()
var/b = BinTree8_Create()
src << "Setting index [DecToBin(10)] to 'Hello'."
BinTree8_Set(b, 10, "Hello")
src << "Setting index [DecToBin(20)] to 'World'."
BinTree8_Set(b, 20, "World")
src << "Printing the binary tree:"
src << BinTree8_ToString(b)
Example's output:
Setting index 1010 to 'Hello'.
Setting index 10100 to 'World'.
Printing the binary tree:
0: 0
1: 0
2: 0
3: 0
4: 0
5: 0
6: 0
7: 0
8: 0
9: 0
10: Hello
11: 0
12: 0
13: 0
14: 0
15: 0
16: 0
17: 0
18: 0
19: 0
20: World
21: 0
22: 0
... (shortened for convenience)
254: 0
255: 0
Questions to ask:
Does this help with efficiency in any way? Not in BYOND. BYOND already has a /list datum which handles things like this for you. However, when dealing with direct memory in other languages, this can be handy if the developer wished to separate data across memory. Arrays by nature always use a block of memory. When dealing with memory constraints, sometimes a block of memory like this won't fit.
How does it differ from a linked list?
A linked list needs to iterate linearly from start to finish (unless you happen to have a node that isnt the head or the tail). With a binary tree, the amount of iterations to get to the destination is usually always the same. In this example, it's always 8 steps. This saves considerable CPU time in large array sizes.