Code shared from the Rust Playground

playground.rs

#![feature(box_syntax)]

#![feature(rustc_private)] extern crate rand;

use std::ptr::null_mut;

struct Node {
    x: i32,
    y: i32,
    left: *mut Node,
    right: *mut Node,
}

impl Drop for Node {
    fn drop(&mut self) {
        if !self.left.is_null() {
            unsafe { Box::from_raw(self.left); }
        }
        if !self.right.is_null() {
            unsafe { Box::from_raw(self.right); }
        }
    }
}

impl Node {
    fn new(x: i32) -> Self {
        Self {
            x,
            y: rand::random::<i32>(),
            left: null_mut(),
            right: null_mut(),
        }
    }
}

struct Tree { root: *mut Node }

impl Tree {
    fn new() -> Self {
        Self { root: null_mut() }
    }

    fn has_value(&mut self, x: i32) -> bool {
        let mut lower = null_mut();
        let mut equal = null_mut();
        let mut greater = null_mut();
        split5(self.root, &mut lower, &mut equal, &mut greater, x);
        let res = !equal.is_null();
        self.root = merge3(lower, equal, greater);
        res
    }

    fn insert(&mut self, x: i32) {
        let mut lower = null_mut();
        let mut equal = null_mut();
        let mut greater = null_mut();
        split5(self.root, &mut lower, &mut equal, &mut greater, x);
        if equal.is_null() {
            equal = Box::into_raw(box Node::new(x));
        }

        self.root = merge3(lower, equal, greater);
    }

    fn erase(&mut self, x: i32) {
        let mut lower = null_mut();
        let mut equal = null_mut();
        let mut greater = null_mut();
        split5(self.root, &mut lower, &mut equal, &mut greater, x);
        self.root = merge(lower, greater);
        if !equal.is_null() {
            unsafe { Box::from_raw(equal); }
        }
    }
}

fn merge(lower: *mut Node, greater: *mut Node) -> *mut Node {
    if lower.is_null() {
        return greater;
    }

    if greater.is_null() {
        return lower;
    }

    unsafe {
        if (*lower).y < (*greater).y {
            (*lower).right = merge((*lower).right, greater);
            lower
        } else {
            (*greater).left = merge(lower, (*greater).left);
            greater
        }
    }
}

fn merge3(lower: *mut Node, equal: *mut Node, greater: *mut Node) -> *mut Node {
    merge(merge(lower, equal), greater)
}

fn split(orig: *mut Node, lower: *mut *mut Node,
         greater_or_equal: *mut *mut Node, val: i32) {
    unsafe {
        if orig.is_null() {
            *lower = null_mut();
            *greater_or_equal = null_mut();
            return;
        }

        if (*orig).x < val {
            *lower = orig;
            split((**lower).right, &mut (**lower).right, greater_or_equal, val);
        } else {
            *greater_or_equal = orig;
            split((**greater_or_equal).left, lower, &mut (**greater_or_equal).left, val);
        }
    }
}

fn split5(orig: *mut Node, lower: *mut *mut Node,
          equal: *mut *mut Node, greater: *mut *mut Node, val: i32) {
    let mut equal_or_greater = null_mut();
    split(orig, lower, &mut equal_or_greater, val);
    split(equal_or_greater, equal, greater, val + 1);
}

fn main() {
    let mut tree = Tree::new();
    let mut cur: i32 = 5;
    let mut res: i32 = 0;

    for i in 1 .. 1_000_000 {
        let mode = i % 3;
        cur = (cur * 57 + 43) % 10_007;
        if mode == 0 {
            tree.insert(cur);
        } else if mode == 1 {
            tree.erase(cur);
        } else if mode == 2 {
            if tree.has_value(cur) { res += 1 };
        }
    }

    println!("{}", res);
}