二叉搜索树

定义：

     二叉搜索树是一棵二叉树来组织的。二叉搜索中的关键字总是以满足二叉树搜索性质的方式来存储的。

    设x 是二叉树中的一个节点。如果y是x 左子树中的一个结点，那么 y.key <= x.key。

                              如果y是x 右子树中的一个结点，那么 y.key >= x.key。

算法的分析：

    假如我们选择中序遍历整个二叉树。 例如

       

---

                                   6

                           5                7

                      2         5                 8

---

   这样一个二叉树，（中间的线自己想象）。

   INORDER-TREE—WALK

   1  if x != NULL

   2     INORDER-TREE-WALK(x, left)

   3     print x.key;

   4     INORDER-TREE-WALK(x, right)

 很简单我们可以得到树的中序遍历结果： 2 5 5 6 7 8

---

遍历一棵具有N个结点的二叉搜索树需要消耗的时间是：Θ（n)

证明：

   用 T(n)表示需要的时间，由于 中序需要访问这棵树的全部n各节点，所以有T(n)=Ω(n）,下面只要证明T(n) = O(n).

   对于一棵空树， 需要消耗很小的常数时间c,对于某个常数，c>0;有T(0) = c;

   n > 0 , 假如x 的左子树上 有 k个结点，那么右子树上有 n - k -1;

   对于T(n) 有 T(n) <= T(k) + T(n-k-1) +d;  d >0;

   使用替换法： T(n) <= (c+d)n +c; 可以得出T(n) = O(n);