二叉搜尋樹

                             二叉搜尋樹

定義：

     二叉搜尋樹是一棵二叉樹來組織的。二叉搜尋中的關鍵字總是以滿足二叉樹搜尋性質的方式來存儲的。

    設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);