Created
June 25, 2018 17:01
-
-
Save silkeh/bab26fd8f479f1843320c002c5d02e2b to your computer and use it in GitHub Desktop.
Simple Go treap for unscientific benchmarks
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package main | |
import ( | |
"fmt" | |
"math/rand" | |
"time" | |
) | |
func init() { | |
rand.Seed(time.Now().UnixNano()) | |
} | |
// Tree represents a treap | |
type Tree struct { | |
root *Node | |
} | |
// Insert inserts a value into the treap | |
func (t *Tree) Insert(v int) { | |
t.root = t.root.Insert(v) | |
} | |
// Delete removes a value from the treap | |
func (t *Tree) Delete(v int) { | |
t.root = t.root.Delete(v) | |
} | |
// Contains checks if the treap contains a value | |
func (t *Tree) Contains(v int) bool { | |
return t.root.Contains(v) | |
} | |
// Node represents a node in the treap | |
type Node struct { | |
Value, Weight int | |
Left, Right *Node | |
} | |
// NewNode creates a new node with a value and a random weight | |
func NewNode(v int) *Node { | |
return &Node{ | |
Value: v, | |
Weight: rand.Int(), | |
} | |
} | |
// Contains checks if the current node, or related nodes, contain a value | |
func (n *Node) Contains(v int) bool { | |
lower, equal, greater := n.split(v) | |
merge(merge(lower, equal), greater) | |
return equal != nil | |
} | |
// Insert inserts a value in the correct place in or below the current node | |
func (n *Node) Insert(v int) *Node { | |
lower, equal, greater := n.split(v) | |
if equal == nil { | |
equal = NewNode(v) | |
} | |
return merge(merge(lower, equal), greater) | |
} | |
// Delete deletes a node with a specified value from the tree | |
func (n *Node) Delete(v int) *Node { | |
lower, _, greater := n.split(v) | |
return merge(lower, greater) | |
} | |
// split splits the tree between binary equal and greater node-links | |
func (n *Node) split(v int) (lower, equal, greater *Node) { | |
var equalGreater *Node | |
lower, equalGreater = n.splitBinary(v) | |
equal, greater = equalGreater.splitBinary(v+1) | |
return | |
} | |
// splitbinary splits the tree in twain on a value | |
func (n *Node) splitBinary(v int) (left, right *Node) { | |
if n == nil { | |
return | |
} | |
if n.Value < v { | |
left = n | |
n.Right, right = n.Right.splitBinary(v) | |
} else { | |
right = n | |
left, n.Left = n.Left.splitBinary(v) | |
} | |
return | |
} | |
// merge two nodes | |
func merge(left, right *Node) (result *Node) { | |
if left == nil { | |
result = right | |
} else if right == nil { | |
result = left | |
} else if left.Weight > right.Weight { | |
result, left.Right = left, merge(left.Right, right) | |
} else { | |
result, right.Left = right, merge(left, right.Left) | |
} | |
return | |
} | |
func main() { | |
t := &Tree{} | |
cur := 5 | |
res := 0 | |
for i := 1; i < 1000000; i++ { | |
a := i % 3 | |
cur = (cur*57 + 43) % 10007 | |
if a == 0 { | |
t.Insert(cur) | |
} else if a == 1 { | |
t.Delete(cur) | |
} else if a == 2 { | |
if t.Contains(cur) { | |
res++ | |
} | |
} | |
} | |
fmt.Println(res) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment