二元搜尋樹(Binary Search Tree)是二元樹(Binary Tree)的一種，但其另外遵循以下幾個規則:
1. Left child 的值會少於等於其父節點的值
2. Right child 的值會大於等於其父節點的值
3. 任意節點的左右子樹也符合上述定義

由於有這些特別的特性，BST在插入與刪除節點方面較一般的BT快 (時間複雜度: O(logn) versus O(n))。我們直接來看程式碼:

from collections import deque

class TreeNode:
    def __init__(self, data=None):
        self.data = data
        self.leftchild = None
        self.rightchild = None
        
# 時間複雜度: O(logN)，空間複雜度: O(logN)        
def insertNode(root, value):
    new_node = TreeNode(value)
    # 如果rootNode還沒有東西，那他就是rootnode惹
    if root.data == None:
        root.data = value
        return 'The value is inserted'
    # 欲插入值小於節點值，根據BST的定義，往左邊看
    elif value <= root.data:
        if root.leftchild is None:
            root.leftchild = new_node
            return 'The value is inserted'
        else:
            return insertNode(root.leftchild, value)
    # 欲插入值大於節點值，根據BST的定義，往右邊看
    else:
        if root.rightchild is None:
            root.rightchild = new_node
            return 'The value is inserted'
        else:
            return insertNode(root.rightchild, value)
            
# traversal的方法也跟binary tree，這裡我們就不再贅述，單純用leverordertraversal來看樹現在長怎樣
def levelordertraversal(root):
    customqueue = deque()
    customqueue.append(root)
    while len(customqueue) != 0:
        pop_node = customqueue.popleft()
        print(pop_node.data)
        if pop_node.leftchild is not None:
            customqueue.append(pop_node.leftchild)
        if pop_node.rightchild is not None:
            customqueue.append(pop_node.rightchild)
BST = TreeNode()
insertNode(BST, 40)
insertNode(BST, 50)
insertNode(BST, 30)
insertNode(BST, 90)
insertNode(BST, 10)
levelordertraversal(BST)
>>  40
    30
    50
    10
    90

# 搜尋值，時間複雜度: O(logN)，空間複雜度: O(logN)  
def searchNode(root, value):
    if not root:
        return 'Not Found!'
    if root.data == value:
        return 'Found!'
    elif value < root.data:
        return searchNode(root.leftchild, value)
    elif value > root.data:
        return searchNode(root.rightchild, value)

print(searchNode(BST, 40))
>> Found!
print(searchNode(BST, 60))
>> Not Found!

# 由於在刪除節點的case裡，在遇到有兩個子樹的時候，需要在right subtree裡找一個local minimum的node而定義的函式
def findlocalmin(node):
    current = node
    while current.leftchild is not None:
        current = current.leftchild
    return current
   

# 時間複雜度:O(logN), 空間複雜度: O(logN)
def deleteNode(node, target):
    if not node:
        return node
    elif target < node.data:
        node.leftchild = deleteNode(node.leftchild, target)
    elif target > node.data:
        node.rightchild = deleteNode(node.rightchild, target)
    else:
        # 只有single child或是 no children的case，將下面那個節點上移
        if node.leftchild is None:
            temp = node.rightchild
            node = temp
            return temp
        elif node.rightchild is None:
            temp = node.leftchild
            node = temp
            return temp
        # 在兩個children都在的情況下，在右邊子樹找local minimum的值代替
        else:
            temp = findlocalmin(node.rightchild)
            node.data = temp.data
            node.rightchild = deleteNode(node.rightchild, temp.data)
            return temp
            
print('=== delete Node ===')
deleteNode(BST,40)
levelordertraversal(BST)
>>  50
    30
    90
    10

參考資料:
本文主要為udemy課程: The Complete Data Structures and Algorithms Course in Python的學習筆記，有興趣的人可以自己上去看看。