摘要：在二叉查找樹上執(zhí)行基本操作的時間與樹的高度成正比。不同的二叉查找樹可以表示同一組值。紅黑樹樹二叉查找樹，紅黑樹，樹紅黑樹

雖是讀書筆記，但是如轉(zhuǎn)載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復(fù)制黨

關(guān)于二叉樹的基本知識，可以參見：Java 實現(xiàn)基本數(shù)據(jù)結(jié)構(gòu) 2(樹)

以下是算法導(dǎo)論第十二章的學(xué)習(xí)筆記

查找樹是一種數(shù)據(jù)結(jié)構(gòu)，支持動態(tài)集合操作。在二叉查找樹上執(zhí)行基本操作的時間與樹的高度成正比。對已n個節(jié)點的完全二叉樹，各種操作的最壞情況運行時間O(logn). 但是如果二叉查找樹退化成含n個節(jié)點的線性鏈，各種操作的最壞情況運行時間O(n)。 一顆隨機構(gòu)造的二叉查找樹的操作平均時間是O(logn).

對于任何節(jié)點x，其左子樹的關(guān)鍵字最大不超過key[x],其右子樹的關(guān)鍵字最小不小于key[x]. 因此可以使用中序遍歷算法，輸出有序的樹的所有關(guān)鍵字。

不同的二叉查找樹可以表示同一組值。

查找二叉查找樹的時間可以在O(h) = O(logn)的時間內(nèi)完成。

關(guān)于二叉樹的一些數(shù)學(xué)性質(zhì)：
1. 在二叉樹的第i層上至多有2^(i-1)個節(jié)點(i>=1)
2. 深度為k的二叉樹至多有2^k-1個節(jié)點
3. 對于任何一棵二叉樹T，如果其葉子節(jié)點數(shù)為n₀，度為2的節(jié)點數(shù)為n₂,則n₀=n₂+1.

        // 返回指向包含關(guān)鍵字k的節(jié)點的指針
    public TreeNode search(TreeNode root, int k){
        if(root==null){
            return null;
        }
        if(root.val == k)
            return root;
        if(root.val > k){
            return search(root.left,k);
        }
        else
            return search(root.right,k);
    }

    //非遞歸 - 返回指向包含關(guān)鍵字k的節(jié)點的指針
    public TreeNode searchIterative(TreeNode root, int k){
        while(root!=null){
            if(root==null || root.val == k){
                return root;
                }
            if(root.val>k)
            {
                root = root.left;
            }
            else
                root = root.right;
            }
        return root;
    }
    // 返回最小值節(jié)點
    public TreeNode minimal(TreeNode root){
        if(root ==null){
            return null;
        }
        while(root.left!=null){
            root = root.left;
        }
        return root;
    }
    // 返回最大值節(jié)點
    public TreeNode maximal(TreeNode root){
        if(root ==null){
            return null;
        }
        while(root.right!=null){
            root = root.right;
        }
        return root;
    }

所謂前驅(qū)和后繼是指，指定元素在所有元素順序排列模式下的前一個元素或后一個元素。

要獲取一個二叉搜索樹中指定結(jié)點的后繼的直觀的辦法是，找到所有比指定結(jié)點大的結(jié)點中最小的。根據(jù)二叉搜索樹的屬性，找比某結(jié)點大的元素，可以往兩個兩個方向走：

往右子樹方向走，結(jié)點右子樹的元素都不小于本身；
往父結(jié)點方向走，指定的結(jié)點有可能處于其它結(jié)點的左子樹中。
當(dāng)指定結(jié)點擁有右子樹時，那么其后繼必存在于其右子樹中。因往父結(jié)點方向找到的比指定結(jié)點大的元素大于指定結(jié)點右子樹的所有元素。如果指定結(jié)點沒有右孩子呢？那么沿著父結(jié)點的方向找到第一個節(jié)點的左子樹包含指定結(jié)點的結(jié)點，這個結(jié)點就是指定結(jié)點的后繼。

// 尋找前驅(qū)后繼
    public TreeNode successor(TreeNode root){
        if(root ==null || root.right == null){
            return null;
        }
        // 如果該節(jié)點有右孩子，則輸出右孩子的最左 -- minimal
        if(root.right != null){
            return minimal(root.right);
        }
        else{
            TreeNode y = root.parent;
            while(y!=null && root == y.right){
                root = y;
                y = y.parent;
            }
            return y;
        }
    }

