h["a"] = 1 h[1.1] = 2 # => TypeError because "a" <=> 1.1 returns nil h.delete(1.1) # => ditto h[1.1] # => nil, not error Closes #4.
Change internal rebalance timing. Do convert (b (r r)) -> (r (b b)) to make balance of tree be perfect after insert. Before this commit, the above convert run at the next insert. It includes related 4 updates for the test. 2 tests for delete indicate that the balance of the tree is better than before. Other 2 tests for insert indicate that the balance of the tree is better than before at the first insert, and the balance is the same as before at the second insert.
To reduce the same method definitions for Node and EmptyNode.
Allow #values to be called on empty trees
Do not force keys to be strings
Keys must be Comparable (defines the <=> method).
Do red pull-up check and rotation at a time.
Follows name convention of tree data structure.
With help from 'protected' of Ruby.
run this with ruby-prof
It's the only different behavior between AVLTree and RadixTree. RadixTree compares keys by char-to-char comparison but AVLTree just uses String#<=>
RadixTree is from https://github.com/nahi/radix_tree You can install it with 'gem install radix_tree'
It utilized delete_min for node delete always but the right branch of the deleted node can be EMPTY. Use delete_min/delete_max properly.