3
$\begingroup$

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, foo2... so tree balance is an issue.

I considered balancing and auto-balancing algorithms, but then I realized that the hash for a key given a good hash function should have a 50% average chance for left/right. And I already had a hash function so that meant no additional code. So I would get a balanced tree for free(edit: at no point did I want to imply a perfectly balanced tree, this is emergent behavior).

I wanted to check if my theory was correct. When I search for BSTs, hashes, and hash trees, however, no relevant information turns up.

What is the term for a binary search tree that balances itself by using a hash?

edit: I am going to accept the answer because if something doesn't have a name it just doesn't, but I tested this because some comments and asides imply that it is worse than it actually is.

I tested a sorted list of 468685 words containing both English words and "elite" password cracking words.

balanced-tree:    worst(19)     average(18.84)
edlin-tree:       worst(47)     average(22.72)
edlin-tree(SHA2): worst(46)     average(23.25)
regular BST:      worst(468685) average(234342.50)

So it's not going to replace your language library algorithms but, as stated in the accepted answer, it is obviously logarithmic.

As for the hash function(Which for reference is add+xorshift as in:

do{h+=*s;h^=h<<left1;h^=h>>right;h^=h<<left2;}while(*s);

), I have also tested how bad it is by comparing collisions to the expected value.

8 bits:
   expected :  468428.99
   axs      :  468429
   SHA2-256 :  468429

16 bits:
   expected :  403200.35
   axs      :  403189
   SHA2-256 :  403198

24 bits:
   expected :    6485.99
   axs      :    6451
   SHA2-256 :    6433

31 bits:
   expected :      51.14
   axs      :      59
   SHA2-256 :      47

32 bits:
   expected :      25.57
   axs      :      30
   SHA2-256 :      20

33 bits:
   expected :      12.79
   axs      :      14
   SHA2-256 :      11

35 bits:
   expected :       3.19
   axs      :       7
   SHA2-256 :       2

36 bits:
   expected :       1.59
   axs      :       1
   SHA2-256 :       2

37 bits:
   expected :       0.80
   axs      :       0
   SHA2-256 :       0

So, while it appears to lag for some bitnesses, it generally follows the expected values, both for tree depth and collisions. What would a hash which is not good for your input mean? That your input generates a sequence when passed to it? That would be ridiculously unlikely statistically speaking. Worst case is O(n) but you are not going to see it.

The algorithm is not good compared to AVL or red-black, even though insertion will probably be faster generally, however it beats a linked list or betting on input for a BST any day.

$\endgroup$
  • 2
    $\begingroup$ If you have a good hash algorithm, why are you using a tree? A hash into a hash table should get a hit on the first bucket, or maybe one more comparison for the linked bucket. $\endgroup$ – Guy Coder Jul 3 '14 at 16:17
  • $\begingroup$ The reason you are not finding anything is because hashes work with hash tables and not binary trees. $\endgroup$ – Guy Coder Jul 3 '14 at 16:23
  • 1
    $\begingroup$ OK. AFAIK there is no term because as I said hash functions are meant to work with hash tables. If you think about it in terms of comparison operations of getting from a key to a value, the best one can get is 1 and that would be using a perfect hash, which IIRC can be done for a finite fixed set. If one can find no hash then one uses a balanced tree which you have tried. If one finds a hash that in general works better than that, then one uses a hash with a hash map. $\endgroup$ – Guy Coder Jul 3 '14 at 16:50
  • 1
    $\begingroup$ Maybe that's just me, but I'd rather rely on AVL-rotations than on the hashfunction being "good". You might not even control it. $\endgroup$ – Raphael Jul 3 '14 at 21:39
  • 1
    $\begingroup$ Here's the one thing that everyone needs to know: the only reason to balance a BST is to avoid worst-case pathological behaviour. There has been a lot of research on which balancing scheme is "best" in a practical environment, and all across this research there is a consistent answer: they all do pretty much the same. So which balancing scheme should you pick? Use other criteria than performance to decide. RB trees only require an extra bit, and you can often scrounge that. BBB trees store the size of the subtree in each node, and sometimes that's information you need for other reasons. $\endgroup$ – Pseudonym Oct 4 '14 at 1:06
4
$\begingroup$

To answer the explicitly asked question: There probably is no specific name for this data structure since noone has bothered to use or study it.

Regarding the underlying question: Even using a "good" hash function, you can not expect as well a degree of balanced as you think:

Looking at the node with key $foo$, we see that all keys (in the subtree below $foo$) with a hash smaller than $h(foo)$ will be in the left subtree, while all those with a larger hash will be in the right subtree. So the balancedness of the tree will depend on how far $h(foo)$ is away from the center. This has an expected value of $\frac 12 N$, where $N$ is the number of hash values that belong in the subtree below $foo$. So we can expect an average weight balance of $1:3$ in each node. While this is still enough to give logarithmic expected height, it is already notably worse than the $1:1.6$ balance an AVL tree has in the worst case. Factoring in the additional risk of the hash function being not "good" for the data of a specific run, the idea quickly becomes unattractive.

Additionally, in many practical scenarios you have the option of using a library implementation of AVL trees, while you have to implement the "hash tree" yourself. So your "for free" argument will typically be the other way round.

$\endgroup$
3
$\begingroup$

It's not that the analysis in the previous answer is wrong regarding the weight balance, but the answer I was looking for was that this algorithm is basically equivalent to a http://en.wikipedia.org/wiki/Random_binary_tree .

The longest path is $$4.311 \times \log_{e} n$$


EDIT: I'll update this answer because the information below was relatively hard to come by.

The magic number comes from:

Reed, Bruce (2003), "The height of a random binary search tree", Journal of the ACM 50 (3): 306–332, doi:10.1145/765568.765571. 

The author shows that the expected height of a random binary tree is $E(H_n ) = \alpha \log_e n − \beta\log_e \log_e n + O(1)$, where $α = 4.311\ldots$ and $β = 1.953\ldots$. The magic number represents the upper bound.

The expected height happens to be $\approx\log_{\frac{4}{3}} n$, which is somewhat intuitive when you consider that each parent node represents a random pivot partitioning the node search space like in random quicksort.

Finally, the average access time for any given node is actually $\approx\log_{\frac{4}{3}} \sqrt{n}$(I can't find a reference for this).

That makes using hash as the key $\approx1.205\log_2n$ or 20% slower on average than a self-balancing binary tree.*

Similar structures with various trade-offs include the hash-as-priority treap, hash+b-tree, and hash+suffix tree. The suffix tree is only a bit less lazy than the proposed structure and provides expected $\log_2n$ access time.

[*] Many balanced tree algorithms also have a worst-case height upper bound of $\log_\phi n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.