二叉搜尋樹
（
B
inary
S
earch
T
ree，
BST
）是一種常用的資料結構，在理想情況下，它可以以
的複雜度完成一系列修改和查詢，包括：
插入
一個數
刪除
一個數
查詢某數的
排名
（排名定義為比該數小的數的個數+1）
查詢指定
排名
的數
求某數的
前驅
（前驅定義為小於該數，且最大的數）
求某數的
後繼
（後繼定義為大於該數，且最小的數）
維護一個有序的
陣列
，配合二分查詢，也可以實現這些操作，但插入和刪除的複雜度是
。相對地，
連結串列
可以
插入和刪除，但其他操作的複雜度不夠優秀。
二叉搜尋樹
即BST對於以上每個操作，都擁有不差的複雜度。
例如，如果我們依次插入6、2、5、1、7、4、2、5、9、5，得到BST的結構如下：
顯然，二叉搜尋樹是一個
二叉樹
，每個節點對應的左子樹中的所有數都
小於
它，右子樹中的所有數都
大於
它。而且每個節點對應的左右子樹也是二叉搜尋樹（這是一個天然
遞迴
的結構）。由於我們這裡維護的是可重集，所以每個節點還帶有額外資訊，即該節點儲存的數出現的
次數
。此外，為了方便查詢排名，我們還儲存每個子樹的
大小
。
// L： 左子樹根節點編號，R：右子樹根節點編號，N：該節點儲存的數出現的次數
// val：該節點儲存的數，size：以該節點為根節點的子樹的節點數目（即子樹大小）
int
L
［
MAXN
］，
R
［
MAXN
］，
N
［
MAXN
］，
val
［
MAXN
］，
size
［
MAXN
］，
cnt
=
1
；
現在我們分別實現上述的操作。
插入
從根節點開始，遞迴地搜尋。若插入的值小於當前節點的值，則向左搜；反之向右搜。這樣最後如果找到一個已有節點，則令其計數+1；否則若到達空節點，則用該節點儲存這個值。
void
insert
（
int
v
，
int
pos
=
1
）
// 插入
{
size
［
pos
］
++
；
// 樹大小+1
if
（
N
［
pos
］
==
0
&&
L
［
pos
］
==
0
&&
R
［
pos
］
==
0
）
// 空節點
{
val
［
pos
］
=
v
；
N
［
pos
］
=
1
；
}
else
if
（
v
<
val
［
pos
］）
// 向左搜尋
{
if
（
L
［
pos
］
==
0
）
// 如果應該向左搜，但不存在左節點，則建立一個新節點
L
［
pos
］
=
++
cnt
；
insert
（
v
，
L
［
pos
］）；
}
else
if
（
v
>
val
［
pos
］）
// 向右搜尋
{
if
（
R
［
pos
］
==
0
）
R
［
pos
］
=
++
cnt
；
insert
（
v
，
R
［
pos
］）；
}
else
// 已經存在值相同的節點
N
［
pos
］
++
；
}
刪除
這裡直接採取惰性刪除的方法：找到要刪除的數，令其計數-1。這樣寫起來比較簡單，不用進行較複雜的分類討論，而且不會增加時間複雜度。
稍微注意一下，採取惰性刪除時判斷一個節點是不是空節點要用
N［pos］==0 && L［pos］==0 && R［pos］==0
而不能僅僅判斷
N
，因為
N［pos］==0
的點也可能是被刪除的中間節點。（注意被刪除的葉子節點可以當作空節點處理）
void
remove
（
int
v
，
int
pos
=
1
）
// 刪除
{
size
［
pos
］
——
；
// 樹大小-1
if
（
v
<
val
［
pos
］）
remove
（
v
，
L
［
pos
］）；
else
if
（
v
>
val
［
pos
］）
remove
（
v
，
R
［
pos
］）；
else
N
［
pos
］
——
；
}
求排名
因為排名被定義為比某數小的數+1，所以我們直接實現兩個函式
countl
和
countg
，用來求比某數小的數的數量和比某數大的數的數量。（這兩個函式後面也會用到）
以
countl
為例，我們遞迴地求。如果要找的值比當前節點小，則向左邊搜；反之則向右邊搜，但這時要加上
size［L［pos］］+N［pos］
，因為左子樹和根節點的所有數都比要找的數小；如果要找的值恰好等於當前節點，則直接返回左子樹的大小。
int
countl
（
int
v
，
int
pos
=
1
）
// 求比某數小的數的個數
{
if
（
v
<
val
［
pos
］）
return
L
［
pos
］
？
countl
（
v
，
L
［
pos
］）
：
0
；
else
if
（
v
>
val
［
pos
］）
return
size
［
L
［
pos
］］
+
N
［
pos
］
+
（
R
［
pos
］
？
countl
（
v
，
R
［
pos
］）
：
0
）；
else
return
size
［
L
［
pos
］］；
}
而
countg
完全類似。
int
countg
（
int
v
，
int
pos
=
1
）
// 求比某數大的數的個數
{
if
（
v
>
val
［
pos
］）
return
R
［
pos
］
？
countg
（
v
，
R
［
pos
］）
：
0
；
else
if
（
v
<
val
［
pos
］）
return
size
［
R
［
pos
］］
+
N
［
pos
］
+
（
L
［
pos
］
？
countg
（
v
，
L
［
pos
］）
：
0
）；
else
return
size
［
R
［
pos
］］；
}
rank
函式其實可以不寫了：
int
rank
（
int
v
）
{
return
countl
（
v
）
+
1
；
}
求指定排名的數
與上面的方法類似，每個節點處判斷應該往左邊還是右邊找，遞迴地往下搜尋。
int
kth
（
int
k
，
int
pos
=
1
）
// 求指定排名的數
{
if
（
size
［
L
［
pos
］］
+
1
>
k
）
// 答案在左，在左子樹中找排名為k的數
return
kth
（
k
，
L
［
pos
］）；
else
if
（
size
［
L
［
pos
］］
+
N
［
pos
］
<
k
）
// 答案在右，在右子樹中找排名為k - size［L［pos］］ - N［pos］的數
return
kth
（
k
-
size
［
L
［
pos
］］
-
N
［
pos
］，
R
［
pos
］）；
else
return
val
［
pos
］；
}
注意，假如某個數的排名為2，且它出現了3次，那麼這個函式傳入2、3、4都會返回這個數，這也提供了一些方便。
求前驅
根據我們
kth
函式的性質，直接找到排名比當前數小1的那個數即可。
int
pre
（
int
v
）
// 求前驅
{
int
r
=
countl
（
v
）；
return
kth
（
r
）；
}
求後繼
後繼的排名則是小於等於當前數的數的數量+1。
int
suc
（
int
v
）
// 求後繼
{
int
r
=
size
［
1
］
-
countg
（
v
）
+
1
；
return
kth
（
r
）；
}
以上是二叉搜尋樹的介紹。然而，這種資料結構本身很少使用，因為它的各種操作複雜度是
，其中
為層數。只有在它大致平衡（平衡指所有葉子的深度趨於相同），才具有優秀的複雜度（當它是完全二叉樹時，為
），然而這只是理想情況。假如我們依次加入6、5、4、3、2、1，BST的結構會是這樣：
這樣，BST就退化成了連結串列，複雜度變為
。
為了使BST能夠大致平衡，人們想了很多種改進方法，它們稱為
平衡樹
。今後的筆記會介紹一些常用的平衡樹。
