3.2 二叉查找树

本文深入介绍了二叉查找树（BST）的基本概念和实现方法。BST将链表插入的灵活性和有序数组查找的高效性结合起来，是一种重要的符号表实现。文章首先介绍了BST的定义和基本术语，包括结点、链接、二叉树、二叉查找树等概念。随后详细讨论了BST的基本实现，包括数据表示和查找方法。通过递归算法实现了在BST中查找键的过程，以及命中和未命中的情况。文章还给出了基于BST的符号表的API实现代码，并介绍了树的结构和节点对象的组成。 此外，文章分析了BST的运行时间取决于树的形状，而树的形状又取决于键被插入的先后顺序。在最好的情况下，树是完全平衡的，每条空链接和根结点的距离都为约logN。在最坏的情况下，搜索路径上可能有N个结点。对于随机键构造的BST，命中查找平均所需的比较次数约为2lnN。这些分析为读者提供了对BST性能的直观认识。 文章通过简洁的语言和直观的图示，使读者能够快速理解了BST的基本概念、实现方法以及性能分析。此外，还介绍了BST在有序符号表API中的应用，包括最大键和最小键的查找、向上取整和向下取整的实现方法，以及选择操作的相关内容。这些内容丰富了读者对BST的理解，为他们在实际应用中提供了更多的参考和指导。