import java.util.Stack;

/**
 * Created by Administrator on 2016/5/6.
 */
public class MyAvlTree<AnyType extends Comparable<? super AnyType>> {
  private static class AvlNode<AnyType> {
    AvlNode(AnyType theElement) {
      this(theElement, null, null);
    }

    AvlNode(AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
      height = 0;
    }

    AnyType element;
    AvlNode<AnyType> left;
    AvlNode<AnyType> right;
    int height;
  }

  private AvlNode<AnyType> root;
  private int modCount;

  public MyAvlTree() {
    root = null;
    modCount = 0;
  }

  public void insert(AnyType item) {
    root = insert(item, root);
  }

  private AvlNode<AnyType> insert(AnyType item, AvlNode<AnyType> tree) {
    if (null == tree) {
      modCount++;
      return new AvlNode<>(item);
    }

    int compareResult = compare(item, tree.element);

    if (compareResult > 0) {
      tree.right = insert(item, tree.right);
      if (height(tree.right) - height(tree.left) == 2) {
        if (compare(item, tree.right.element) > 0) {
          tree = rotateWithRightChild(tree);
        } else {
          tree = doubleWithRightChild(tree);
        }
      }
    } else if (compareResult < 0) {
      tree.left = insert(item, tree.left);
      if (height(tree.left) - height(tree.right) == 2) {
        if (compare(item, tree.left.element) < 0) {
          tree = rotateWithLeftChild(tree);
        } else {
          tree = doubleWithLeftChild(tree);
        }
      }
    }

    tree.height = max(height(tree.left), height(tree.right)) + 1;
    return tree;
  }

  private int max(int a, int b) {
    return a > b ? a : b;
  }

