BUGFIX-66

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:

func hash(key int) int { u64 := uint64(key) u64 ^= 0x_43ec_4853_c7e7_fa78 u64 *= 0x_c4ce_b9fe_1a85_ec53 return int(u64) } type node struct { lt *node gt *node key int } type Treap struct { root *node } func (t *Treap) Lookup(key int) bool { for curr := t.root; curr != nil; { switch { case key < curr.key: curr = curr.lt case key > curr.key: curr = curr.gt default: return true } } return false } func (t *Treap) Insert(key int) bool { hash1 := hash(key) for at := &t.root; ; { curr := *at if curr == nil { *at = &node{key: key} return true } hash2 := hash(curr.key) switch { case hash1 < hash2: case hash1 == hash2: return false case key < curr.key: at = &curr.lt continue default: at = &curr.gt continue } var ( put = &node{key: key} lt = &put.lt gt = &put.gt ) for curr != nil { if curr.key < key { *lt = curr lt = &curr.gt curr = curr.gt continue } *gt = curr gt = &curr.lt curr = curr.lt } *lt = nil *gt = nil *at = put return true } } func (t *Treap) Remove(key int) bool { for at := &t.root; ; { curr := *at switch { case curr == nil: return false case key < curr.key: at = &curr.lt case key > curr.key: at = &curr.gt continue } var ( lt = curr.lt gt = curr.gt ) for { switch { case lt == nil: *at = gt return true case gt == nil: *at = lt return true case hash(lt.key) < hash(gt.key): *at = lt at = &lt.gt lt = lt.gt default: *at = gt at = &gt.lt gt = gt.lt } } } }

To receive a hint, submit unfixed code.