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

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

關于二叉樹的基本知識，可以參見：Java 實現基本數據結構 2(樹)

以下是算法導論第十二章的學習筆記

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

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

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

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

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

        // 返回指向包含關鍵字k的節點的指針
    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);
    }

    //非遞歸 - 返回指向包含關鍵字k的節點的指針
    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;
    }
    // 返回最小值節點
    public TreeNode minimal(TreeNode root){
        if(root ==null){
            return null;
        }
        while(root.left!=null){
            root = root.left;
        }
        return root;
    }
    // 返回最大值節點
    public TreeNode maximal(TreeNode root){
        if(root ==null){
            return null;
        }
        while(root.right!=null){
            root = root.right;
        }
        return root;
    }

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

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

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

// 尋找前驅后繼
    public TreeNode successor(TreeNode root){
        if(root ==null || root.right == null){
            return null;
        }
        // 如果該節點有右孩子，則輸出右孩子的最左 -- 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;
        }
    }

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

        // 插入
    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;
            }
        }
        // 樹本來沒有節點的時候
        x.parent = y;
        if(x.val <= y.val){
            y.left = x;
        }
        else{
            y.right = x;
        }
        return root;
    }

一個規律：如果BST的某個節點有兩個子女，則其后繼沒有左子女，其前驅沒有右子女。

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

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

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的二叉查找樹，動態集合操作 INSERT 和DELETE 的運行時間為 O(h)。

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

雖然BST的操作用數組完全可以實現，但是數組只適合那種write once, read many times的操作。
然而當要進行操作諸如 插入,刪除，交換的時候，BST的性能遠遠超過了數組。BST 是 node based 數據結構，
而數組是 contiguous chunk of memory, 即基于連續內存的數據結構，插入,刪除，交換要BST更好。

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

所以應該采用BST。