3.2 二叉查找树
Robert Sedgewick Kevin Wayne
在本节中我们将学习一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体来说,就是使用每个结点含有两个链接(链表中每个结点只含有一个链接)的二叉查找树来高效地实现符号表,这也是计算机科学中最重要的算法之一。
首先,我们需要定义一些术语。我们所使用的数据结构由结点组成,结点包含的链接可以为空(null)或者指向其他结点。在二叉树中,每个结点只能有一个父结点(只有一个例外,也就是根结点,它没有父结点),而且每个结点都只有左右两个链接,分别指向自己的左子结点和右子结点(如图 3.2.1 所示)。尽管链接指向的是结点,但我们可以将每个链接看做指向了另一棵二叉树,而这棵树的根结点就是被指向的结点。因此我们可以将二叉树定义为一个空链接,或者是一个有左右两个链接的结点,每个链接都指向一棵(独立的)子二叉树。在二叉查找树中,每个结点还包含了一个键和一个值,键之间也有顺序之分以支持高效的查找。
![](https://static001.geekbang.org/files/resource/ebook/100010/image01308.gif)
图 3.2.1 详解二叉树
定义。一棵二叉查找树(BST)是一棵二叉树,其中每个结点都含有一个 Comparable 的键(以及相关联的值)且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。
我们在画出二叉查找树时会将键写在结点上。我们使用“A 是 E 的左子结点”的说法用键指代结点。我们用连接结点的线表示链接,并将键对应的值写在结点旁边(若值不确定则省略)。除了空结点只表示为向下的一条线段以外,每个结点的链接都指向它下方的结点。和以前一样,我们在例子中只会使用索引测试用例生成的单个字母作为键,如图 3.2.2 所示。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
本文深入介绍了二叉查找树(BST)的基本概念和实现方法。BST将链表插入的灵活性和有序数组查找的高效性结合起来,是一种重要的符号表实现。文章首先介绍了BST的定义和基本术语,包括结点、链接、二叉树、二叉查找树等概念。随后详细讨论了BST的基本实现,包括数据表示和查找方法。通过递归算法实现了在BST中查找键的过程,以及命中和未命中的情况。文章还给出了基于BST的符号表的API实现代码,并介绍了树的结构和节点对象的组成。 此外,文章分析了BST的运行时间取决于树的形状,而树的形状又取决于键被插入的先后顺序。在最好的情况下,树是完全平衡的,每条空链接和根结点的距离都为约logN。在最坏的情况下,搜索路径上可能有N个结点。对于随机键构造的BST,命中查找平均所需的比较次数约为2lnN。这些分析为读者提供了对BST性能的直观认识。 文章通过简洁的语言和直观的图示,使读者能够快速理解了BST的基本概念、实现方法以及性能分析。此外,还介绍了BST在有序符号表API中的应用,包括最大键和最小键的查找、向上取整和向下取整的实现方法,以及选择操作的相关内容。这些内容丰富了读者对BST的理解,为他们在实际应用中提供了更多的参考和指导。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论