  private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> node) {
    AvlNode<AnyType> leftNode = node;
    node = node.right;
    leftNode.right = node.left;
    node.left = leftNode;
    node.left.height = max(height(node.left.left), height(node.left.right)) + 1;
    node.height = max(height(node.left), height(node.right)) + 1;
    return node;
  }

  private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> node) {
//    AvlNode<AnyType> leftNode = node;
//    node = node.right.left;
//    leftNode.right.left = node.right;
//    node.right = leftNode.right;
//    leftNode.right = node.left;
//    node.left = leftNode;
//
//    node.left.height = max(height(node.left.left), height(node.left.right)) + 1;
//    node.right.height = max(height(node.right.left), height(node.right.right)) + 1;
//    node.height = max(height(node.left), height(node.right)) + 1;
    node.right = rotateWithLeftChild(node.right);
    return rotateWithRightChild(node);
  }

  private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> node) {
    AvlNode<AnyType> rightNode = node;
    node = node.left;
    rightNode.left = node.right;
    node.right = rightNode;

    node.right.height = max(height(node.right.left), height(node.right.right)) + 1;
    node.height = max(height(node.left), height(node.right)) + 1;

    return node;
  }

  private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> node) {
//    AvlNode<AnyType> rightNode = node;
//    node = node.left.right;
//    rightNode.left.right = node.left;
//    node.left = rightNode.left;
//    rightNode.left = node.right;
//    node.right = rightNode;
//
//    node.left.height = max(height(node.left.left), height(node.left.right)) + 1;
//    node.right.height = max(height(node.right.left), height(node.right.right)) + 1;
//    node.height = max(height(node.left), height(node.right)) + 1;
    node.left = rotateWithRightChild(node.left);
    return rotateWithLeftChild(node);
  }

  private int height(AvlNode<AnyType> node) {
    return null == node ? -1 : node.height;
  }

  private int compare(AnyType a, AnyType b) {
    return a.compareTo(b);
  }

  public void makeEmpty() {
    root = null;
  }

  public boolean isEmpty() {
    return null == root;
  }

  public int size() {
    return size(root.left) + size(root.right) + 1;
  }

  private int size(AvlNode<AnyType> tree) {
    if (null == tree) {
      return 0;
    }

    return size(tree.left) + size(tree.right) + 1;
  }

  public void remove(AnyType item) {
    root = remove(item, root);
  }

  private AvlNode<AnyType> remove(AnyType item, AvlNode<AnyType> tree) {
    if (null == tree) {
      return null;
    }

    int compareResult = compare(item, tree.element);

    if (compareResult > 0) {
      tree.right = remove(item, tree.right);
      if (height(tree.left) - height(tree.right) == 2) {
        tree = rotateWithLeftChild(tree);
      }
    } else if (compareResult < 0) {
      tree.left = remove(item, tree.left);
      if (height(tree.right) - height(tree.left) == 2) {
        tree = rotateWithRightChild(tree);
      }
    } else {
      if (null != tree.left && null != tree.right) {
        tree.element = findMin(tree.right).element;
        tree.right = remove(tree.element, tree.right);
        tree.height = max(height(tree.left), height(tree.right)) + 1;
      } else {
        tree = null != tree.left ? tree.left : tree.right;
      }
    }

    return tree;
  }

  public AnyType findMin() {
    return findMin(root).element;
  }

  private AvlNode<AnyType> findMin(AvlNode<AnyType> tree) {
    if (null == tree) {
      return null;
    } else if (null == tree.left) {
      return tree;
    }

    return findMin(tree.left);
  }

  public AnyType findMax() {
    return findMax(root).element;
  }

  private AvlNode<AnyType> findMax(AvlNode<AnyType> tree) {
    if (null == tree) {
      return null;
    } else if (null == tree.right) {
      return tree;
    }

    return findMax(tree.right);
  }

  public boolean isAvlTree() {
    return isAvlTree(root);
  }

  private boolean isAvlTree(AvlNode<AnyType> tree) {
    if (null == tree) {
      return true;
    } else if (height(root) != max(height(root.left), height(root.right)) + 1) {
      return false;
    }

    return isAvlTree(tree.left) && isAvlTree(tree.right);
  }

  public void insertWithoutRecursion(AnyType item) {
    Stack<AvlNode<AnyType>> stack = new Stack<>();
    AvlNode<AnyType> pointer = root;
    while (null != pointer) {
      stack.push(pointer);

      int compareResult = compare(item, pointer.element);

      if (compareResult < 0) {
        pointer = pointer.left;
      } else if (compareResult > 0) {
        pointer = pointer.right;
      } else {
        return;
      }
    }

    pointer = new AvlNode<>(item);

    while (!stack.isEmpty()) {
      pointer = stack.pop();
      pointer.height = max(height(pointer.left), height(pointer.right)) + 1;
    }
  }
}

import java.util.Stack;

/**
 * 带有比当前节点小的最大子节点和比当前节点大的最小子节点的二叉树，该树可以从两个角度看：树或双向链表
 * 因为每个节点都保存有前一个节点和后一个几点的指针，因而可以看做是一个双向链表，并且该链表是经过排序的链表
 */
public class MyTreeSet<AnyType extends Comparable<? super AnyType>> implements Iterable<AnyType> {
  private static class BinaryNode<AnyType> {
    BinaryNode() {}

    BinaryNode(AnyType theElement) {
      this(theElement, null, null, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt, BinaryNode<AnyType> pv, BinaryNode<AnyType> nt) {
      element = theElement;
      left = lt;
      right = rt;
      prev = pv;
      next = nt;
    }

    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
    BinaryNode<AnyType> prev;
    BinaryNode<AnyType> next;
  }

  public MyTreeSet() {
    root = null;
    begin = new BinaryNode<>();
    end = new BinaryNode<>(null, null, null, begin, null);
    begin.next = end;
    modCount = 0;
  }

  public void makeEmpty() {
    modCount++;
    root = null;
    begin.next = end;
    end.prev = begin;
  }

  public boolean isEmpty() {
    return null == root && begin.next == end && end.prev == begin;
  }

  public boolean contains(AnyType x) {
    return contains(x, root);
  }

