目录

  1. 基本特性
  2. 派生特性
  3. 性能相关的特性
  4. 代码示例（伪代码）
  5. 参考资料

1. 基本特性

二分搜索树是一种特殊的二叉树，具有以下核心特性：

  • 有序性：
  • 对于任意节点，其左子树的所有节点值小于当前节点值。
  • 其右子树的所有节点值大于当前节点值。
  • 递归定义：
  • 每个节点的左右子树本身也是二分搜索树。
  • 唯一性（可选）：
  • 通常假设节点值唯一，若允许重复值，可约定放入左子树或右子树。

2. 派生特性

基于基本特性，BST 还具有以下派生特性：

  • 中序遍历有序：
  • 对 BST 进行中序遍历（左子树 → 根 → 右子树），结果是一个升序序列。
  • 示例：树 5-3-7-1-4，中序遍历输出 1, 3, 4, 5, 7。
  • 查找效率：
  • 通过比较值，可以快速定位目标节点，类似于二分查找。
  • 动态性：
  • 支持动态插入和删除操作，保持树的有序结构。

3. 性能相关的特性

BST 的性能与树形结构密切相关：

  • 高度依赖性：
  • 操作（如查找、插入、删除）的时间复杂度取决于树高 h。
  • 平衡时：h ≈ log n，复杂度 O(log n)。
  • 退化时（如链表）：h = n，复杂度 O(n)。
  • 非自平衡：
  • 普通 BST 不具备自动平衡机制，输入顺序可能导致退化。
  • 示例：插入 [1, 2, 3, 4, 5] 形成右偏树，失去效率优势。
  • 节点分布：
  • 随机插入数据时，平均高度接近 log n，具有较好性能。

4. 代码示例（伪代码）

class Node:
    value         // 节点值
    left          // 左子节点
    right         // 右子节点

class BST:
    root          // 根节点

    // 验证 BST 特性（检查有序性）
    function isBST():
        return isBSTRec(root, -∞, +∞)

    function isBSTRec(node, min, max):
        if node is null:
            return true
        if node.value <= min or node.value >= max:
            return false
        return isBSTRec(node.left, min, node.value) and
               isBSTRec(node.right, node.value, max)

    // 中序遍历（展示有序性）
    function inOrder():
        inOrderRec(root)

    function inOrderRec(node):
        if node is not null:
            inOrderRec(node.left)
            print(node.value)
            inOrderRec(node.right)

5. 参考资料

如果你需要更详细的特性分析或特定语言实现，请告诉我！