DSA 二叉搜尋樹

二叉搜尋樹

二叉搜尋樹 (BST) 是一種 二叉樹資料結構，其中對於樹中的任何節點 "X"，以下屬性必須成立：

• X 節點的左子節點及其所有後代（子節點、子節點的子節點，依此類推）的值都小於 X 的值。
• 右子節點及其所有後代的值都大於 X 的值。
• 左子樹和右子樹也必須是二叉搜尋樹。

這些屬性使得搜尋、新增和刪除值的速度比普通二叉樹更快。

為了儘可能輕鬆地理解和實現，我們還假設二叉搜尋樹中的所有值都是唯一的。

使用下面的二叉搜尋樹來更好地理解這些概念和相關術語。

樹的大小是樹中的節點數（\(n\)。

子樹以樹中的一個節點作為區域性根開始，並由該節點及其所有後代組成。

節點的後代是該節點的所有子節點，以及它們的所有子節點，依此類推。只需從一個節點開始，後代就是連線在該節點下方的所有節點。

節點高度是該節點與葉子節點之間的最大邊數。

BST 的中序後繼節點是在進行中序遍歷時出現在其後的節點。上面 BST 的中序遍歷將導致節點 13 出現在節點 14 之前，因此節點 13 的後繼節點是節點 14。

遍歷二叉搜尋樹

為了確認我們確實擁有二叉搜尋樹資料結構，我們可以檢查此頁面頂部的屬性是否為真。因此，對於圖中每個節點，檢查節點左側的所有值是否都更小，而右側的所有值是否都更大。

另一種檢查二叉樹是否為 BST 的方法是進行中序遍歷（就像我們在上一頁上所做的那樣），並檢查由此產生的節點值列表是否按遞增順序排列。

下面的程式碼是上面圖中二叉搜尋樹的實現，包含遍歷功能。

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

root = TreeNode(13)
node7 = TreeNode(7)
node15 = TreeNode(15)
node3 = TreeNode(3)
node8 = TreeNode(8)
node14 = TreeNode(14)
node19 = TreeNode(19)
node18 = TreeNode(18)

root.left = node7
root.right = node15

node7.left = node3
node7.right = node8

node15.left = node14
node15.right = node19

node19.left = node18

# Traverse
inOrderTraversal(root)

正如我們透過執行上面的程式碼示例所看到的，中序遍歷會產生一個按遞增（升序）順序排列的數字列表，這意味著這棵二叉樹是一棵二叉搜尋樹。

在 BST 中搜索值

在 BST 中搜索值與我們在陣列上使用 二分搜尋 查詢值的方式非常相似。

為了使二分搜尋起作用，陣列必須已經排序，然後才能非常快速地搜尋陣列中的值。

同樣，由於節點的放置方式，在 BST 中搜索值也可以非常快速地完成。

使用下面的動畫，瞭解如何在二叉搜尋樹中搜索值。

上面的演算法可以這樣實現：

def search(node, target):
    if node is None:
        return None 
    elif node.data == target:
        return node
    elif target < node.data:
        return search(node.left, target)
    else:
        return search(node.right, target)

在 BST 中搜索值的時複雜度為 \(O(h)\)，其中 \(h\) 是樹的高度。

例如，對於大部分節點都在右側的 BST，樹的高度會比它需要的大，最壞情況下的搜尋會花費更長的時間。這樣的樹稱為不平衡樹。

上面兩個二叉搜尋樹具有相同的節點，並且它們的的中序遍歷結果相同，但高度卻非常不同。搜尋上面的不平衡樹需要更長的時間，因為它更高。

我們將在下一頁介紹一種稱為 AVL 樹的二叉樹。AVL 樹是自平衡的，這意味著樹的高度被保持在最低限度，以便搜尋、插入和刪除等操作所需的時間更少。

在 BST 中插入節點

在 BST 中插入節點與搜尋值類似。

如上所述插入節點意味著插入的節點將始終成為新的葉子節點。

使用下面的模擬來檢視如何插入新節點。

BST 中的所有節點都是唯一的，因此如果我們找到與要插入的值相同的值，我們什麼也不做。

這是 BST 中節點插入的實現方式：

def insert(node, data):
    if node is None:
        return TreeNode(data)
    else:
        if data < node.data:
            node.left = insert(node.left, data)
        elif data > node.data:
            node.right = insert(node.right, data)
    return node

查詢 BST 子樹中的最小值

下一節將解釋如何刪除 BST 中的節點，但要做到這一點，我們需要一個可以找到節點子樹中最小值的函式。

在下圖，如果我們從節點 13 開始一直向左走，我們最終會到達節點 3，這是最小值，對嗎？