插入：從根結(jié)點開始，沿樹下降。指針 x 跟蹤這條路徑，而 y 始終指向 x 的父結(jié)點。根據(jù) key[z] 與 key[x] 的比較結(jié)果，決定向左向右轉(zhuǎn)。直到 x 成為 NIL 為止。這個 NIL 所占位置及我們想插入 z 的地方，y 即為 z 的父結(jié)點。

        // 插入
    public TreeNode insert (TreeNode root, TreeNode x){
        TreeNode p = root;
        TreeNode y = new TreeNode();
        if(p==null){
            root = x;
            return root;
        }
        while(p!=null)      
        {    
            if(p.val >= x.val){
                y = p;
                p = p.left;
            }
            else{
                y = p;
                p =p.right;
            }
        }
        // 樹本來沒有節(jié)點的時候
        x.parent = y;
        if(x.val <= y.val){
            y.left = x;
        }
        else{
            y.right = x;
        }
        return root;
    }

一個規(guī)律：如果BST的某個節(jié)點有兩個子女，則其后繼沒有左子女，其前驅(qū)沒有右子女。

以指向 z 的指針為參數(shù)，考慮三種情況。
youtu20分鐘短視頻講解
1. 若 z 沒有子女，則修改其父結(jié)點 p[z]，是 NIL 為其子女；
2. 如果結(jié)點 z 只有一個子女，則可以通過在其子結(jié)點與父結(jié)點之間建立一條鏈來刪除 z;
3. 如果結(jié)點 z 有兩個子女，先刪除 z 的后繼 y（它沒有左子女），再用 y 的內(nèi)容來替代 z 的內(nèi)容。

以下是刪除操作的偽碼：
注意：偽碼中的 TRANSPLANT，只修改 v 與 u 的父親之間的關(guān)系，而不修改與 u 孩子的關(guān)系。

TREE-DELETE(T,z)
    if z.left == NIL            
       TRANSPLANT(T,z,z.right)
    else if z.right == NIL       
       TRANSPLANT(T,z,z.left)
    else y = TREE-MINIMUM(z.right)
       if y.p ≠ z              
          TRANSPLANT(T,y,y.right)  
          y.right = z.right
          y.right.p = y
       TRANSPLANT(T,z,y)          
       y.left = z.left       
       y.left.p = y
TRANSPLANT(T,u,v)
  if u.p == NIL       
       T.root = v
  else if u == u.p.left   
       u.p.left = v
  else u.p.right = v      
  if v ≠ NIL
       v.p = u.p

對于高度為h的二叉查找樹，動態(tài)集合操作 INSERT 和DELETE 的運行時間為 O(h)。

stackoverflow的解答
在搜索應(yīng)用中使用，尤其是數(shù)據(jù)頻繁插入和刪除等等更改操作。比如set和map。

雖然BST的操作用數(shù)組完全可以實現(xiàn)，但是數(shù)組只適合那種write once, read many times的操作。
然而當(dāng)要進(jìn)行操作諸如 插入,刪除，交換的時候，BST的性能遠(yuǎn)遠(yuǎn)超過了數(shù)組。BST 是 node based 數(shù)據(jù)結(jié)構(gòu)，
而數(shù)組是 contiguous chunk of memory, 即基于連續(xù)內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，插入,刪除，交換要BST更好。

舉個例子
BST和哈希表有何區(qū)別？ 存儲手機上的通訊錄用哪個數(shù)據(jù)結(jié)構(gòu)好？
哈希表可以O(1)時間進(jìn)行搜索和插入。
BST 可以O(nlogn)時間進(jìn)行搜索和插入。 在這一點BST稍慢。
但是二者最大的區(qū)別是哈希表是一個無序的DS，while, BSTs 是有序的DS。
當(dāng)設(shè)計手機通訊錄這種對內(nèi)存要求很高的應(yīng)用時候，需要考慮存儲空間而且手機通訊錄需要元素有序。哈希表無序，需要額外的空間和時間去排序，而BST就不需要額外的空間去
排序，而且在n<5000條記錄的時候，BST的O(nlogn)足夠快。

所以應(yīng)該采用BST。