Bug 28: A Long Strange Treap
- This is the simplest and fastest balanced binary search tree: The top-down hash treap.
- Each node has two links (lt is short for less than, gt is short for greater than) and a key.
- The hash function is a one-to-one deterministic pseudorandom function of the search key.
- The hash of a node's key is strictly less than the hash of every one of its descendant keys.
- Lookup is the same as for an ordinary binary search tree, returning true if the key is found.
- Insert returns false if the key was already present in the tree. Otherwise, it creates a new node.
- Insert puts the new node at a nil link or in place of an existing node with a greater hash.
- Insert attaches any existing node and its subtrees onto the new node to produce a single new tree.
- Remove returns false if the key was not present in the tree. Otherwise, it deletes a node.
- Remove interleaves the subtrees of the deleted node to produce a single replacement tree.
Fix The Tiny Bug In This Go Code: