/**
   A simple binary search tree class, generic in the type of the value stored
   in the tree.
  */


class BinarySearchTree <V extends Comparable<V>>
  
  BinarySearchTree()
    root = null


  void
  add(V v)
    root = add(v, root)


  private Node
  add(V v, Node root)

    if (root == null)
      return new Node(v, null, null)

    final int i = root.value.compareTo(v)

    if (i > 0)
      root.left = add(v, root.left)
    else if (i < 0)
      root.right = add(v, root.right)

    return root


  void
  delete(V v)
    root = delete(v, root)


  private Node
  delete(V v, Node root)

    if (root != null)
      final int c = root.value.compareTo(v)

      if (c > 0)
	root.left = delete(v, root.left)
      else if (c < 0)
	root.right = delete(v, root.right)
      else
	Pair<V, Node> p

	if (root.left != null)
	  p = extractMax(root.left)
	  root.left = p.snd
	else if (root.right != null)
	  p = extractMin(root.right)
	  root.right = p.snd
	else 
	  return null

	root.value = p.fst

    return root


  private Pair<V, Node>
  extractMax(Node root)
    if (root.left == null)
      return Pair.newPair(root.value, root.left)
    else
      Pair<V, Node> p = extractMax(root.right)
      root.right = p.snd
      return Pair.newPair(p.fst, root)


  private Pair<V, Node>
  extractMin(Node root)
    if (root.left == null)
      return Pair.newPair(root.value, root.right)
    else
      Pair<V, Node> p = extractMin(root.left)
      root.left = p.snd
      return Pair.newPair(p.fst, root)


  boolean
  find(V v)
    return find(v, root)


  private boolean
  find(V v, Node root)

    if (root == null)
      return false

    final int i = root.value.compareTo(v)

    if (i < 0)
      return find(v, root.right)
    if (i == 0)
      return true

    return find(v, root.left)


  public static void
  main(String args[])

    final BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>()
    int i
    final int n = 10

    final Integer v[] = PermutedIota.makePermutedIota(n)

    for (int j: v)
      bst.add(j)

    for (i = 1; i <= n; i++)
      assert bst.find(i)


  private class
  Node

    Node(V v, Node l, Node r)
      value = v
      left = l
      right = r

    Node left, right
    V value


  private Node root


// $Log:$