首先查找与插入都是放在一起说的。而且顺序查找这种低级的事情，是上不了台面的，虽然很多时候，顺序查找也能够解决问题。从编程的原则上讲，如果数据规模不大，用顺序查找（数组或者链表）问题不大，而且也不用那么伤脑筋。

二叉查找树

所有的二叉树，查找算法都是一致的，虽然有先根、中根与后根的区别，但是都简单到不行，区别在于插入时的性能与复杂度，还有更可怕的删除时的性能与复杂度。

基本二叉树

基本二叉树的插入比较简单，如果比当前节点小，就在左子树上插入，否则在右子树上插入。代码将更新父节点简化了，不过不影响逻辑。

/* root is a reference */
void insertNode(root, node) {
  if (root == null) {
    root = node;
  }
  
  if (node == node) return; /* duplicate */
  
  if (node < node) insertNode(node.left, node)
  else insertNode(node.right, node);
}

删除的逻辑就比较复杂一些，如果删除的叶子节点，删了也就删除了。如果删除只有一个子树（左右子树有一个为空），把子树的根节点拿来代替当前节点就可以了。上面两种情况其实都是对应了一种基本概念，我们要删除的是某个子树上的最大值或者最小值：没有左子树的时候，删除的是最小值，没有右子树时删除的最小值。

基于上面的删除最值的操作，删除中间节点的删除逻辑上就非常简单了：我们拿左子树中的最大值或者右子树中的最小值来代替当前节点就可以了。

/* 
  删除一个节点，并且返回被删除的节点，其中x是根节点，返回删除最小节点 
  之后的根节点；
*/
func getMin(Node x) {
    if (x.left != null) return getMin(x.left);
    return x;
}

func deleteMin(Node x) {
  if (x.left != null) {
    x.left = deleteMin(x, x.left);
    return x;
  }
  return x.right;
}

func getMax(Node x) {
   if (x.right != null) return getMax(x.right);
   return x;
}

Node deleteMax(Node x) {
  if (node.right != null) {
    x.right = deleteMax(x.right);
    return x;
  }
  return x.right;
}

func deleteNode(Node parent, Node x) {
    /* 在左子树或者右子树中，找到前续或者后继 */
    Node y = deleteMinOrMax(x);
    y.left = x.left;
    y.right = x.right;
    
   if (parent) {
      if(parent->left == x)  parent->left = y;
      else parent->right = y;
   } else {
      root = y;
  }
};