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 .

提交答案 »

开始练习