如果我們從節點 15 開始一直向左走，我們最終會到達節點 14，這是節點 15 子樹中的最小值。

查詢 BST 節點子樹中最小值的函式看起來像這樣：

def minValueNode(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

我們將在下面的部分中使用這個 minValueNode() 函式來查詢節點的 中序後繼節點，並用它來刪除節點。

刪除 BST 中的節點

要刪除節點，我們的函式必須首先搜尋 BST 來找到它。

找到節點後，有三種不同的情況，刪除節點的方式必須不同。

在上面的第 3 步中，我們找到的後繼節點將始終是葉子節點，並且由於它是我們要刪除的節點之後的節點，我們可以與之交換值並刪除它。

使用下面的動畫，瞭解如何刪除不同的節點。

節點 8 是一個葉子節點（情況 1），所以找到它後，我們就可以直接刪除它。

節點 19 只有一個子節點（情況 2）。要刪除節點 19，父節點 15 直接連線到節點 18，然後可以移除節點 19。

節點 13 有兩個子節點（情況 3）。我們透過查詢節點 13 右子樹中的最小節點（即節點 14）來找到後繼節點（中序遍歷時緊隨其後的節點）。將值 14 放入節點 13，然後我們可以刪除節點 14。

這是 BST 的實現方式，它具有刪除節點的功能：

def delete(node, data):
    if not node:
        return None

    if data < node.data:
        node.left = delete(node.left, data)
    elif data > node.data:
        node.right = delete(node.right, data)
    else:
        # Node with only one child or no child
        if not node.left:
            temp = node.right
            node = None
            return temp
        elif not node.right:
            temp = node.left
            node = None
            return temp

        # Node with two children, get the in-order successor
        node.data = minValueNode(node.right).data
        node.right = delete(node.right, node.data)

    return node

第 1 行：這裡的 node 引數使得函式能夠遞迴地在越來越小的子樹上呼叫自身，以搜尋具有我們要刪除的 data 的節點。

第 2-8 行：這是在搜尋我們要刪除的具有正確 data 的節點。

第 9-22 行：已找到我們要刪除的節點。有三種情況：

1. 情況 1：節點沒有子節點（葉子節點）。返回 None，然後透過遞迴（第 6 行或第 8 行）成為父節點的新左子節點或右子節點。
2. 情況 2：節點只有一個子節點（左子節點或右子節點）。該左子節點或右子節點透過遞迴（第 7 行或第 9 行）成為父節點的新左子節點或右子節點。
3. 情況 3：節點同時具有左子節點和右子節點。使用 minValueNode() 函式找到中序後繼節點。我們透過將後繼節點的值設定為我們要刪除的節點的值來保留後繼節點的值，然後我們可以刪除後繼節點。

第 24 行：返回 node 以維持遞迴功能。

BST 與其他資料結構的比較

二叉搜尋樹結合了其他兩種資料結構的最佳特性：陣列和連結串列。

在 BST 中搜索值與在陣列上進行 二分搜尋 一樣快，具有相同的時複雜度 \(O(\log n)\)。

並且刪除和插入新值可以在不移動記憶體元素的情況下完成，就像使用連結串列一樣。

BST 平衡和時複雜度

在二叉搜尋樹上，插入新節點、刪除節點或搜尋節點等操作的複雜度實際上是 \(O(h)\)。這意味著樹越高（\(h\)越大），操作花費的時間就越長。

我們在上面的表格中寫搜尋值是 \(O(\log n)\) 的原因是，如果樹是“平衡的”，就像下圖所示，那確實如此。

我們將此樹稱為平衡樹，因為樹的左右兩側有大致相同數量的節點。

判斷二叉樹是否平衡的精確方法是，任何節點的左右子樹的高度只相差一。在上圖中，根節點的左子樹高度為 \(h=2\)，右子樹高度為 \(h=3\)。

對於具有大量節點（大 \(n\））的平衡 BST，我們得到高度 \(h \approx \log_2 n\)，因此搜尋、刪除或插入節點的時複雜度可以寫為 \(O(h) = O(\log n)\)。

但是，如果 BST 完全不平衡，如下面的影像所示，樹的高度約等於節點數，\(h \approx n\)，則搜尋、刪除或插入節點的時複雜度為 \(O(h) = O(n)\)。

因此，為了最佳化 BST 上的操作，必須最小化高度，為此必須使樹保持平衡。

而保持二叉搜尋樹平衡正是 AVL 樹所做的，這正是下一頁將要解釋的資料結構。

DSA 練習

透過練習來測試自己

練習

在此二叉搜尋樹中插入值為 6 的節點

新節點插入在哪裡？

The node with value 6 
becomes the right child node
of the node with value .

提交答案 »

開始練習