Menu
CoddyTech
开始学习

二叉搜索树（BST）

最后更新

二叉搜索树让数值保持有序：对每个节点来说，左子树中的所有值都比它小，右子树中的所有值都比它大。要插入或查找一个值，就从根节点出发，根据比较结果不断向左或向右走，每一步都把搜索范围缩小一半。点击上方的“播放”，观察数值如何通过比较找到位置，以及一次查找如何沿着树向下走。

在平衡的树上，这些操作的时间复杂度是 O(log n)。问题在于：插入已经有序的数据会让树退化成一条链表，操作变成 O(n)，这正是 AVL 树和红黑树这类自平衡变体存在的原因。

时间和空间复杂度

操作平衡时最坏情况（倾斜）
查找O(log n)O(n)
插入O(log n)O(n)
删除O(log n)O(n)
空间O(n)O(n)

分步说明（插入）

步骤发生了什么
1如果树为空，新值就成为根节点。
2否则从根节点开始。
3如果新值更小，就走到左子节点；如果更大，就走到右子节点。
4重复，直到遇到一个空位。
5把新值作为叶子节点放在那里。

示例演算

把 [5, 3, 8, 1, 4] 逐个插入一棵空树：

插入经过的路径操作
5-树为空，所以 5 成为根节点。
353 < 5，向左走；该位置为空，把 3 作为 5 的左子节点。
858 > 5，向右走；该位置为空，把 8 作为 5 的右子节点。
15 -> 31 < 5 向左走，再 1 < 3 向左走；把 1 作为 3 的左子节点。
45 -> 34 < 5 向左走，再 4 > 3 向右走；把 4 作为 3 的右子节点。

什么时候使用二叉搜索树

适合使用的情况不适合使用的情况
需要有序存储加快速查找，并且插入的数据顺序随机。数据到达时已经有序，不平衡的 BST 每次操作会退化为 O(n)。
希望通过中序遍历直接按顺序得到所有值。只需要判断元素是否存在，不需要顺序，哈希表的平均查找是 O(1)。
需要范围查询，或查找某个键的后继和前驱。需要保证 O(log n) 的上界，这时应改用自平衡的 AVL 树或红黑树。
数据经常变化，用静态有序数组更新起来代价很高。数据固定且只读，有序数组加二分查找更简单，对缓存也更友好。

Binary Search Tree 代码

简洁、可运行的 Binary Search Tree 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。

Binary Search Tree 的 Python 代码

Python
1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7
8def insert(node, key):9    if node is None:10        return Node(key)11    if key < node.key:12        node.left = insert(node.left, key)13    elif key > node.key:14        node.right = insert(node.right, key)15    return node  # duplicates are ignored16
17
18def search(node, key):19    if node is None:20        return False21    if key == node.key:22        return True23    if key < node.key:24        return search(node.left, key)25    return search(node.right, key)26
27
28def inorder(node):29    if node is None:30        return []31    return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36    root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))
在 Python 在线编辑器中运行这段代码

二叉搜索树常见问题

二叉搜索树的时间复杂度是多少？
在平衡的树上，查找、插入和删除都是 O(log n)，因为每次比较都会排除剩下一半的节点。最坏情况下（有序插入让树倾斜成一条链），它们会退化为 O(n)。
二叉树和二叉搜索树有什么区别？

二叉树是指每个节点最多有两个子节点的任意树，没有顺序规则。二叉搜索树额外要求左子树的值都比节点小、右子树的值都比节点大，正是这条规则让快速查找成为可能。

为什么二叉搜索树会变慢？
如果数值按升序（或降序）插入，每个新节点都会落在同一侧，形成一棵又高又斜的树，表现得像链表一样，每次操作都是 O(n)。自平衡树（AVL 树、红黑树）通过旋转节点来避免这种情况。
二叉搜索树和哈希表有什么区别？
哈希表的平均查找是 O(1)，但键的存储没有特定顺序，所以无法回答范围查询或后继查询。二叉搜索树稍慢，是 O(log n)，但它让键保持有序，你可以按顺序遍历它们，也能找到最接近的值。顺序重要时选 BST，只需判断是否存在时选哈希表。
什么时候该用自平衡树而不是普通 BST？
当你无法控制插入顺序，又需要保证 O(log n) 的性能时，就用自平衡树（AVL 树、红黑树）。普通 BST 适合教学、小数据集，或键以随机顺序到达的场景，但它无法防止倾斜带来的最坏情况。
BST 的中序遍历会返回有序的值吗？

会。先访问左子树，再访问节点本身，最后访问右子树，就能按升序得到所有键，这直接来自 BST 的规则。一个常见的错误是对普通二叉树抱有同样的期待：没有顺序规则，中序遍历得到的序列没有任何意义。

相关资源

更多可视化

Coddy 编程语言插图

在 Coddy 掌握算法

开始