DSA 二叉搜索树

二叉搜索树

二叉搜索树 (BST) 是一种二叉树数据结构，其中以下属性必须对树中的任何节点“X”都成立

• X 节点的左子节点及其所有后代（子节点、子节点的子节点等）的值都小于 X 的值。
• 右子节点及其所有后代的值都大于 X 的值。
• 左右子树也必须是二叉搜索树。

这些属性使得搜索、添加和删除值的速度比普通二叉树更快。

为了使理解和实现尽可能容易，我们还假设二叉搜索树中的所有值都是唯一的。

使用下面的二叉搜索树来更好地理解这些概念和相关术语。

树的大小是它包含的节点数量 ( \(n\))。

子树从树中某个节点作为局部根开始，包含该节点及其所有后代。

节点的后代是该节点的所有子节点，以及它们的子节点，等等。只需从一个节点开始，后代将是连接到该节点以下的所有节点。

节点的高度是从该节点到叶节点之间的最大边数。

节点的中序后继是在进行中序遍历时出现在它之后的节点。上面 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 中搜索值的时

例如，对于大多数节点都在右侧的 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)\) 的原因是，如果树是“平衡”的，比如下面的图像所示，那么它是正确的。

我们称这棵树为平衡树，因为树的左右两侧大约有相同数量的节点。

判断二叉树是否平衡的精确方法是，任何节点的左右子树的高度之差最多为 1。在上面的图像中，根节点的左子树高度为 \(h=2\)，右子树高度为 \(h=3\)。

对于平衡的 BST，当节点数量很大时（\(n\) 很大），我们会得到高度 \(h \approx \log_2 n\)，因此搜索、删除或插入节点的时间复杂度可以写成 \(O(h) = O(\log n)\)。

但是，如果 BST 完全不平衡，比如下面的图像所示，树的高度大约等于节点数量，\(h \approx n\)，而搜索、删除或插入节点的时间复杂度为 \(O(h) = O(n)\)。

因此，为了优化对 BST 的操作，必须最小化高度，为此必须平衡树。

而保持二叉搜索树平衡正是 AVL 树所做的，AVL 树是下一页解释的数据结构。

DSA 练习

通过练习测试自己

练习

在该二叉搜索树中插入值为 6 的节点

新节点插入在哪里？

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

提交答案 »

开始练习