package 查找;

import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdOut;

public class BST<Key extends Comparable<Key>, Value> {
  private class Node {
    private Key key; // 鍵
    private Value value;// 值
    private Node left, right; // 指向子樹的鏈接
    private int n; // 以該節(jié)點(diǎn)為根的子樹中的節(jié)點(diǎn)總數(shù)

    public Node(Key key, Value val, int n) {
      this.key = key;
      this.value = val;
      this.n = n;
    }
  }

  private Node root;

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

  private int size(Node x) {
    if (x == null)
      return 0;
    else
      return x.n;
  }

  /**
   * 如果樹是空的，則查找未命中 如果被查找的鍵小于根節(jié)點(diǎn)，則在左子樹中繼續(xù)查找 如果被查找的鍵大于根節(jié)點(diǎn)，則在右子樹中繼續(xù)查找
   * 如果被查找的鍵和根節(jié)點(diǎn)的鍵相等，查找命中
   * 
   * @param key
   * @return
   */
  public Value get(Key key) {
    return get(root, key);
  }

  private Value get(Node x, Key key) {
    if (x == null)
      return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
      return get(x.left, key);
    else if (cmp > 0)
      return get(x.right, key);
    else
      return x.value;
  }

  /**
   * 二叉查找樹的一個很重要的特性就是插入的實(shí)現(xiàn)難度和查找差不多。 當(dāng)查找到一個不存在與樹中的節(jié)點(diǎn)（null）時，new 新節(jié)點(diǎn)，并將上一路徑指向該節(jié)點(diǎn)
   * 
   * @param key
   * @param val
   */
  public void put(Key key, Value val) {
    root = put(root, key, val);
  }

  private Node put(Node x, Key key, Value val) {
    if (x == null)
      return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
      x.left = put(x.left, key, val);
    else if (cmp > 0)
      x.right = put(x.right, key, val);
    else
      x.value = val;
    x.n = size(x.left) + size(x.right); // 要及時更新節(jié)點(diǎn)的子樹數(shù)量
    return x;
  }

  public Key min() {
    return min(root).key;
  }

  private Node min(Node x) {
    if (x.left == null)
      return x;
    return min(x.left);
  }

  public Key max() {
    return max(root).key;
  }

  private Node max(Node x) {
    if (x.right == null)
      return x;
    return min(x.right);
  }

