二叉查找树

核心思想：

• 结合链表插入的灵活性和有序数组查找的高效性的符号表实现。
• 使用二叉查找树这种数据结构，每个结点最多有两个子节点（左子节点和右子节点）。

• 运行时间取决于树的形状:

  • 最佳情况 (完全平衡): 查找路径长度 ≈ lgN。
  • 最坏情况 (单链): 查找路径长度 = N。
  • 一般情况: 更接近最佳情况。
  • 随机键模型: 假设键的分布是随机的，BST 性能类似于快速排序。

• 命题 C: 随机键构造的 BST 中，查找命中平均比较次数 ≈ 2lnN (约 1.39lgN)。

  • 证明：基于内部路径长度和递归关系式，与快速排序分析类似。
• 命题 D: 随机键构造的 BST 中，插入和查找未命中平均比较次数 ≈ 2lnN (约 1.39lgN)。
  • 证明：插入操作和查找未命中平均比查找命中多一次比较。
• 结点计数器 N 的必要性:
  • 支持 rank() 和 select() 等有序操作必需。
  • 简化 size() 方法实现，避免线性时间复杂度的递归 size()。

算法（数据结构）	最坏情况下的运行时间的增长数量级 (N 次插入之后)	平均情况下的运行时间的增长数量级 (N 次插入随机键之后)	是否支持有序性相关的操作
	查找	插入	查找命中
顺序查找（无序链表）	N	N	N/2
二分查找（有序数组）	lgN	N	lgN
二叉树查找（二叉查找树）	N	N	1.39lgN