Splay-дерево

class Splay {
  Node root;

  private Node rotateRight(Node h) {
   Node x = h.lNode;
   h.lNode = x.rNode;
   x.rNode = h;
   return x;
  }

  private Node rotateLeft(Node h) {
   Node x = h.rNode;
   h.rNode = x.lNode;
   x.lNode = h;
   return x;
  }

  private Node splay(Node h, int key) {
   if (h == null)
    return null;

   if (key < h.key) {
    if (h.lNode == null) {
     return h;
    }
    if (key < h.lNode.key) {
     h.lNode.lNode = splay(h.lNode.lNode, key);
     h = rotateRight(h);
    } else if (key > h.lNode.key) {
     h.lNode.rNode = splay(h.lNode.rNode, key);
     if (h.lNode.rNode != null)
      h.lNode = rotateLeft(h.lNode);
    }
    if (h.lNode == null)
     return h;
    else
     return rotateRight(h);
   }
   if (key > h.key) {
    if (h.rNode == null) {
     return h;
    }
    if (key < h.rNode.key) {
     h.rNode.lNode = splay(h.rNode.lNode, key);
     if (h.rNode.lNode != null)
      h.rNode = rotateRight(h.rNode);
    } else if (key > h.rNode.key) {
     h.rNode.rNode = splay(h.rNode.rNode, key);
     h = rotateLeft(h);
    }

    if (h.rNode == null)
     return h;
    else
     return rotateLeft(h);
   }

   return h;
  }

  public void insert(int key) {
   if (root == null) {
    root = new Node(key);
    return;
   }

   root = splay(root, key);

   if (key < root.key) {
    Node n = new Node(key);
    n.lNode = root.lNode;
    n.rNode = root;
    root.lNode = null;
    root = n;
   } else if (key > root.key) {
    Node n = new Node(key);
    n.rNode = root.rNode;
    n.lNode = root;
    root.rNode = null;
    root = n;
   }

  }

  public void remove(int key) {
   if (root == null)
    return;

   root = splay(root, key);

   if (root.key == key) {
    if (root.lNode == null) {
     root = root.rNode;
    } else {
     Node x = root.rNode;
     root = root.lNode;
     root = splay(root, key);
     root.rNode = x;
    }
   }
  }

  Node next(int key) {
   if (root == null) {
    return null;
   }
   root = splay(root, key);
   return next(key, root);
  }
  
  Node next(int key, Node root) {
   if (root == null) return null;
   Node best = null;
   if (root.key > key) best = root;
   if (root.key <= key) {
    Node tryNode = next(key, root.rNode);
    if (tryNode != null) {
     if (best == null || tryNode.key < best.key) best = tryNode;
    }
   } else {
    Node tryNode = next(key, root.lNode);
    if (tryNode != null) {
     if (best == null || tryNode.key < best.key) best = tryNode;
    }
   }
   return best;
  }

  Node prev(int key) {
   if (root == null) {
    return null;
   }
   root = splay(root, key);
   return prev(key, root);
  }
  
  Node prev(int key, Node root) {
   if (root == null) return null;
   Node best = null;
   if (root.key < key) best = root;
   if (root.key < key) {
    Node tryNode = prev(key, root.rNode);
    if (tryNode != null) {
     if (best == null || tryNode.key > best.key) best = tryNode;
    }
   } else {
    Node tryNode = prev(key, root.lNode);
    if (tryNode != null) {
     if (best == null || tryNode.key > best.key) best = tryNode;
    }
   }
   return best;
  }


  boolean contains(int key) {
   if (root == null) {
    return false;
   } else {
    root = splay(root, key);
    if (root.key == key) return true;
    return false;      
   }
  }
}

class Node {
  int key;
  Node lNode, rNode;

  Node(int key) {
   this.key = key;
  }
}