什么是二叉搜索树（BST）

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它具有以下主要特点和性质：

1. 定义：二叉搜索树是一种特殊的二叉树，其每个节点的左子树中的所有节点值都小于该节点值，而右子树中的所有节点值都大于该节点值。
2. 结构：二叉搜索树由节点组成，每个节点最多有两个子节点。
3. 排序性质：二叉搜索树的节点按照特定的顺序进行存储，每个节点的左子树中的所有节点值都小于该节点值，而右子树中的所有节点值都大于该节点值。
4. 基本操作：二叉搜索树支持多种操作，包括插入、删除、查找、中序遍历等。这些操作在理想情况下可以以 O(log n) 的复杂度完成。
5. 应用：二叉搜索树在计算机科学领域中广泛应用，特别是在需要高效搜索、插入和删除操作的场景中。
6. 实现：二叉搜索树可以用链表数据结构来表示，其中每个节点包含数据内容 key 和指向孩子（也称为子节点）的指针。
7. 性质：对于二叉搜索树的任一节点，如果左子树非空，则左子树上的值一定都小于根节点的值；如果右子树非空，则右子树上的值一定都大于根节点的值。
8. 中序遍历：二叉搜索树的中序遍历结果是一个有序序列，这使得二叉搜索树在排序和查找操作中非常高效。
9. 验证：一个有效的二叉搜索树需要满足所有节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数，并且所有左子树和右子树自身也必须是二叉搜索树。

二叉搜索树是一种高效的数据结构，适用于需要频繁进行搜索、插入和删除操作的场景。它的基本操作在理想情况下可以以 O(log n) 的复杂度完成，这使得它在处理大规模数据时表现出色。