BST

算法导论这本书真的确实很有帮助，你照着书上的代码打一遍就有助于你理解这种data structure是如何实现的。而且其实能更好的帮助你理解recursion的原理，因为书中很多data structure都是用recursion来实现的。而且你照着代码打一下的时候，可以先尝试自己打一遍，如果遇到问题在看书上是如何解决的。这样能让你更好的理解，或者说更好的发现自己思维中的漏洞。填补逻辑上的漏洞。

今天在实现BST的时候发现其实很多API method本身就是leetcode上面的题……这么一想leetcode就是在帮助你掌握实现BST的逻辑。更好的运用它。比如BST的floor() method 是为了找到一个小于等于(<=)当前key

  public Key floor(Key key) {
      Node x = floor(root, key);
      if (x == null) return null;
      return x.key;
  }
  private Node floor(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    // if the key is less than current node key, move to left subtree
    if (cmp < 0) return floor(x.left, key);
    // 这里是之前从来没见过的，脑子里没有说可以直接在加一个variable然后用它来存储搜索右子树最小key的结果
    //因为如果当前key > 当前node.key的时候，你不能直接返回，而需要找到右子树最小key才可以（floor的定义）
    Node t = floor(x.right, key);
    if (t != null) return t;
    return x;
  }

recursion本身思路还是清晰的，一开始可能有点麻烦，但是过一段时间之后就发现recursion实际上确实是更加方便。
BST删除节点确实挺难的，最重要的还是脑子里要形成图像。它本身核心思想还是通过一个临时指针指向要被删除的节点，然后把现在的指针指向右子树最小的节点，这时候把现在指针x的右指针（指向右子树）指向临时指针的右指针中最小的节点（通过deleteMin(t.right) 来实现，t.right 就是临时指针的右子树。再把x的左指针指向t.left 就是完成了删除操作。我觉得书中这张图还是很有用的

image.png