  public AnyType findMin() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return begin.next.element;
    }
  }

  public AnyType findMax() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return end.prev.element;
    }
  }

  public void insert(AnyType x) {
    root = insert(x, root, begin);
  }

  public void remove(AnyType x) {
    root = remove(x, root);
  }

  public void printTree() {
    if (isEmpty()) {
      System.out.println("Empty Tree");
    } else {
      BinaryNode<AnyType> pointer = begin.next;
      while (pointer != end) {
        System.out.print(pointer.element + "\t");
        pointer = pointer.next;
      }
    }
  }

  private boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return false;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      return contains(x, t.left);
    } else if (compareResult > 0) {
      return contains(x, t.right);
    } else {
      return true;
    }
  }

  private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.left){
      return t;
    }

    return findMin(t.left);
  }

  private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.right) {
      return t;
    }

    return findMin(t.right);
  }

  /**
   * 插入一个节点
   * @param x 要插入的节点值
   * @param t 要插入的位置
   * @param pv 要插入位置之前的最大节点
   * @return 插入后的子树
   */
  private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t, BinaryNode<AnyType> pv) {
    if (null == t) {
      modCount++;
      BinaryNode<AnyType> result = new BinaryNode<>(x, null, null, pv, pv.next);
      pv.next.prev = result;
      pv.next = result;
      return result;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = insert(x, t.left, t.prev);
    } else if (compareResult > 0) {
      t.right = insert(x, t.right, t);
    }

    return t;
  }

  private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return t;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = remove(x, t.left);
    } else if (compareResult > 0) {
      t.right = remove(x, t.right);
    } else if (t.left != null && t.right != null) {
      t.element = findMin(t.right).element;
      t.right = remove(t.element, t.right);
    } else {
      modCount++;
      t.prev.next = t.next;
      t.next.prev = t.prev;
      t = null != t.left ? t.left : t.right;
    }

    return t;
  }

  public int size() {
    int result = 0;
    BinaryNode<AnyType> pointer = begin.next;
    while (pointer != end) {
      pointer = pointer.next;
      result++;
    }
    return result;
  }

  public void inOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()){
        pointer = stack.pop();
        visit(pointer);
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void inOrder1() {
    BinaryNode<AnyType> pointer = begin.next;
    while (pointer != end) {
      visit(pointer);
      pointer = pointer.next;
    }
  }

  public void preOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        visit(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()) {
        pointer = stack.pop();
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void laterOrder1() {
    Stack<StackElement<AnyType>> stack = new Stack<>();
    StackElement<AnyType> pointer = new StackElement<>(root, Tag.LEFT);

    while (true) {
      if (null != pointer.node && pointer.tag == Tag.LEFT) {
        stack.push(pointer);
        pointer = new StackElement<>(pointer.node.left, Tag.LEFT);
      } else if (!stack.isEmpty()){
        pointer = stack.peek();
        if (Tag.LEFT == pointer.tag) {
          pointer.tag = Tag.RIGHT;
          pointer = new StackElement<>(pointer.node.right, Tag.LEFT);
        } else {
          pointer = stack.pop();
          visit(pointer.node);
        }
      } else {
        break;
      }
    }

  }

  public void laterOrder() {
    if (null == root) {
      return;
    }
    Stack<StackElement<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;
    StackElement<AnyType> element;

    while (true) {
      while (null != pointer) { // 找到最左节点
        element = new StackElement<>(pointer, Tag.LEFT);
        stack.push(element);
        pointer = pointer.left;
      }

      element = stack.pop();
      pointer = element.node;

      while (Tag.RIGHT == element.tag) {  // 如果是从右子树返回，则对其进行访问
        visit(pointer);
        if (stack.isEmpty()) {
          return;
        }
        element = stack.pop();
        pointer = element.node;
      }

      element.tag = Tag.RIGHT;  // 左边节点访问完则向右下滑一个节点开始访问右边节点
      stack.push(element);
      pointer = pointer.right;
    }
  }

  private void visit(BinaryNode<AnyType> node) {
    System.out.print(node.element.toString() + "\t");
  }

  private BinaryNode<AnyType> begin;
  private BinaryNode<AnyType> end;
  private BinaryNode<AnyType> root;
  private int modCount;

  public java.util.Iterator<AnyType> iterator() {
    return new MyTreeSetIterator();
  }

  private class MyTreeSetIterator implements java.util.Iterator<AnyType> {
    private BinaryNode<AnyType> current;
    private Stack<BinaryNode<AnyType>> stack;
    private int expectedModCount = modCount;
    private boolean okToRemove = false;

    public MyTreeSetIterator() {
      stack = new Stack<>();
      pushLeftMost(root);
    }

    public boolean hasNext() {
      return !stack.isEmpty();
    }

    public AnyType next() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!hasNext()) {
        throw new java.util.NoSuchElementException();
      }

      current = stack.pop();
      pushLeftMost(current.right);
      okToRemove = true;

      return current.element;
    }

    public void remove() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!okToRemove) {
        throw new IllegalStateException();
      }

      MyTreeSet.this.remove(current.element);
      expectedModCount++;
    }

    private void pushLeftMost(BinaryNode<AnyType> tree) {
      BinaryNode<AnyType> pointer = tree;
      while (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      }
    }
  }

  private class StackElement<AnyType> {
    Tag tag;
    BinaryNode<AnyType> node;

    public StackElement(BinaryNode<AnyType> n, Tag t) {
      node = n;
      tag = t;
    }
  }
  enum Tag{LEFT, RIGHT}
}

