Binary Search Tree

二元搜尋樹（Binary search tree, BST）是一種二元樹（binary tree）。它提供了一些有用操作，包含 search、insert、delete、minimum、maximum、successor 和 predecessor。

Binary Search Tree

一個 binary search tree 必須滿足以下特性：

• 每個 node 有一個 key，任兩個 node 的 key 都不會相同。
• 左子樹的所有 keys 都必須比 root 的 key 小。
• 右子樹的所有 keys 都必須比 root 的 key 大。
• 左右子樹也都是 binary search trees。

以下都是合法的 binary search trees。

搜尋

假設我們要在一個 binary search tree 中搜尋 x ，其演算法如下。我們列出兩種演算法，一種是用 recursive 的方式，另一種是 iterative 的方式。兩種方式的時間複雜度都是 ，其中 h 是樹的高度。

Algorithm BSTSearch(root, x) {
    if root == null {
        return null
    } else if root.key == x {
        return root
    } else if root.key > x {
        return Search(root.left, x)
    } else {
        return Search(root.right, x)
    }
}

Algorithm BSTSearch(root, x) {
    node := root
    while node != null {
        if node.key == x {
            return node
        } else if node.key > x {
            node = node.left
        } else {
            node = node.right
        }
    }
    return null
}

Minimum 和 Maximum

在一個 binary search tree 中，要找最小值時，只要一直向左邊找下去，就會找到最小值。反之，要找最大值時，只要一直向右邊找下去，就會找到最大值。如下圖中，最小的值是在最左邊的 3，而最大的值是在最右邊的 48。

Algorithm BSTMinimum(node) {
    while node.left != null {
        node = node.left
    }
    return node
}

Algorithm BSTMaximum(node) {
    while node.right != null {
        node = node.right
    }
    return node
}

Successor 和 Predecessor

在 binary search tree 中，對於任一個 node x，它的 successor 是所有大於 x 中最小的 key；它的 predecessor 是所有小於 x 中最大的 key。如下圖中，20 的 successor 是 30，而 20 的 predecessor 是 10。

Algorithm BSTSuccessor(node) {
    if node.right != null {
        return BSTMinimum(node.right)
    }
    p := node.parent
    while p != null && node == p.right {
        node := p
        p := p.parent
    }
    return p
}

Algorithm BSTMinimum(node) {
    if node.left != null {
        return BSTMaximum(node.left)
    }
    p := node.parent
    while p != null && node == p.left {
        node := p
        p := parent
    }
    return p
}

插入

假設我們要在一個 binary search tree 中插入 x，其演算法如下。首先，先試著是搜尋 x，如果找到 key 為 x 的 node，則我們無法插入 x，因為它已經存在了。如果找不到的話，我們將最後一次查詢的 node 存在 parent 中。如果 x 比 parent.key 小，則將 x 插入到 parent.left。反之，則插入到 parent.right。插入的時間複雜度是 ，其中 h 是樹的高度。

Algorithm BSTInsertion(root, x) {
    node := root
    parent := root
    while node != null {
        parent := node
        if node.key == x {
            // found a node with key x
            return null
        } else if node.key > x {
            node = node.left
        } else {
            node = node.right
        }
    }

    q := TreeNode(x)
    q.left = q.right = null
    if root == null {
        return q
    } else {
        if parent.key > x {
            parent.left = q
        } else {
            parent.right = q
        }
        return root
    }
}

刪除

假設在一個 binary search tree 中刪除一個 node x 時，我們需要考慮三種情況。

第一種是當 x 沒有 children 的時候，我們只要直接將 x 刪除。如下圖中，我們直接刪除 28 即可。

第二種是當 x 只有一個 child 時，我們只要將 x 的 parent 和 child 連起來，並刪除 x。如下圖中，我們將 30 與 50 連起來，並刪除 40。

第三種是當 x 有兩個 children 時，我們要先找到 x 的 successor z。然後，將 z 從 binary search tree 中刪除。最後，將 x 的 key 用 z 的 key 來取代。因為 z 是 x 的 successor，所以 z 必定沒有左子樹。所以在刪除 z 的時候，會面臨到第一種或第二種的情況。

如下圖中，我們要刪除 10。我們先找到 10 的 successor，其為 12，並將其刪除。然後再將要刪除的 node 的 key 改為 12。

Algorithm BSTDelete(Tree, x) {
    if x.left == null || x.right == null {
        successor := x
    } else {
        successor := BSTSuccessor(x)
    }

    if successor.left != null {
        y := successor.left
    } else {
        y := successor.right
    }
    if y != null {
        y.parent := successor.parent
    }

    if successor.parent == null {
        Tree.root := y
    } else {
        if successor == successor.parent.left {
            successor.parent.left = y
        } else {
            successor.parent.right = y
        }
    }

    if successor != x {
        x.key = successor.key
    }
}

時間複雜度

Algorithm	Average	Worst Case
Search
Insert
Delete

參考

• Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithm.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 4th Ed.
• Binary search tree, Wikipedia.