二叉查找樹具有很高的靈活性，對其優化可以生成平衡二叉樹，紅黑樹等高效的查找和插入資料結構，後文會一一介紹。
二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
3. 任意節點的左、右子樹也分别為二叉查找樹。
4. 沒有鍵值相等的節點（no duplicate nodes）。
如下圖，這個是普通的二叉樹：
在此基礎上，加上節點之間的大小關系，就是二叉查找樹：
在實作中，我們需要定義一個内部類Node，它包含兩個分别指向左右節點的Node，一個用于排序的Key，以及該節點包含的值Value，還有一個記錄該節點及所有子節點個數的值Number。
查找操作和二分查找類似，将key和節點的key比較，如果小于，那麼就在Left Node節點查找,如果大于，則在Right Node節點查找，如果相等，直接傳回Value。
該方法實作有疊代和遞歸兩種。
遞歸的方式實作如下：
疊代的如下：
插入和查找類似，首先查找有沒有和key相同的，如果有，更新；如果沒有找到，那麼建立新的節點。并更新每個節點的Number值，代碼實作如下：
插入操作圖示如下：
下面是插入動畫效果：
随機插入形成樹的動畫如下，可以看到，插入的時候樹還是能夠保持近似平衡狀态：
如下圖可以看出，二叉查找樹的最大最小值是有規律的：
從圖中可以看出，二叉查找樹中，最左和最右節點即為最小值和最大值，是以我們隻需疊代調用即可。
以下是遞歸的版本：
查找Floor(key)的值就是所有<=key的最大值，相反查找Ceiling的值就是所有>=key的最小值，下圖是Floor函數的查找示意圖：
以查找Floor為例，我們首先将key和root元素比較，如果key比root的key小，則floor值一定在左子樹上；如果比root的key大，則有可能在右子樹上，當且僅當其右子樹有一個節點的key值要小于等于該key；如果和root的key相等，則floor值就是key。根據以上分析，Floor方法的代碼如下，Ceiling方法的代碼類似，隻需要把符号換一下即可：
删除元素操作在二叉樹的操作中應該是比較複雜的。首先來看下比較簡單的删除最大最小值得方法。
以删除最小值為例，我們首先找到最小值，及最左邊左子樹為空的節點，然後傳回其右子樹作為新的左子樹。操作示意圖如下：
代碼實作如下：
删除最大值也是類似。
現在來分析一般情況，假定我們要删除指定key的某一個節點。這個問題的難點在于：删除最大最小值的操作，删除的節點隻有1個子節點或者沒有子節點，這樣比較簡單。但是如果删除任意節點，就有可能出現删除的節點有0個，1 個，2個子節點的情況，現在來逐一分析。
當删除的節點沒有子節點時，直接将該父節點指向該節點的link設定為null。
當删除的節點隻有1個子節點時，将該自己點替換為要删除的節點即可。
當删除的節點有2個子節點時，問題就變複雜了。
假設我們删除的節點t具有兩個子節點。因為t具有右子節點，是以我們需要找到其右子節點中的最小節點，替換t節點的位置。這裡有四個步驟：
1. 儲存帶删除的節點到臨時變量t
2. 将t的右節點的最小節點min(t.right)儲存到臨時節點x
3. 将x的右節點設定為deleteMin(t.right)，該右節點是删除後，所有比x.key最大的節點。
4. 将x的做節點設定為t的左節點。
整個過程如下圖：
對應代碼如下：
以上二叉查找樹的删除節點的算法不是完美的，因為随着删除的進行，二叉樹會變得不太平衡，下面是動畫示範。
二叉查找樹的運作時間和樹的形狀有關，樹的形狀又和插入元素的順序有關。在最好的情況下，節點完全平衡，從根節點到最底層葉子節點隻有lgN個節點。在最差的情況下，根節點到最底層葉子節點會有N各節點。在一般情況下，樹的形狀和最好的情況接近。
在分析二叉查找樹的時候，我們通常會假設插入的元素順序是随機的。對BST的分析類似與快速排序中的查找：
BST中位于頂部的元素就是快速排序中的第一個劃分的元素，該元素左邊的元素全部小于該元素，右邊的元素均大于該元素。
對于N個不同元素，随機插入的二叉查找樹來說，其平均查找/插入的時間複雜度大約為2lnN，這個和快速排序的分析一樣，具體的證明方法不再贅述，參照快速排序。
它和二分查找一樣，插入和查找的時間複雜度均為lgN，但是在最壞的情況下仍然會有N的時間複雜度。原因在于插入和删除元素的時候，樹沒有保持平衡。我們追求的是在最壞的情況下仍然有較好的時間複雜度，這就是後面要講的平衡查找樹的内容了。下文首先講解平衡查找樹的最簡單的一種：2-3查找樹。
希望本文對您了解二叉查找樹有所幫助。