Binary Trees and Bit Reversed Numbers
by Bob Day (bobday.nh@verizon.net)
Copyright (C) November, 2002 by Bob Day. All rights reserved.
While implementing binary tree functions a while back, I noticed that the bit
reversals of the normal counting sequence (1, 2, 3, 4, etc.) fall naturally into
a binary tree.
Here's the problem: If you just take the numbers starting with 1 and counting on
up, here's what you get when you insert them in order into a binary tree:
Building the tree with the "root" on top and proceeding downward, '1' starts the
tree and goes on top. 2 is greater than 1, so it goes below and to the
right of 1. 3 is greater than 2, so it ends up below and to the right of
2. And so on. We get:
1
\
2
\
3
\
4
\
etc.
If we do a search in this tree, we have to search all the numbers in sequence
and it's very inefficient; it's the worst case of what can happen if you just
blindly insert numbers into a binary tree. More complex implementations of
binary trees, such as AVL trees, were developed to combat this problem.
I haven't developed the idea very far, and I don't really know whether it's
useful, but as I said at the beginning, I have noticed that the bit reversals of
the normal number sequence fall naturally into a binary tree order. Here's
an example using the numbers 1 to 15:
Decimal
Binary Bit reversed binary
Bit reversed decimal
1
0001
1000
8
2
0010
0100
4
3
0011
1100
12
4
0100
0010
2
5
0101
1010
10
6
0110
0110
6
7
0111
1110
14
8
1000
0001
1
9
1001
1001
9
10
1010
0101
5
11
1011
1101
13
12
1100
0011
3
13
1101
1011
11
14
1110
0111
7
15
1111
1111
15
Inserting the bit reversed values into a binary tree in the order we
encounter them, we get:
8
/ \
/
\
/
\
/
\
/
\
/
\
4
12
/ \
/ \
/
\
/
\
/
\
/
\
2
6
10
14
/
\
/ \
/ \
/ \
1
3
5 7
9 11
13 15
A perfectly ordered binary tree! Now, if we want to search for a value,
say 11, all we have to do is search for its bit reversal, 3, and it just takes 4
comparisons to obtain a match.
Useful? I don't know. But maybe bit reversal would yield a better
binary tree in the case where you have partially ordered numbers.
Certainly, very few naturally occurring sequences are bit reversed, so it would
be virtually impossible for a tree to degenerate into a linear sequence.
Perhaps a bit reversal step would speed up the average time for inserting a node
into an AVL tree or other more complex tree implementation.