第二十六课 Binary Search Tree

public Entry find(Object k) {
  BinaryTreeNode node = root;                   // Start at the root.
  while (node != null) {
    int comp = ((Comparable) k).compareTo(node.entry.key());
    if (comp < 0) {                             // Repeatedly compare search
      node = node.left;                         // key k with current node; if
    } else if (comp > 0) {                      // k is smaller, go to the left
      node = node.right;                        // child; if k is larger, go to
    } else {    /* The keys are equal */        // the right child.  Stop when
      return node.entry;                        // we find a match (success;
    }                                           // return the entry) or reach
  }                                             // a null pointer (failure;
  return null;                                  // return null).
}

当你想精确的查找某个 entry，用 hashtable 会更有效率。

This method only finds exact matches. What if we want to find the smallest key greater than or equal to k, or the largest key less than or equal to k? Fortunately, when searching downward through the tree for a key k that is not in the tree, we are certain to encounter both

• the node containing the smallest key greater than k (if any key is greater)
• the node containing the largest key less than k (if any key is less).

See Footnote 1 for an explanation why.

      +--+         For instance, suppose we search for the key 27 in the tree
      |18|         at left.  Along the way, we encounter the keys 25 and 28,
      /--\--+      which are the keys closest to 27 (below and above).
    12   |25|
   / \   +/-\--+   Here's how to implement a method smallestKeyNotSmaller(k):
  4  15  25 |30|   search for the key k in the tree, just like in find().
 /  /  \  +-/+-+   As you go down the tree, keep track of the smallest key
1  13  17 |28|     not smaller than k that you've encountered so far.  If you
 \  \     +-\+     find the key k, you can return it immediately.  If you reach
  3  14      29    a null pointer, return the best key you found on the path.
                   You can implement largestKeyNotLarger(k) symmetrically.

很明显，如果你查找的 key 不在 binary search tree 中，你的搜索会‘路过’比你大的最小 entry 和比你小的最大 entry这时，你只需要在代码中增加两个变量分别记录‘比你小的最大值’和‘比你大的最小值’即可找到他们。or 你可以通过另一个 trick 找到两个值，就是最近的一次'choose left'和'choose right',以上图为例，最近一次‘向左’是28， 最近的一次向右是 25.通过在代码中记录并随时覆盖，就可以找到他们。（个人认为这种方法更好）

min() is very simple. If the tree is empty, return null. Otherwise, start at the root. Repeatedly go to the left child until you reach a node with no left child. That node has the minimum key.

max() is the same, except that you repeatedly go to the right child. In the tree above, observe the locations of the minimum (1) and maximum (30) keys.

insert() starts by following the same path through the tree as find(). (find() works because it follows the same path as insert().) When it reaches a null reference, replace that null with a reference to a new node storing the entry (k, v).

Duplicate keys are allowed. If insert() finds a node that already has the key k, it puts the new entry in the left subtree of the older one. (We could just as easily choose the right subtree; it doesn't matter.)

If the node is a leaf then you just deleted. If the node is an internal node, then you find its successor or predeccessor, you swap and then you delete the successor or predeccessor. And , this successor(suppose it is) cannot have a right child, if it has, then the left child should be the successor. So, what we really do about deleting , we just delete a leaf or a leaf' partent

删除要分三种情况，待删节点没有孩子，只有一个孩子，有两个孩子有两个孩子就删除其 successor, 其 successor 肯定没有左孩子 or 干脆没孩子，因为如果有左孩子说明排序是这样的，待删<'successor_L'<successor<successor_R因为是直接后继（successor）, 所以 successor 肯定没有左孩子

If it has 2 children, i went to the successor of that node, I copied the content of this successor into that node then, I deleted the successor. The actual node I deleted was the successor node and successor node has only one or no children

所以删除带有两个孩子的节点，实际就归结为 ‘有一个孩子的’ or ‘没有孩子的’两个问题。AVL-tree Splay-tree 的所有操作，其实跟这里的 binary search tree 的操作很相似,不同的是都要 avl 和 splay 都要 rotation

remove() is the most difficult operation. First, find a node with key k using the same algorithm as find(). Return null if k is not in the tree; otherwise, let n be the first node with key k.

1. If n has no children, we easily detach it from its parent and throw it away.
2. If n has one child, move n's child up to take n's place. n's parent becomes the parent of n's child, and n's child becomes the child of n's parent.Dispose of n.

3. If n has two children, however, we have to be a bit more clever. Let x be the node in n's right subtree with the smallest key. Remove x; since x has the minimum key in the subtree, x has no left child and is easily removed. Finally, replace n's entry with x's entry. x has the key closest to k that isn't smaller than k, so the binary search tree invariant still holds.

   这里使用了一种‘步进’的方式，把'two child'问题，转换为'one child'问题：如果待删节点有左右两个子树，那么选择右子树中最小的节点（比待删节点大的节点中最小的）与待删节点互换，互换的方法分两步：

   1. 用‘if n has one child’方法删除这个最小的节点，因为这个节点肯定没有左子树；
   2. 用这个节点替换待删节点

       18                          18                            18
      /  \                        /  \                          /  \
    12    25                    12    25                      12    25
   / \    / \                  / \    / \                    / \    / \
  4  15  25  30 -insert(2)->  4  15  25  30 -remove(30)->   4  15  25  28
 /  /  \    /                /  /  \    /                  /  /  \      \
1  13  17  28               1  13  17  28                 1  13  17      29
 \  \       \                \  \       \                  \  \
  3  14      29               3  14      29                 3  14
                             /                             /
                            2                             2

                          18                   18
                      +--/  \                 /  \
                      |12|   25             13    25
                      /-\+   / \           / \    / \
     -remove(12)->   4  15  25  28   ->   4  15  25  28
                    /+-/+ \      \       /  /  \      \
                   1 |13| 17      29    1  14  17      29
                    \+-\+                \
                     3  14                3
                    /                    /
                   2                    2

To ensure you understand the binary search tree operations, especially remove(), I recommend you inspect Goodrich and Tamassia's code on page 446. Be aware that Goodrich and Tamassia use sentinel nodes for the leaves of their binary trees; I think these waste an unjustifiably large amount of space.

[TODO] 这个 remove()一定要注意：
    2
   / --\
  1    7
      / \
     5   8
    /
   4

比如这里要删除 root 2, 但是 2 有左右子树，不能直接删除，要删除 nearest higher:4 先用 4 replace 2, 然后把带有 4 的 node 删除, 问题是，这个 node 是否是字典型 node，包含 value 和 key 的？这里树中的数字明显是 key，那么如果仅仅是“用 key4 去替换 key2”，那么是不是就改变了原来的 key:value 对了？