class UnderFlowException extends Exception {}

import java.util.Stack;

/**
 * @auther zhangxufeng@uworks.cc 2016/05/03
 */
public class MyTreeSet<AnyType extends Comparable<? super AnyType>> implements Iterable<AnyType> {
  private static class BinaryNode<AnyType> {
    BinaryNode(AnyType theElement) {
      this(theElement, null, null);
    }

    BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
      element = theElement;
      left = lt;
      right = rt;
    }

    AnyType element;
    BinaryNode<AnyType> left;
    BinaryNode<AnyType> right;
  }

  public MyTreeSet() {
    root = null;
    modCount = 0;
  }

  public void makeEmpty() {
    modCount++;
    root = null;
  }

  public boolean isEmpty() {
    return null == root;
  }

  public boolean contains(AnyType x) {
    return contains(x, root);
  }

  public AnyType findMin() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return findMin(root).element;
    }
  }

  public AnyType findMax() throws UnderFlowException {
    if (isEmpty()) {
      throw new UnderFlowException();
    } else {
      return findMax(root).element;
    }
  }

  public void insert(AnyType x) {
    root = insert(x, root);
  }

  public void remove(AnyType x) {
    root = remove(x, root);
  }

  public void printTree() {
    if (isEmpty()) {
      System.out.println("Empty Tree");
    } else {
      printTree(root);
    }
  }

  private void printTree(BinaryNode<AnyType> t) {
    if (null != t) {
      printTree(t.left);
      System.out.println(t.element);
      printTree(t.right);
    }
  }

  private boolean contains(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return false;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      return contains(x, t.left);
    } else if (compareResult > 0) {
      return contains(x, t.right);
    } else {
      return true;
    }
  }

  private BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.left){
      return t;
    }

    return findMin(t.left);
  }

  private BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
    if (null == t) {
      return null;
    } else if (null == t.right) {
      return t;
    }

    return findMax(t.right);
  }

  private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      modCount++;
      return new BinaryNode<AnyType>(x, null, null);
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = insert(x, t.left);
    } else if (compareResult > 0) {
      t.right = insert(x, t.right);
    } else {}

    return t;
  }

  private BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
    if (null == t) {
      return t;
    }

    int compareResult = x.compareTo(t.element);

    if (compareResult < 0) {
      t.left = remove(x, t.left);
    } else if (compareResult > 0) {
      t.right = remove(x, t.right);
    } else if (t.left != null && t.right != null) {
      t.element = findMin(t.right).element;
      t.right = remove(t.element, t.right);
    } else {
      modCount++;
      t = null != t.left ? t.left : t.right;
    }

    return t;
  }

  public int size() {
    return size(root);
  }

  private int size(BinaryNode<AnyType> tree) {
    if (null == tree) {
      return 0;
    }

    return size(tree.left) + size(tree.right) + 1;
  }

  public void inOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()){
        pointer = stack.pop();
        visit(pointer);
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void preOrder() {
    Stack<BinaryNode<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;

    while (true) {
      if (null != pointer) {
        stack.push(pointer);
        visit(pointer);
        pointer = pointer.left;
      } else if (!stack.isEmpty()) {
        pointer = stack.pop();
        pointer = pointer.right;
      } else {
        break;
      }
    }
  }

  public void laterOrder1() {
    Stack<StackElement<AnyType>> stack = new Stack<>();
    StackElement<AnyType> pointer = new StackElement<>(root, Tag.LEFT);

    while (true) {
      if (null != pointer.node && pointer.tag == Tag.LEFT) {
        stack.push(pointer);
        pointer = new StackElement<>(pointer.node.left, Tag.LEFT);
      } else if (!stack.isEmpty()){
        pointer = stack.peek();
        if (Tag.LEFT == pointer.tag) {
          pointer.tag = Tag.RIGHT;
          pointer = new StackElement<>(pointer.node.right, Tag.LEFT);
        } else {
          pointer = stack.pop();
          visit(pointer.node);
        }
      } else {
        break;
      }
    }

  }

  public void laterOrder() {
    if (null == root) {
      return;
    }
    Stack<StackElement<AnyType>> stack = new Stack<>();
    BinaryNode<AnyType> pointer = root;
    StackElement<AnyType> element;

    while (true) {
      while (null != pointer) { // 找到最左节点
        element = new StackElement<>(pointer, Tag.LEFT);
        stack.push(element);
        pointer = pointer.left;
      }

      element = stack.pop();
      pointer = element.node;

      while (Tag.RIGHT == element.tag) {  // 如果是从右子树返回，则对其进行访问
        visit(pointer);
        if (stack.isEmpty()) {
          return;
        }
        element = stack.pop();
        pointer = element.node;
      }

      element.tag = Tag.RIGHT;  // 左边节点访问完则向右下滑一个节点开始访问右边节点
      stack.push(element);
      pointer = pointer.right;
    }
  }

  public void breadthOrder() {
    Queue<BinaryNode<AnyType>> queue = new Queue<>();
    queue.enQueue(root);

    while (!queue.isEmpty()) {
      BinaryNode<AnyType> pointer = queue.deQueue();
      visit(pointer);
      if (null != pointer.left) {
        queue.enQueue(pointer.left);
      }
      if (null != pointer.right) {
        queue.enQueue(pointer.right);
      }
    }
  }

  private void visit(BinaryNode<AnyType> node) {
    System.out.print(node.element.toString() + "\t");
  }

  private BinaryNode<AnyType> root;
  private int modCount;

  public java.util.Iterator<AnyType> iterator() {
    return new MyTreeSetIterator();
  }

  private class MyTreeSetIterator implements java.util.Iterator<AnyType> {
    private BinaryNode<AnyType> current;
    private Stack<BinaryNode<AnyType>> stack;
    private int expectedModCount = modCount;
    private boolean okToRemove = false;

    public MyTreeSetIterator() {
      stack = new Stack<>();
      pushLeftMost(root);
    }

    public boolean hasNext() {
      return !stack.isEmpty();
    }

    public AnyType next() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!hasNext()) {
        throw new java.util.NoSuchElementException();
      }

      current = stack.pop();
      pushLeftMost(current.right);
      okToRemove = true;

      return current.element;
    }

    public void remove() {
      if (modCount != expectedModCount) {
        throw new java.util.ConcurrentModificationException();
      }
      if (!okToRemove) {
        throw new IllegalStateException();
      }

      MyTreeSet.this.remove(current.element);
      expectedModCount++;
    }

    private void pushLeftMost(BinaryNode<AnyType> tree) {
      BinaryNode<AnyType> pointer = tree;
      while (null != pointer) {
        stack.push(pointer);
        pointer = pointer.left;
      }
    }
  }

  private class StackElement<AnyType> {
    Tag tag;
    BinaryNode<AnyType> node;

    StackElement(BinaryNode<AnyType> n, Tag t) {
      node = n;
      tag = t;
    }
  }
  enum Tag{LEFT, RIGHT};
}

class UnderFlowException extends Exception {}