  /**
   * 向下取整：找出小于等于該鍵的最大鍵
   * 
   * @param key
   * @return
   */
  public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null)
      return null;
    else
      return x.key;
  }

  /**
   * 如果給定的鍵key小于二叉查找樹的根節(jié)點(diǎn)的鍵，那么小于等于key的最大鍵一定出現(xiàn)在根節(jié)點(diǎn)的左子樹中
   * 如果給定的鍵key大于二叉查找樹的根節(jié)點(diǎn)，那么只有當(dāng)根節(jié)點(diǎn)右子樹中存在大于等于key的節(jié)點(diǎn)時，
   * 小于等于key的最大鍵才會出現(xiàn)在右子樹中，否則根節(jié)點(diǎn)就是小于等于key的最大鍵
   * 
   * @param x
   * @param key
   * @return
   */
  private Node floor(Node x, Key key) {
    if (x == null)
      return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
      return x;
    else if (cmp < 0)
      return floor(x.left, key);
    else {
      Node t = floor(x.right, key);
      if (t == null)
        return x;
      else
        return t;
    }
  }

  /**
   * 向上取整：找出大于等于該鍵的最小鍵
   * 
   * @param key
   * @return
   */
  public Key ceiling(Key key) {
    Node x = ceiling(root, key);
    if (x == null)
      return null;
    else
      return x.key;
  }

  /**
   * 如果給定的鍵key大于二叉查找樹的根節(jié)點(diǎn)的鍵，那么大于等于key的最小鍵一定出現(xiàn)在根節(jié)點(diǎn)的右子樹中
   * 如果給定的鍵key小于二叉查找樹的根節(jié)點(diǎn)，那么只有當(dāng)根節(jié)點(diǎn)左子樹中存在大于等于key的節(jié)點(diǎn)時，
   * 大于等于key的最小鍵才會出現(xiàn)在左子樹中，否則根節(jié)點(diǎn)就是大于等于key的最小鍵
   * 
   * @param x
   * @param key
   * @return
   */
  private Node ceiling(Node x, Key key) {
    if (x == null)
      return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
      return x;
    else if (cmp > 0) {
      return ceiling(x.right, key);
    } else {
      Node t = floor(x.left, key);
      if (t == null)
        return x;
      else
        return t;
    }
  }

  /**
   * 選擇排名為k的節(jié)點(diǎn)
   * 
   * @param k
   * @return
   */
  public Key select(int k) {
    return select(root, k).key;
  }

  private Node select(Node x, int k) {
    if (x == null)
      return null;
    int t = size(x.left);
    if (t > k)
      return select(x.left, k);
    else if (t < k)
      return select(x.right, k - t - 1);// 根節(jié)點(diǎn)也要排除掉
    else
      return x;
  }

  /**
   * 查找給定鍵值的排名
   * 
   * @param key
   * @return
   */
  public int rank(Key key) {
    return rank(key, root);
  }

  private int rank(Key key, Node x) {
    if (x == null)
      return 0;
    int cmp = key.compareTo(x.key);
    if (cmp < 0)
      return rank(key, x.left);
    else if (cmp > 0)
      return 1 + size(x.left) + rank(key, x.right);
    else
      return size(x.left);
  }
  /**
   * 刪除最小鍵值對
   */
  public void deleteMin(){
    root = deleteMin(root);
  }
  /**
   * 不斷深入根節(jié)點(diǎn)的左子樹直到遇見一個空鏈接，然后將指向該節(jié)點(diǎn)的鏈接指向該結(jié)點(diǎn)的右子樹
   * 此時已經(jīng)沒有任何鏈接指向要被刪除的結(jié)點(diǎn)，因此它會被垃圾收集器清理掉
   * @param x
   * @return
   */
  private Node deleteMin(Node x){
    if(x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.n = size(x.left)+size(x.right) + 1;
    return x;
  }
  
  public void deleteMax(){
    root = deleteMax(root);
  }
  private Node deleteMax(Node x){
    if(x.right == null ) return x.left;
    x.right = deleteMax(x.right);
    x.n = size(x.left)+size(x.right) + 1;
    return x;
  }
  
  public void delete(Key key){
    root = delete(root,key);
  }
  private Node delete(Node x, Key key){
    if(x == null) return null;
    int cmp = key.compareTo(x.key);
    if(cmp < 0) x.left = delete(x.left,key);
    else if(cmp > 0) x.right = delete(x.right,key);
    else{
      if(x.right == null) return x.left;
      if(x.left == null ) return x.right;
      /**
       * 如果被刪除節(jié)點(diǎn)有兩個子樹，將被刪除節(jié)點(diǎn)暫記為t
       * 從t的右子樹中選取最小的節(jié)點(diǎn)x，將這個節(jié)點(diǎn)x的左子樹設(shè)為t的左子樹
       * 這個節(jié)點(diǎn)x的右子樹設(shè)為t的右子樹中刪除了最小節(jié)點(diǎn)的子樹，這樣就成功替換了t的位置
       */
      Node t = x;
      x = min(t.right);
      x.left = t.left;
      x.right = deleteMin(t.right);
    }
    x.n = size(x.left) + size(x.right) +1;
    return x;
  }
  
  public void print(){
    print(root);
  }
  private void print(Node x){
    if(x == null ) return;
    print(x.left);
    StdOut.println(x.key);
    print(x.right);
  }
  
  public Iterable<Key> keys(){
    return keys(min(),max());
  }
  public Iterable<Key> keys(Key lo, Key hi){
    Queue<Key> queue = new Queue<Key>();
    keys(root, queue, lo, hi);
    return queue;
  }
  private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
    if(x == null) return;
    int cmplo = lo.compareTo(x.key);
    int cmphi = lo.compareTo(x.key);
    if(cmplo < 0 ) keys(x.left,queue,lo,hi);
    if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key);
    if(cmphi > 0 ) keys(x.right,queue,lo,hi);
  }
}