前言
这个系列是毕业找工作的复习笔记，希望可以和广大正准备毕业的童鞋一起打牢基础，迎接各种笔试……为了应付中英文笔试，关键词都用英文进行标注，这样就不怕面对英文题目了。之所以开始这一系列是因为之前在参加微软笔试的时候，被一道stable sorting的选择题给卡住了，才发现自己的基本功什么时候变得这么差了。既然要找工作就要好好复习，从最基础的开始。算法的部分来自《The Algorithm Design Manual》的笔记。
结构特点
二叉搜索树的特点是，小的值在左边，大的值在右边，即
比如：
这样的结构有一个好处是很容易获得最大值（Maximum）、最小值（minimum）、某元素的前驱（Precursor）、某元素的后继（Successor）。
最大值：树的最右节点。
最小值：树的最左节点。
某元素前驱：左子树的最右。
某元素的后继：右子树的最左。
基本操作
二叉搜索树的基本操作包括searching、traversal、insertion以及deletion。
(代码为了省地方没有按照规范来写，真正写代码的时候请一定遵照规范)
① searching
tree * search_tree(tree *l, item_type x){ if(l == null) return NULL; if(l->item == x) return l; if(x < l->item){ return (search_tree(l->left, x)); } if(x > l->item){ return (search_tree(l->right, x)); } }
时间复杂度为O(h)，h为树的高度。
② traversal
由于小的节点在左边，大的节点在右边，因此使用中序(in-order)遍历可以方便的得到一个sorted list。
void traverse_tree(tree *l){ if(l != NULL){ traverse_tree(l->left); process_item(l->item); traverse_tree(l->right); } }
时间复杂度为O(n)，n为树的总结点数。
③ insertion
insert_tree(tree **l, item_type x, tree *parent){ tree *p; /*temporary pointer*/ if(*l == NULL){ p = malloc(sizeof(tree)); p->item = x; p->left = p->right = NULL; p->parent = parent; *l = p; return; } if(x < (*l)->item){ insert_tree(&((*l)->left), x, *l); }else{ insert_tree(&((*l)->right), x, *l); } }
时间复杂度为O(h)，h为树的高度。
④deletion
在删除节点时有三种情况：
1）要删除的节点为叶节点
那么直接删除即可。
2）要删除的节点有一个子节点
那么删除掉该节点，并用其唯一的子节点代替自己的位置即可。
3）要删除的节点有两个子节点
那么首先要找到该节点的右子树的最小值节点k，然后将该k替换掉待删除节点。
最坏情况下，时间复杂度为O(h)+指针的移动开销。
进阶
由上可知，二叉搜索树的dictionary operation（包括search、insertion、deletion）的时间复杂度均与O(h)相关，h为树的高度（log n），如果按照上述的insertion方法构建树，那么构建出来的树的形状各异，特别是当输入序列有序时，更会退化到链表的程度。所以，如果能用某种方法，将树的高度降低到最小，那么其dictionary operation的时间开销均可以降低，不过相对而言构建树的开销将增大。为了降低二叉搜索树的高度而提出了平衡二叉树（Balanced Binary Tree）的概念。它要求左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这样就可以将搜索树的高度尽量减小。常用算法有红黑树、AVL、Treap、伸展树等。